数据结构与算法---树结构(Tree structure)
为什么需要树这种数据结构
数组存储方式的分析
- 优点:通过下标方式访问元素,速度快。对于有序数组,还可使用二分查找提高检索速度。
- 缺点:如果要检索具体某个值,或者插入值(按一定顺序)会整体移动,效率较低。
链式存储方式的分析
- 优点:在一定程度上对数组存储方式有优化(比如:插入一个数值节点,只需要将插入节点,链接到链表中即可, 删除效率也很好)。
- 缺点:在进行检索时,效率仍然较低,比如(检索某个值,需要从头节点开始遍历)
树存储方式的分析
能提高数据存储,读取的效率, 比如利用 二叉排序树(Binary Sort Tree),既可以保证数据的检索速度,同时也可以保证数据的插入,删除,修改的速度。
树结构示意图
二叉树的概念
- 树有很多种,每个节点最多只能有两个子节点的一种形式称为二叉树。
- 二叉树的子节点分为左节点和右节点。
- 如果该二叉树的所有叶子节点都在最后一层,并且结点总数= 2^n -1 , n 为层数,则我们称为满二叉树。
- 如果该二叉树的所有叶子节点都在最后一层或者倒数第二层,而且最后一层的叶子节点在左边连续,倒数第二层的叶子节点在右边连续,我们称为完全二叉树。
二叉树遍历的说明
前序遍历: 先输出父节点,再遍历左子树和右子树
中序遍历: 先遍历左子树,再输出父节点,再遍历右子树
后序遍历: 先遍历左子树,再遍历右子树,最后输出父节点
小结: 看输出父节点的顺序,就确定是前序,中序还是后序
示例:
将下列二叉树 前序、中序、后序输出
1 package com.tree;
2
3 /**
4 * Created by wanbf on 2019/7/9.
5 */
6
7 public class BinaryTreeDemo {
8
9 public static void main(String[] args) {
10 //先需要创建一颗二叉树
11 BinaryTree binaryTree = new BinaryTree();
12 //创建需要的结点
13 HeroNode root = new HeroNode(1, "宋江");
14 HeroNode node2 = new HeroNode(2, "吴用");
15 HeroNode node3 = new HeroNode(3, "卢俊义");
16 HeroNode node4 = new HeroNode(4, "林冲");
17 //HeroNode node5 = new HeroNode(5, "关胜");
18
19 //说明,我们先手动创建该二叉树,后面我们学习递归的方式创建二叉树
20 root.setLeft(node2);
21 root.setRight(node3);
22 node3.setRight(node4);
23 //node3.setLeft(node5);
24 binaryTree.setRoot(root);
25
26 //测试
27 System.out.println("前序遍历"); // 1,2,3,4
28 binaryTree.preOrder();
29
30 //测试
31 System.out.println("中序遍历");
32 binaryTree.infixOrder(); // 2,1,3,4
33
34 System.out.println("后序遍历");
35 binaryTree.postOrder(); // 2,4,3,1
36
37 }
38
39 }
40
41
42
43
44 //定义BinaryTree 二叉树
45 class BinaryTree {
46 private HeroNode root;
47
48 public void setRoot(HeroNode root) {
49 this.root = root;
50 }
51 //前序遍历
52 public void preOrder() {
53 if(this.root != null) {
54 this.root.preOrder();
55 }else {
56 System.out.println("二叉树为空,无法遍历");
57 }
58 }
59
60 //中序遍历
61 public void infixOrder() {
62 if(this.root != null) {
63 this.root.infixOrder();
64 }else {
65 System.out.println("二叉树为空,无法遍历");
66 }
67 }
68 //后序遍历
69 public void postOrder() {
70 if(this.root != null) {
71 this.root.postOrder();
72 }else {
73 System.out.println("二叉树为空,无法遍历");
74 }
75 }
76 }
77
78
79 //先创建HeroNode 结点
80 class HeroNode {
81 private int no;
82 private String name;
83 private HeroNode left; //默认null
84 private HeroNode right; //默认null
85 public HeroNode(int no, String name) {
86 this.no = no;
87 this.name = name;
88 }
89 public int getNo() {
90 return no;
91 }
92 public void setNo(int no) {
93 this.no = no;
94 }
95 public String getName() {
96 return name;
97 }
98 public void setName(String name) {
99 this.name = name;
100 }
101 public HeroNode getLeft() {
102 return left;
103 }
104 public void setLeft(HeroNode left) {
105 this.left = left;
106 }
107 public HeroNode getRight() {
108 return right;
109 }
110 public void setRight(HeroNode right) {
111 this.right = right;
112 }
113 @Override
114 public String toString() {
115 return "HeroNode [no=" + no + ", name=" + name + "]";
116 }
117
118 //编写前序遍历的方法
119 public void preOrder() {
120 System.out.println(this); //先输出父结点
121 //递归向左子树前序遍历
122 if(this.left != null) {
123 this.left.preOrder();
124 }
125 //递归向右子树前序遍历
126 if(this.right != null) {
127 this.right.preOrder();
128 }
129 }
130 //中序遍历
131 public void infixOrder() {
132
133 //递归向左子树中序遍历
134 if(this.left != null) {
135 this.left.infixOrder();
136 }
137 //输出父结点
138 System.out.println(this);
139 //递归向右子树中序遍历
140 if(this.right != null) {
141 this.right.infixOrder();
142 }
143 }
144 //后序遍历
145 public void postOrder() {
146 if(this.left != null) {
147 this.left.postOrder();
148 }
149 if(this.right != null) {
150 this.right.postOrder();
151 }
152 System.out.println(this);
153 }
154 }
代码
1 前序遍历
2 HeroNode [no=1, name=宋江]
3 HeroNode [no=2, name=吴用]
4 HeroNode [no=3, name=卢俊义]
5 HeroNode [no=4, name=林冲]
6 中序遍历
7 HeroNode [no=2, name=吴用]
8 HeroNode [no=1, name=宋江]
9 HeroNode [no=3, name=卢俊义]
10 HeroNode [no=4, name=林冲]
11 后序遍历
12 HeroNode [no=2, name=吴用]
13 HeroNode [no=4, name=林冲]
14 HeroNode [no=3, name=卢俊义]
15 HeroNode [no=1, name=宋江]
输出
前上图的 3号节点 "卢俊" , 增加一个左子节点 [5, 关胜]
使用前序,中序,后序遍历,请写出各自输出的顺序是什么?
1 public static void main(String[] args) {
2 //先需要创建一颗二叉树
3 BinaryTree binaryTree = new BinaryTree();
4 //创建需要的结点
5 HeroNode root = new HeroNode(1, "宋江");
6 HeroNode node2 = new HeroNode(2, "吴用");
7 HeroNode node3 = new HeroNode(3, "卢俊义");
8 HeroNode node4 = new HeroNode(4, "林冲");
9 HeroNode node5 = new HeroNode(5, "关胜");
10
11 //说明,我们先手动创建该二叉树,后面我们学习递归的方式创建二叉树
12 root.setLeft(node2);
13 root.setRight(node3);
14 node3.setRight(node4);
15 node3.setLeft(node5);
16 binaryTree.setRoot(root);
17
18 //测试
19 System.out.println("前序遍历"); // 1,2,3,5,4
20 binaryTree.preOrder();
21
22 //测试
23 System.out.println("中序遍历");
24 binaryTree.infixOrder(); // 2,1,5,3,4
25
26 System.out.println("后序遍历");
27 binaryTree.postOrder(); // 2,5,4,3,1
28
29 }
代码
1 前序遍历
2 HeroNode [no=1, name=宋江]
3 HeroNode [no=2, name=吴用]
4 HeroNode [no=3, name=卢俊义]
5 HeroNode [no=5, name=关胜]
6 HeroNode [no=4, name=林冲]
7 中序遍历
8 HeroNode [no=2, name=吴用]
9 HeroNode [no=1, name=宋江]
10 HeroNode [no=5, name=关胜]
11 HeroNode [no=3, name=卢俊义]
12 HeroNode [no=4, name=林冲]
13 后序遍历
14 HeroNode [no=2, name=吴用]
15 HeroNode [no=5, name=关胜]
16 HeroNode [no=4, name=林冲]
17 HeroNode [no=3, name=卢俊义]
18 HeroNode [no=1, name=宋江]
输出
二叉树-查找指定节点
1.编写前序查找,中序查找和后序查找的方法。
2.并分别使用三种查找方式,查找 heroNO = 5 的节点
3.并分析各种查找方式,分别比较了多少次
思路分析
1 /**
2 * Created by wanbf on 2019/7/9.
3 */
4 public class BinaryTreeDemo {
5
6 public static void main(String[] args) {
7 //先需要创建一颗二叉树
8 BinaryTree binaryTree = new BinaryTree();
9 //创建需要的结点
10 HeroNode root = new HeroNode(1, "宋江");
11 HeroNode node2 = new HeroNode(2, "吴用");
12 HeroNode node3 = new HeroNode(3, "卢俊义");
13 HeroNode node4 = new HeroNode(4, "林冲");
14 HeroNode node5 = new HeroNode(5, "关胜");
15
16 //说明,我们先手动创建该二叉树,后面我们学习递归的方式创建二叉树
17 root.setLeft(node2);
18 root.setRight(node3);
19 node3.setRight(node4);
20 node3.setLeft(node5);
21 binaryTree.setRoot(root);
22
23 //前序遍历
24 //前序遍历的次数 :4
25 System.out.println("前序遍历方式~~~");
26 HeroNode resNode = binaryTree.preOrderSearch(5);
27 if (resNode != null) {
28 System.out.printf("找到了,信息为 no=%d name=%s", resNode.getNo(), resNode.getName());
29 } else {
30 System.out.printf("没有找到 no = %d 的英雄", 5);
31 }
32
33 //中序遍历查找
34 //中序遍历3次
35 System.out.println("中序遍历方式~~~");
36 HeroNode resNode = binaryTree.infixOrderSearch(5);
37 if (resNode != null) {
38 System.out.printf("找到了,信息为 no=%d name=%s", resNode.getNo(), resNode.getName());
39 } else {
40 System.out.printf("没有找到 no = %d 的英雄", 5);
41 }
42
43 //后序遍历查找
44 //后序遍历查找的次数 2次
45 System.out.println("后序遍历方式~~~");
46 HeroNode resNode = binaryTree.postOrderSearch(5);
47 if (resNode != null) {
48 System.out.printf("找到了,信息为 no=%d name=%s", resNode.getNo(), resNode.getName());
49 } else {
50 System.out.printf("没有找到 no = %d 的英雄", 5);
51 }
52 }
53
54 }
55
56 //定义BinaryTree 二叉树
57 class BinaryTree {
58 private HeroNode root;
59
60 public void setRoot(HeroNode root) {
61 this.root = root;
62 }
63 //前序遍历查找
64 public HeroNode preOrderSearch(int no) {
65 if(root != null) {
66 return root.preOrderSearch(no);
67 } else {
68 return null;
69 }
70 }
71 //中序遍历查找
72 public HeroNode infixOrderSearch(int no) {
73 if(root != null) {
74 return root.infixOrderSearch(no);
75 }else {
76 return null;
77 }
78 }
79 //后序遍历查找
80 public HeroNode postOrderSearch(int no) {
81 if(root != null) {
82 return this.root.postOrderSearch(no);
83 }else {
84 return null;
85 }
86 }
87 }
88
89 //先创建HeroNode 结点
90 class HeroNode {
91 private int no;
92 private String name;
93 private HeroNode left; //默认null
94 private HeroNode right; //默认null
95 public HeroNode(int no, String name) {
96 this.no = no;
97 this.name = name;
98 }
99 public int getNo() {
100 return no;
101 }
102 public void setNo(int no) {
103 this.no = no;
104 }
105 public String getName() {
106 return name;
107 }
108 public void setName(String name) {
109 this.name = name;
110 }
111 public HeroNode getLeft() {
112 return left;
113 }
114 public void setLeft(HeroNode left) {
115 this.left = left;
116 }
117 public HeroNode getRight() {
118 return right;
119 }
120 public void setRight(HeroNode right) {
121 this.right = right;
122 }
123 @Override
124 public String toString() {
125 return "HeroNode [no=" + no + ", name=" + name + "]";
126 }
127 //前序遍历查找
128 /**
129 *
130 * @param no 查找no
131 * @return 如果找到就返回该Node ,如果没有找到返回 null
132 */
133 public HeroNode preOrderSearch(int no) {
134 System.out.println("进入前序遍历");
135 //比较当前结点是不是
136 if(this.no == no) {
137 return this;
138 }
139 //1.则判断当前结点的左子节点是否为空,如果不为空,则递归前序查找
140 //2.如果左递归前序查找,找到结点,则返回
141 HeroNode resNode = null;
142 if(this.left != null) {
143 resNode = this.left.preOrderSearch(no);
144 }
145 if(resNode != null) {//说明我们左子树找到
146 return resNode;
147 }
148 //1.左递归前序查找,找到结点,则返回,否继续判断,
149 //2.当前的结点的右子节点是否为空,如果不空,则继续向右递归前序查找
150 if(this.right != null) {
151 resNode = this.right.preOrderSearch(no);
152 }
153 return resNode;
154 }
155
156 //中序遍历查找
157 public HeroNode infixOrderSearch(int no) {
158 //判断当前结点的左子节点是否为空,如果不为空,则递归中序查找
159 HeroNode resNode = null;
160 if(this.left != null) {
161 resNode = this.left.infixOrderSearch(no);
162 }
163 if(resNode != null) {
164 return resNode;
165 }
166 System.out.println("进入中序查找");
167 //如果找到,则返回,如果没有找到,就和当前结点比较,如果是则返回当前结点
168 if(this.no == no) {
169 return this;
170 }
171 //否则继续进行右递归的中序查找
172 if(this.right != null) {
173 resNode = this.right.infixOrderSearch(no);
174 }
175 return resNode;
176
177 }
178
179 //后序遍历查找
180 public HeroNode postOrderSearch(int no) {
181
182 //判断当前结点的左子节点是否为空,如果不为空,则递归后序查找
183 HeroNode resNode = null;
184 if(this.left != null) {
185 resNode = this.left.postOrderSearch(no);
186 }
187 if(resNode != null) {//说明在左子树找到
188 return resNode;
189 }
190
191 //如果左子树没有找到,则向右子树递归进行后序遍历查找
192 if(this.right != null) {
193 resNode = this.right.postOrderSearch(no);
194 }
195 if(resNode != null) {
196 return resNode;
197 }
198 System.out.println("进入后序查找");
199 //如果左右子树都没有找到,就比较当前结点是不是
200 if(this.no == no) {
201 return this;
202 }
203 return resNode;
204 }
205
206 }
代码
1 前序遍历方式~~~
2 进入前序遍历
3 进入前序遍历
4 进入前序遍历
5 进入前序遍历
6 找到了,信息为 no=5 name=关胜中序遍历方式~~~
7 进入中序查找
8 进入中序查找
9 进入中序查找
10 找到了,信息为 no=5 name=关胜后序遍历方式~~~
11 进入后序查找
12 进入后序查找
13 找到了,信息为 no=5 name=关胜
输出
二叉树-删除节点
定义:
- 如果删除的节点是叶子节点,则删除该节点
- 如果删除的节点是非叶子节点,则删除该子树.
思路分析:
实现删除代码:
1 //定义BinaryTree 二叉树
2 class BinaryTree {
3 private HeroNode root;
4
5 public void setRoot(HeroNode root) {
6 this.root = root;
7 }
8
9 //删除结点
10 public void delNode(int no) {
11 if(root != null) {
12 //如果只有一个root结点, 这里立即判断root是不是就是要删除结点
13 if(root.getNo() == no) {
14 root = null;
15 } else {
16 //递归删除
17 root.delNode(no);
18 }
19 }else{
20 System.out.println("空树,不能删除~");
21 }
22 }
23 }
24 class HeroNode {
25 private int no;
26 private String name;
27 private HeroNode left; //默认null
28 private HeroNode right; //默认null
29 public HeroNode(int no, String name) {
30 this.no = no;
31 this.name = name;
32 }
33 public int getNo() {
34 return no;
35 }
36 public void setNo(int no) {
37 this.no = no;
38 }
39 public String getName() {
40 return name;
41 }
42 public void setName(String name) {
43 this.name = name;
44 }
45 public HeroNode getLeft() {
46 return left;
47 }
48 public void setLeft(HeroNode left) {
49 this.left = left;
50 }
51 public HeroNode getRight() {
52 return right;
53 }
54 public void setRight(HeroNode right) {
55 this.right = right;
56 }
57 @Override
58 public String toString() {
59 return "HeroNode [no=" + no + ", name=" + name + "]";
60 }
61 //递归删除结点
62 //1.如果删除的节点是叶子节点,则删除该节点
63 //2.如果删除的节点是非叶子节点,则删除该子树
64 public void delNode(int no) {
65
66 //思路
67 /*
68 * 1. 因为我们的二叉树是单向的,所以我们是判断当前结点的子结点是否需要删除结点,而不能去判断当前这个结点是不是需要删除结点.
69 2. 如果当前结点的左子结点不为空,并且左子结点 就是要删除结点,就将this.left = null; 并且就返回(结束递归删除)
70 3. 如果当前结点的右子结点不为空,并且右子结点 就是要删除结点,就将this.right= null ;并且就返回(结束递归删除)
71 4. 如果第2和第3步没有删除结点,那么我们就需要向左子树进行递归删除
72 5. 如果第4步也没有删除结点,则应当向右子树进行递归删除.
73
74 */
75 //2. 如果当前结点的左子结点不为空,并且左子结点 就是要删除结点,就将this.left = null; 并且就返回(结束递归删除)
76 if(this.left != null && this.left.no == no) {
77 this.left = null;
78 return;
79 }
80 //3.如果当前结点的右子结点不为空,并且右子结点 就是要删除结点,就将this.right= null ;并且就返回(结束递归删除)
81 if(this.right != null && this.right.no == no) {
82 this.right = null;
83 return;
84 }
85 //4.我们就需要向左子树进行递归删除
86 if(this.left != null) {
87 this.left.delNode(no);
88 }
89 //5.则应当向右子树进行递归删除
90 if(this.right != null) {
91 this.right.delNode(no);
92 }
93 }
94 }
代码
测试:
1 public static void main(String[] args) {
2 //先需要创建一颗二叉树
3 BinaryTree binaryTree = new BinaryTree();
4 //创建需要的结点
5 HeroNode root = new HeroNode(1, "宋江");
6 HeroNode node2 = new HeroNode(2, "吴用");
7 HeroNode node3 = new HeroNode(3, "卢俊义");
8 HeroNode node4 = new HeroNode(4, "林冲");
9 HeroNode node5 = new HeroNode(5, "关胜");
10
11 //说明,我们先手动创建该二叉树,后面我们学习递归的方式创建二叉树
12 root.setLeft(node2);
13 root.setRight(node3);
14 node3.setRight(node4);
15 node3.setLeft(node5);
16 binaryTree.setRoot(root);
17 System.out.println("删除前,前序遍历");
18 binaryTree.preOrder(); // 1,2,3,5,4
19 binaryTree.delNode(5);
20 //binaryTree.delNode(3);
21 System.out.println("删除后,前序遍历");
22 binaryTree.preOrder(); // 1,2,3,4
23 }
24 输出:
25 删除前,前序遍历
26 HeroNode [no=1, name=宋江]
27 HeroNode [no=2, name=吴用]
28 HeroNode [no=3, name=卢俊义]
29 HeroNode [no=5, name=关胜]
30 HeroNode [no=4, name=林冲]
31 删除后,前序遍历
32 HeroNode [no=1, name=宋江]
33 HeroNode [no=2, name=吴用]
34 HeroNode [no=3, name=卢俊义]
35 HeroNode [no=4, name=林冲]
36 如果是删除binaryTree.delNode(3);
37 则输出:
38 删除前,前序遍历
39 HeroNode [no=1, name=宋江]
40 HeroNode [no=2, name=吴用]
41 HeroNode [no=3, name=卢俊义]
42 HeroNode [no=5, name=关胜]
43 HeroNode [no=4, name=林冲]
44 删除后,前序遍历
45 HeroNode [no=1, name=宋江]
46 HeroNode [no=2, name=吴用]
代码
拓展:
上面我们定义了两个删除规则,那么我们考虑另外删除规则又怎么实现。‘
如果要删除的节点是非叶子节点,现在我们不希望将该非叶子节点为根节点的子树删除,需要指定规则, 假如规定如下:
- 如果该非叶子节点A只有一个子节点B,则子节点B替代节点A
- 如果该非叶子节点A有左子节点B和右子节点C,则让左子节点B替代节点A。
这个代码实现在后序讲二叉排序树时,在讲解具体的删除方法。
顺序存储二叉树
顺序存储二叉树的概念
基本说明
从数据存储来看,数组存储方式和树 的存储方式可以相互转换,即数组可 以转换成树,树也可以转换成数组, 看示意图。
要求:
- 上图的二叉树的结点,要求以数组的方式来存放 arr : [1, 2, 3, 4, 5, 6, 7]
- 要求在遍历数组 arr时,仍然可以以前序遍历,中序遍历和后序遍历的方式完成结点的遍历
顺序存储二叉树的特点:
- 顺序二叉树通常只考虑完全二叉树
- 第n个元素的左子节点为 2 * n + 1
- 第n个元素的右子节点为 2 * n + 2
- 第n个元素的父节点为 (n-1) / 2
- n : 表示二叉树中的第几个元素
需求: 给你一个数组 {1,2,3,4,5,6,7},要求以二叉树前序遍历的方式进行遍历。 前序遍历的结果应当为 1,2,4,5,3,6,7
1 public class ArrBinaryTreeDemo {
2
3 public static void main(String[] args) {
4 int[] arr = { 1, 2, 3, 4, 5, 6, 7 };
5 //创建一个 ArrBinaryTree
6 ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
7 arrBinaryTree.preOrder(); // 1,2,4,5,3,6,7
8 }
9
10 }
11
12 //编写一个ArrayBinaryTree, 实现顺序存储二叉树遍历
13
14 class ArrBinaryTree {
15 private int[] arr;//存储数据结点的数组
16
17 public ArrBinaryTree(int[] arr) {
18 this.arr = arr;
19 }
20
21 //重载preOrder
22 public void preOrder() {
23 this.preOrder(0);
24 }
25
26 //编写一个方法,完成顺序存储二叉树的前序遍历
27 /**
28 *
29 * @param index 数组的下标
30 */
31 public void preOrder(int index) {
32 //如果数组为空,或者 arr.length = 0
33 if(arr == null || arr.length == 0) {
34 System.out.println("数组为空,不能按照二叉树的前序遍历");
35 }
36 //输出当前这个元素
37 System.out.println(arr[index]);
38 //向左递归遍历
39 if((index * 2 + 1) < arr.length) {
40 preOrder(2 * index + 1 );
41 }
42 //向右递归遍历
43 if((index * 2 + 2) < arr.length) {
44 preOrder(2 * index + 2);
45 }
46 }
47
48 }
代码
顺序存储二叉树应用实例
八大排序算法中的堆排序,就会使用到顺序存储二叉树, 关于堆排序后序在讲。
posted on 2019-07-10 23:37 wanbf 阅读(...) 评论(...) 编辑 收藏