树
前面已经了解了线性的数据结构(数组,链表,栈,队列,散列表)
现在来了解一下非线性的数据结构
树和图就是典型的非线性数据结构
树的定义
树是n(n>=0)个结点的有限集.当n = 0时,称为空树
非空树的特定
- 有且仅有一个特定的称为根的结点
- 当n>1时,其余的结点可以分为m(m>0)个互不相交的有限集,每一个集合本身又是一个树,并成为根的子树
树的成分
图中深红色的点就是根节点（root);结点5，6，7，8都是树的末端，没有”孩子”结点,就被称为叶子节点;虚线内的结点就是根结点的一个子树。
结点2是4的父节点 ; 结点4的是结点7,8的父节点,因为结点7,8是节点4衍生出来的节点,所以节点7,8也称为节点4的孩子节点 ; 节点5与节点4同级,并且由同一个父节点衍生出来,所以是节点4的兄弟节点。
二叉树
二叉树是树的一种特殊但又很常见的形式,故名思意,二叉树的每个节点最多有2个孩子节点 ( 0 <= 孩子节点个数 <= 2 )
二叉树的两个节点一个被称为左孩子,一个被称为右孩子
二叉树还有两种情形:
- 满二叉树
一个二叉树的所有非叶子节点又有左右孩子节点(两个都有),并且,所有叶子节点都在同一层级,就叫满二叉树。简单来说就是满二叉树的每一个分支都是满的
- 完全二叉树
对于一个有n个节点的二叉树,按照层级顺序编号,则所有节点的编号为从1到n。如果这个树所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同,则这个二叉树为完全二叉树.
二叉树在内存中的存储
二叉树属于逻辑结构,可以通过多种物理结构来表达
例如:
- 链式存储结构
- 数组
链式储存结构
也就是用数组来储存,这种储存结构是最直观的结构,与原始的数组相比,这种链表会多一个指针,因为原本的链表节点只需要指向下一个节点,但是对于二叉树来说需要指向两个节点,所以一般建立Node的数据结构属性为:
1
2
3
4
5
| class Node {
private int Date;
private Node left;
private Node right;
}
|
数组存储结构
二叉树对应的节点的位置是规定好了的,对应到数组中的下标位置,如果在二叉树中该位置的节点被空出来了,那么在数组中该位置的节点也会被空出来.
==对应的下标位置的规律:假设一个父节点的下标是parent,那么它的左孩子节点下标就是2parent+1 ; 右孩子节点的下标就是2parent+2==。==反过来,假设一个左孩子节点的下标是leftChild,那么它的父节点的下标就是(leftChild-1)/2==
但是在枝叶很稀疏的情况下,用数组结构来储存是很浪费空间的,所有就需要二叉堆
二叉树的应用
主要应用于查找操作和维持相对顺序这两方面
查找
二叉查找树：
- 如果左子树不为空，则左子树上所有节点的值均小于根节点的值
- 如果右子树不为空，则右子树上所有节点的值均大于根节点的值
- 左、右子树也都是二叉查找树
如图，这就是一个二叉查找树。
假设要找4，那么4先于根节点相比，4 < 6,那么就访问左孩子节点即3,发现4>3,就接着访问右孩子节点,即4,发现4 = 4就找到了
==对于一个节点分布相对均衡的二叉查找树来说，如果节点总数是n，那么搜索节点的时间复杂度就是O(logn)，和树的深度是一样的==
这种通过比较大小就可以“淘汰”“一半”元素的方法和二分查找算法非常相似
维持相对顺序
二叉查找树还有一个名字叫二叉排序树
相当于是创建一个二叉查找树,为了形成二叉查找树,就必须要求新插入的节点遵循二叉查找树的原则
二叉树的遍历
从节点之间位置关系的角度来看,二叉树的遍历分为4种:
- 前序遍历
- 中序遍历
- 后序遍历
- 层序遍历
从更宏观的角度来看,二叉树的遍历归结为两大类
- 深度优先遍历(前序遍历,中序遍历,后序遍历，层序遍历)
- 广度优先遍历(层序遍历)
二叉树的遍历
二叉树的遍历一定是先左后右的，所谓的前序，中序，后序遍历其实的是根节点的前中后位置
前序遍历
他的访问顺序是：根节点→左子树→右子树
所以上图前序遍历的结果是：A→B→D→E→C→F
访问顺序如下
数据访问顺序：
递归方式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
preOrder(root,list);
return list;
}
public void preOrder(TreeNode root,List<Integer> list) {
if(root == null) return;
list.add(root.val);
preOrder(root.left,list);
preOrder(root.right,list);
}
}
|
说明
题目已经生成好了二叉树，给定的参数是树的根节点，要求前序遍历二叉树，讲值按前序遍历的顺序存进一个List<Integer>中返回
解析
递归的方式就是一层一层的调用函数，一般都是先考虑走到最里面，也就是考虑什么情况是最里面，也即是边界条件了。
考虑到的边界条件就是当二叉树的节点是空的时候表示不能再继续往下走了，这个时候就是最里面了就该返回了
这里的返回条件就是，如果数据是不想要的（空节点肯定不要）就返回，也就是说目前这一层返回到的层就是最后一个满足需求想要的数据层了，这个时候就可以开始收集数据了
- 因为是二叉树的前序遍历，所以是要先第一次遍历到的就是根节点的值，就先接收根节点的值，之后再往下走
- 需要先去走左节点再走右节点，因为树的遍历只是和根节点有关，和左右节点关系不大，永远都是先左后右
总结
对于二叉树的遍历来说，其实大体都一样，就是说取值的位置，前序遍历是先取值再左再右。中序遍历就是先左再取值再右。后序遍历就是先左再右再取值。
迭代方式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null) return list;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode tempNode = stack.pop();
list.add(tempNode.val);
if(tempNode.right != null){
stack.push(tempNode.right);
}
if(tempNode.left != null){
stack.push(tempNode.left);
}
}
return list;
}
}
|
说明
题目已经生成好了二叉树，给定的参数是树的根节点，要求前序遍历二叉树，讲值按前序遍历的顺序存进一个List<Integer>中返回
解析
- 实际上用和用递归的方式的思想是差不多的，用栈实现了非递归，但是栈本身就是前进后出的数据结构，本身和函数就有很大的相似之处，所以思路也差不多
- 但是和递归有不同的是，递归接收空值，而迭代需要提前判断，要避免空值，所以需要提前判断数据是否为空，需要先存进一个数据才能开始函数
- 这里要解释一下数据和程序进行浅层的关系
- 对于递归来说，是函数式，如果有数据就可以执行函数，就会一层一层调用，所以对于空值这种数据来说也能继续运行
- 对于迭代来说，使用的是栈这种数据类型，并且使用的是当栈中数据不为空才继续执行，所以栈一空循环就结束了，所以要一直保持栈中的数据不为空。
- 并且在这里，如果将空的值放进来就是垃圾数据，会将空值存入结果列表中，并且之后的判断也是无用判断
- 和递归方式不同的注意点：
- 这里还是想要先到左取数据再到右取数据，对于递归来说，就是先调用函数，将左节点传进去。但是对于迭代，就需要先将右节点存入栈中，因为先存入的东西后执行。
总结
整体思路和递归一致，有一些小细节不同，需要注意。
中序遍历
他的访问顺序是：左子树→根节点→右子树
所以上图前序遍历的结果是：D→B→E→A→F→C
访问顺序如下
数据访问顺序：
递归方式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
inOrder(root,list);
return list;
}
public void inOrder(TreeNode root,List<Integer> list) {
if(root == null) return;
inOrder(root.left,list);
list.add(root.val);
inOrder(root.right,list);
}
}
|
说明
题目已经生成好了二叉树，给定的参数是树的根节点，要求中序遍历二叉树，讲值按前序遍历的顺序存进一个List<Integer>中返回
具体解析和总结看前序遍历就OK，大致思路是一样的。
迭代方式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null) return list;
Stack<TreeNode> stack = new Stack<>();
while(root != null || !stack.isEmpty()){
while(root != null){
stack.push(root);
root = root.left;
}
if(!stack.isEmpty()){
root = stack.pop();
list.add(root.val);
root = root.right;
}
}
return list;
}
}
|
整体思路和递归一致，就是想要疯狂向左走，直到左边为空了，然后再存储，实际上存储到的就是左节点了。
后序遍历
他的访问顺序是：左子树→右子树→根节点
所以上图前序遍历的结果是：D→E→B→F→C→A
访问顺序如下
递归方式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
postOrder(root,list);
return list;
}
public void postOrder(TreeNode root,List<Integer> list) {
if(root == null) return;
postOrder(root.left,list);
postOrder(root.right,list);
list.add(root.val);
}
}
|
说明
题目已经生成好了二叉树，给定的参数是树的根节点，要求后序遍历二叉树，讲值按前序遍历的顺序存进一个List<Integer>中返回
具体解析和总结看前序遍历就OK，大致思路是一样的。
迭代方式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null) return list;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode tempNode = stack.pop();
list.add(tempNode.val);
if(tempNode.left != null){
stack.push(tempNode.left);
}
if(tempNode.right != null){
stack.push(tempNode.right);
}
}
Collections.reverse(list);
return list;
}
}
|
后序遍历的递归需要先“假前序”然后再倒序一下。
前序是先让根节点入栈，再让右节点入栈，左节点最后入栈。而数据形式是：根节点-左节点-右节点。
分析得：想要的数据形式是：左节点-右节点-根节点。
如果和前序遍历的迭代方法类似代码，但是入栈顺序为：根节点-左节点-右节点。这样的数据形式就是：根节点-右节点-左节点。如果倒序一下数据形式就是：左节点-右节点-根节点了。
根据这样的规律写出了程序——先“假倒序”再倒叙。
层序遍历
深度优先搜索
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> list = new ArrayList<>();
dfs(list,root,0);
return list;
}
public void dfs(List<List<Integer>> list,TreeNode root,int level){
if(root == null) return;
if(list.size() <= level){
list.add(new ArrayList<>());
}
list.get(level).add(root.val);
dfs(list,root.left,level+1);
dfs(list,root.right,level+1);
}
}
|
深度优先搜索就是使用递归的一种方式，在参数中做出改变。
这里就是访问左右节点，访问了左右节点，那么左右节点肯定是下一层，所以参数中level+1，表示层数增加
list表示的是最外层，内部的元素就是一个子list，通过get(level)指定对应层数的子list,就可将元素添加岛对应层。如果level已经大于等于list的size了就需要新建一层子list。
广度优先搜索
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> list = new ArrayList<>();
if(root == null) return list;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
int size = queue.size();
List<Integer> tempList = new ArrayList<>();
for(int i = 0 ; i < size ; i++){
TreeNode node = queue.poll();
tempList.add(node.val);
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.right);
}
list.add(tempList);
}
return list;
}
}
|
记得使用BFS需要使用队列这种数据结构就好了，每一次添加到临时列表中前先判断队列中有几个元素（每一批队列中的的数据都是同一层的）
Morris遍历
前面讲的二叉树的几种遍历方式，如果使用的是非递归方式，我们要么需要一个栈，要么需要一个队列来维护节点之间的关系。如果使用Morris遍历就不需要了，他的实现过程其实就是把叶子节点的指针给利用起来，因为一般情况下，二叉树的叶子节点是没有子节点的，也就是说他们是指向空，这样总感觉有点浪费，Morris的实现原理其实就是把叶子节点的指针给利用了起来。
对于Morris的中序遍历可以把它看做是把二叉树拉直变成了链表。
前序遍历和中序遍历
前序遍历和中序遍历逻辑是一样的，这里以中序遍历为例。中序遍历的数据冯雯顺序是：左子树-根节点-右子树。
实现步骤
判断cur是否为空，如果为空就停止遍历。
如果cur不为空
- 如果cur没有左子节点，打印cur的值，然后让root指向他的右子节点，即
cur=cur.right
- 如果cur有左子节点，则从左子节点中找到最右边的节点pre（用循环的方式）。
- 如果pre的右节点不为空，且不等于cur即
while(pre.right != null && pre.light != cur)，就让pre指向pre的右节点，即pre = pre.right。这样的最右实际上不一定是为空才是最右边，下一个节点是cur也被认为是最右边，所以要具体再判断是那种情况。
- 如果pre的右子节点为空，就让pre的右子节点指向cur，即
pre.right=cur，然后cur指向他的左子节点，即cur=cur.left。
- 如果pre的右子节点不为空，就让他指向空，即
pre.right=null，然后输出cur节点的值，并将节点cur指向其右子节点，即cur=cur.right。
重复步骤2，直到节点cur为空为止。
中序遍历代码
光看上面的实现步骤还有点抽象，看看代码再分析是怎么样的过程。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
TreeNode cur = root;
while (cur != null) {
if (cur.left == null) {
list.add(cur.val);
cur = cur.right;
} else {
TreeNode pre = cur.left;
while (pre.right != null && pre.right != cur)
pre = pre.right;
if (pre.right == null) {
pre.right = cur;
cur = cur.left;
} else {
pre.right = null;
list.add(cur.val);
cur = cur.right;
}
}
}
return list;
}
}
|
演示图
看了代码还不直观就看图理解吧
动态图：
连续图：
前序遍历代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
TreeNode cur = root;
while (cur != null) {
if (cur.left == null) {
res.add(cur.val);
cur = cur.right;
} else {
TreeNode pre = cur.left;
while (pre.right != null && pre.right != cur)
pre = pre.right;
if (pre.right == null) {
pre.right = cur;
res.add(cur.val);
cur = cur.left;
} else {
pre.right = null;
cur = cur.right;
}
}
}
return res;
}
}
|
前序遍历和中序遍历很类似，只是添加节点（访问数据）的时机不同而已。
前序遍历是：如果左边没有被遍历，那么在移动cur前就访问cur。
中序遍历是：如果左边已经被遍历了，或者无法遍历了（已经是最左边的叶子节点了），才访问cur
后序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if (root == null) {
return res;
}
TreeNode p1 = root, p2 = null;
while (p1 != null) {
p2 = p1.left;
if (p2 != null) {
while (p2.right != null && p2.right != p1) {
p2 = p2.right;
}
if (p2.right == null) {
p2.right = p1;
p1 = p1.left;
continue;
} else {
p2.right = null;
addPath(res, p1.left);
}
}
p1 = p1.right;
}
addPath(res, root);
return res;
}
public void addPath(List<Integer> res, TreeNode node) {
int count = 0;
while (node != null) {
++count;
res.add(node.val);
node = node.right;
}
int left = res.size() - count, right = res.size() - 1;
while (left < right) {
int temp = res.get(left);
res.set(left, res.get(right));
res.set(right, temp);
left++;
right--;
}
}
}
|
实现步骤
其实Morris算法就是要利用大量的叶子节点形成链表形式的数，所以大致思路和前面也差不多，但是实现步骤有一点点不同。
新建临时节点，令该节点为 root；
如果当前节点的左子节点为空，则遍历当前节点的右子节点；
如果当前节点的左子节点不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点；
- 如果前驱节点的右子节点为空，将前驱节点的右子节点设置为当前节点，当前节点更新为当前节点的左子节点。
- 如果前驱节点的右子节点为当前节点，将它的右子节点重新设为空。倒序输出从当前节点的左子节点到该前驱节点这条路径上的所有节点。当前节点更新为当前节点的右子节点。
重复步骤 2 和步骤 3，直到遍历结束。
遍历结果的数据特点
前序遍历
前序遍历的第一个元素是根节点
中序遍历
根节点分左右子树
后续遍历
根节点是最后一个元素
作用与应用
由于中序遍历的分左右的特殊性，只要能找出中序遍历的结果中的根节点就能区分处左右子树了，而对于前序遍历的结果和后序遍历的结果都很好得到根节点，所以可以利用前序遍历的结果和中序遍历的结果重新构建出原本的二叉树，也可以利用后序遍历的结果和中序遍历的结果构造出原本的二叉树。
从中序与后序遍历序列构造二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
int len=inorder.length;
if(len==0)return null;
return dfs(inorder,postorder,0,len-1,0,len-1);
}
TreeNode dfs(int[] inorder, int[] postorder,int head1,int tail1, int head2,int tail2){
if(head2>tail2)return null;
int val=postorder[tail2];
TreeNode root=new TreeNode(val);
if(head2==tail2)return root;
int mid=0;
while(inorder[head1+mid]!=val)mid++;
root.left=dfs(inorder, postorder, head1, head1+mid-1, head2, head2+mid-1);
root.right=dfs(inorder, postorder, head1+mid+1, tail1, head2+mid, tail2-1);
return root;
}
}
|
从前序与中序遍历序列构造二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
public TreeNode buildTree(int[] preorder, int[] inorder) {
List<Integer> preorderList = new ArrayList<>();
List<Integer> inorderList = new ArrayList<>();
for (int i = 0; i < preorder.length; i++) {
preorderList.add(preorder[i]);
inorderList.add(inorder[i]);
}
return helper(preorderList, inorderList);
}
private TreeNode helper(List<Integer> preorderList, List<Integer> inorderList) {
if (inorderList.size() == 0)
return null;
int rootVal = preorderList.remove(0);
TreeNode root = new TreeNode(rootVal);
int mid = inorderList.indexOf(rootVal);
root.left = helper(preorderList, inorderList.subList(0, mid));
root.right = helper(preorderList, inorderList.subList(mid + 1, inorderList.size()));
return root;
}
|
构建二叉树
由数组构成二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| public class testHashMap {
public static int index = 0;
public static void main(String[] args) {
TreeNode root = new TreeNode();
Integer[] elements = {1,3,null,4,6,null,9};
TreeNode cur = root;
createTree(cur,elements);
}
public static void createTree(TreeNode root,Integer[] elements){
if(index >= elements.length){
return;
}
if(elements[index] != null){
root.val = elements[index++];
TreeNode node = new TreeNode();
root.left = node;
createTree(node,elements);
TreeNode node2 = new TreeNode();
root.right = node2;
createTree(node2,elements);
} else {
index++;
}
}
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
|
wechat
alipay
