2023年6月22日发(作者：)
一、数据结构分类
（一）按逻辑结构
1. 集合(无辑关系)
2. 线性结构(线性表)：数组、链表、栈、队列
3. 非线性结构：树、图、多维数组
（二）按存储结构
顺序（数组）储结构、链式储结构、索引储结构、散列储结构
二、二叉树相关性质
结点的度：一个结点的子树的个数记为该结点的度．
树的度：所有节点中度数最大的结节的度数，叶子节点的度为零。
树的高度：一棵树的最大层次数记为树的高度(或深度)。
有序(无序)树：若将树中结点的各子树看成是从左到右具有次序的，即不能交换，则称该树为有序树。否则称为无序树。
二叉树第i层（i≥1）上至多有2^(i-1)个节点。
深度为k的二叉树至多有2^k-1个节点（k≥1）。
对任何一棵二叉，若叶子节点数为n0，度为2的节点数为n2，则n0=n2+1。
具有n个节点的完全二叉树的深度为 (㏒2^n)(向下取整)+1。
对一棵有n个节点的完全二叉树的节点按层次从上到下，自左至右进行编号，则对任一节点i(1≤i≤n)有：若 i=1，则节点i是二叉树的根，无双亲；若 i>1，则其双亲为 i/2(向下取整)。若2i>n，则节点i没有孩子节点，否则其左孩子为2i。若2i+1>n，则节点i没有右孩子，否则其右孩子为2i+1。
若深度为k的二叉树有2^k-1个节点，则称其为满二叉树。满二叉树是一棵完全二叉树。
对于完全二叉树中，度为1的节点个数只可能为1个或0个。 对于二叉树，如果叶子节点数为n0，度为1的节点数为n1，度为2的节点数为n2，则节点总数n = n0 + n1 + n2。
对于任意树，总节点数 = 每个节点度数和 + 1
二叉树的高度等于根与最远叶节点（具有最多祖先的节点）之间分支数目。空树的高度是-1。只有单个元素的二叉树，其高度为0。
.
三、二叉树的遍历
遍历是按某种策略访问树中的每个节点，且仅访问一次。
（一） 二叉树结构实现
Java代码
1. package e;
2. /**
3. * 创建 非完全二叉树、完全二叉树、满二叉树
4. *
5. * 由于二叉树的节点增加没有什么规则，所以这里只是简单的使用了递一
6. * 次性把整棵树创建出来，而没有设计出一个一个添加节点的方法与删除
7. *
8. * @author jzj
9. * @date 2009-12-23
10. */
class BinTree {// Bin=Binary(二进位的, 二元的)
12.
13. protected Entry root;//根
14. private int size;//树的节点数
15.
16. /**
17. * 树的节点结构
18. * @author jzj
19. * @date 2009-12-23
20. */ 21. protected static class Entry {
22. int elem;//数据域，这里我们作为编号
23. Entry left;//左子树
24. Entry right;//右子树
25.
26. public Entry(int elem) {
27. = elem;
28. }
29.
30. public String toString() {
31. return " number=" + elem;
32. }
33. }
34.
35. /**
36. * 根据给定的节点数创建一个完全二叉树或是满二叉树
37. * @param nodeCount 要创建节点总数
38. */
39. public void createFullBiTree(int nodeCount) {
40. root = recurCreateFullBiTree(1, nodeCount);
41. }
42.
43. /**
44. * 递归创建完全二叉树
45. * @param num 节点编号
46. * @param nodeCount 节点总数
47. * @return TreeNode 返回创建的节点
48. */
49. private Entry recurCreateFullBiTree(int num, int nodeCount) {
50. size++;
51. Entry rootNode = new Entry(num);//根节点
52. //如果有左子树则创建左子树
53. if (num * 2 <= nodeCount) {
54. = recurCreateFullBiTree(num * 2, nodeCount);
55. //如果还可以创建右子树，则创建
56. if (num * 2 + 1 <= nodeCount) {
57. = recurCreateFullBiTree(num * 2
+ 1, nodeCount);
58. }
59. }
60. return (Entry) rootNode;
61. } 62.
63. /**
64. * 根据给定的数组创建一棵树，这个棵树可以是完全二叉树也可是普通二叉树
65. * 数组中为0的表示不创建该位置上的节点
66. * @param nums 数组中指定了要创建的节点的编号，如果为0，表示不创建
67. */
68. public void createBinTree(int[] nums) {
69. root = recurCreateBinTree(nums, 0);
70. }
71.
72. /**
73. * 递归创建二叉树
74. * @param nums 数组中指定了要创建的节点的编号，如果为0，表示不创建
75. * @param index 需要使用数组中的哪个元素创建节点，如果为元素为0，则不创建
76. * @return TreeNode 返回创建的节点，最终会返回树的根节点
77. */
78. private Entry recurCreateBinTree(int[] nums, int index) {
79. //指定索引上的编号不为零上才需创建节点
80. if (nums[index] != 0) {
81. size++;
82. Entry rootNode = new Entry(nums[index]);//根节点
83. //如果有左子树则创建左子树
84. if ((index + 1) * 2 <= ) {
85. = (Entry) recurCreateBinTree(nums, (index + 1) * 2 - 1);
86. //如果还可以创建右子树，则创建
87. if ((index + 1) * 2 + 1 <= ) {
88. = (Entry) recurCreateBinTree(nums, (index + 1) * 2);
89. }
90. }
91. return (Entry) rootNode;
92. }
93. return null;
94.
95. }
96.
97. public int size() {
98. return size; 99. }
100.
101. //取树的最左边的节点
102. public int getLast() {
103. Entry e = root;
104. while ( != null) {
105. e = ;
106. }
107. return ;
108. }
109.
110. //测试
111. public static void main(String[] args) {
112.
113. //创建一个满二叉树
114. BinTree binTree = new BinTree();
115. FullBiTree(15);
116. n(());//15
117. n(t());//15
118.
119. //创建一个完全二叉树
120. binTree = new BinTree();
121. FullBiTree(14);
122. n(());//14
123. n(t());//7
124.
125. //创建一棵非完全二叉树
126. binTree = new BinTree();
127. int[] nums = new int[] { 1, 2, 3, 4, 0, 0, 5, 0, 6, 0, 0, 0, 0, 7, 8 };
128. BinTree(nums);
129. n(());//8
130. n(t());//8
131.
132. }
133. }
（二）利用二叉树本身特点进行递归遍历（属内部遍历）
由于二叉树所具有的递归性质，一棵非空的二叉树可以看作是由根节点、左子树和右子树3部分构成，因为若能依次遍历这3部分的信息，也就遍历了整个二叉树。按照左子树的遍历在右子树的遍历之前进行的约定，根据访问根节点位置的不同，可以得到二叉的前序、中序、后序3种遍历方法。
Java代码
1. package e;
2.
3. /**
4. * 二叉树的三种 内部 遍历：前序、中序、后序
5. * 但不管是哪种方式，左子树的遍历在右子树的遍历之前遍历是这有三种遍历方式都
6. * 必须遵循的约定
7. * @author jzj
8. * @date 2009-12-23
9. */
class BinTreeInOrder extends BinTree {
11.
12. /**
13. * 节点访问者，可根据需要重写visit方法
14. */
15. static abstract class Visitor {
16. void visit(Object ele) {
17. (ele + " ");
18. }
19. }
20.
21. public void preOrder(Visitor v) {
22. preOrder(v, root);
23. }
24.
25. /**
26. * 树的前序递归遍历 pre=prefix(前缀)
27. * @param node 要遍历的节点
28. */
29. private void preOrder(Visitor v, Entry node) {
30. //如果传进来的节点不为空，则遍历，注，叶子节点的子节点为null
31. if (node != null) {
32. ();//先遍历父节点
33. preOrder(v, );//再遍历左节点
34. preOrder(v, );//最后遍历右节点
35. }
36. }
37. 38. public void inOrder(Visitor v) {
39. inOrder(v, root);
40. }
41.
42. /**
43. * 树的中序递归遍历 in=infix(中缀)
44. * @param node 要遍历的节点
45. */
46. private void inOrder(Visitor v, Entry node) {
47. //如果传进来的节点不为空，则遍历，注，叶子节点的子节点为null
48. if (node != null) {
49. inOrder(v, );//先遍历左节点
50. ();//再遍历父节点
51. inOrder(v, );//最后遍历右节点
52. }
53. }
54.
55. public void postOrder(Visitor v) {
56. postOrder(v, root);
57. }
58.
59. /**
60. * 树的后序递归遍历 post=postfix(后缀)
61. * @param node 要遍历的节点
62. */
63. private void postOrder(Visitor v, Entry node) {
64. //如果传进来的节点不为空，则遍历，注，叶子节点的子节点为null
65. if (node != null) {
66. postOrder(v, );//先遍历左节点
67. postOrder(v, );//再遍历右节点
68. ();//最后遍历父节点
69. }
70. }
71.
72. //测试
73. public static void main(String[] args) {
74.
75. //创建二叉树
76. int[] nums = new int[] { 1, 2, 3, 4, 0, 0, 5, 0, 6, 0,
0, 0, 0, 7, 8 };
77. BinTreeInOrder treeOrder = new BinTreeInOrder();
78. BinTree(nums); 79. ("前序遍历 - ");
80. er(new Visitor() {
81. });
82. n();
83. ("中序遍历 - ");
84. r(new Visitor() {
85. });
86. n();
87. ("后序遍历 - ");
88. der(new Visitor() {
89. });
90. /*
91. * output:
92. * 前序遍历 - 1 2 4 6 3 5 7 8
93. * 中序遍历 - 4 6 2 1 3 7 5 8
94. * 后序遍历 - 6 4 2 7 8 5 3 1
95. */
96. }
97.}
（三）二叉树的非递归遍历（属外部遍历）
1、利用栈与队列对二叉树进行非递归遍历
Java代码
1. package e;
2.
3. import or;
4. import List;
5. import ;
6.
7. /**
8. * 二叉树的外部遍历：深度优先（先根）、广度（层次）优先遍历
9. *
10. * @author jzj
11. * @date 2009-12-23
12. */
class BinTreeOutOrder extends BinTree {
14.
15. /**
16. * 二叉树深序优先遍历（即二叉树的先根遍历）迭代器，外部可以使用该迭代器 17. * 进行非递归的遍历，这是一种在二叉树结构外部的一种遍历算法，它没有使用
18. * 二叉树本身的结构特点（左右子树递归）进行递归遍历
19. * @author jzj
20. */
21. private class DepthOrderIterator implements Iterator {
22. //栈里存放的是每个节点
23. private Stack stack = new Stack();
24.
25. public DepthOrderIterator(Entry node) {
26.
27. //根入栈，但在放入左右子节点前会马上出栈，即根先优于左右子节点访问
28. (node);
29.
30. }
31.
32. //是否还有下一个元素
33. public boolean hasNext() {
34. if (y()) {
35. return false;
36. }
37. return true;
38. }
39.
40. //取下一个元素
41. public Entry next() {
42. if (hasNext()) {
43. //取栈顶元素
44. Entry treeNode = (Entry) ();//先访问根
45.
46. if ( != null) {
47. ();//再放入右子节点
48. }
49.
50. if ( != null) {
51. ();//最后放入左子节点，但访问先于右节点
52. }
53.
54. // 返回遍历得到的节点
55. return treeNode; 56.
57. } else {
58. // 如果栈为空
59. return null;
60. }
61. }
62.
63. public void remove() {
64. throw new UnsupportedOperationException();
65. }
66.
67. }
68.
69. /**
70. * 向外界提供先根遍历迭代器
71. * @return Iterator 返回先根遍历迭代器
72. */
73. public Iterator createPreOrderItr() {
74. return new DepthOrderIterator(root);
75. }
76.
77. /**
78. * 二叉树广度优先遍历迭代器，外部可以使用该迭代器
79. * 进行非递归的遍历，这是一种在二叉树结构外部的一种遍历算法，它没有使用
80. * 二叉树本身的结构特点（左右子树递归）进行递归遍历
81. * @author jzj
82. */
83. private class LevelOrderIterator implements Iterator {
84. //使用队列结构实现层次遍历，队列里存储的为节点
85. private LinkedList queue = new LinkedList();
86.
87. public LevelOrderIterator(Entry node) {
88.
89. if (node != null) {
90. //将根入队
91. t(node);
92. }
93. }
94.
95. //是否还有下一个元素
96. public boolean hasNext() {
97. if (y()) {
98. return false; 99. }
100. return true;
101. }
102.
103. //取下一个元素
104. public Entry next() {
105. if (hasNext()) {
106. //取栈顶迭元素
107. Entry treeNode = (Entry) First();
108.
109. if ( != null) {//如果有左子树，加入有序列表中
110. t();
111. }
112. if ( != null) {//如果有右子树，加入有序列表中
113. t();
114. }
115.
116. // 返回遍历得到的节点
117. return treeNode;
118.
119. } else {
120. // 如果队列为空
121. return null;
122. }
123. }
124.
125. public void remove() {
126. throw new UnsupportedOperationException();
127. }
128.
129. }
130.
131. /**
132. * 向外界提供广度优先迭代器
133. * @return Iterator 返回遍历迭代器
134. */
135. public Iterator createLayerOrderItr() {
136. return new LevelOrderIterator(root);
137. }
138.
139. public static void main(String[] args) { 140. //创建一棵满二叉树
141. BinTreeOutOrder treeOrder = new BinTreeOutOrder();
142. FullBiTree(15);
143. Iterator preOrderItr = PreOrderItr();
144. ("深度优先（先根）遍历 - ");
145. while (t()) {
146. (((Entry) ()).elem + " ");
147. }
148. n();
149. ("广度优先（层次）遍历 - ");
150. Iterator layerOrderItr = LayerOrderItr();
151. while (t()) {
152. (((Entry) ()).elem + " ");
153. }
154. /*
155. * output:
156. * 深度优先（先根）遍历 - 1 2 4 8 9 5 10 11 3 6 12 13 7 14 15
157. * 广度优先（层次）遍历 - 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
158. */
159. }
160. }
2、利用二叉树节点的父节点指针进行非递归遍历
要想采用非递归的方法遍历树，又不借助于前面的队列与栈，我们需要该树是一棵可回溯的二叉树，即从子节点要能够知道他的父节点及祖先节点，与前面的二叉树不同的是，树的节点结构体中多一个指向父的节点指针，这样外界可以以非递归的方式来遍历二叉树了 。
Java代码
1. package e;
2.
3. /**
4. *
5. * 可回溯的二叉树
6. * 二叉树的非递归遍历 7. *
8. * @author jzj
9. * @date 2009-12-23
10. */
class BackBinTree {// Bin=Binary(二进位的, 二元的)
12.
13. protected Entry root;//根
14. private int size;//树的节点数
15.
16. /**
17. * 树的节点结构
18. * @author jzj
19. * @date 2009-12-23
20. */
21. private static class Entry {
22. int elem;//数据域，这里为了测试，就作为节点编号吧
23. Entry paraent;//父节点
24. Entry left;//左节点
25. Entry right;//右节点
26.
27. //构造函数只有两个参数，左右节点是调用add方法时设置
28. public Entry(int elem, Entry parent) {
29. = elem;
30. t = parent;
31. }
32. }
33.
34. /**
35. * 查找前序遍历（根左右）直接后继节点
36. *
37. * 以非递归 根左右 的方式遍历树
38. *
39. * @param e 需要查找哪个节点的直接后继节点
40. * @return Entry 前序遍历直接后继节点
41. */
42. public Entry preOrderSuccessor(Entry e) {
43. if (e == null) {
44. return null;
45. }//如果左子树不为空，则直接后继为左子节点
46. else if ( != null) {//先看左子节点是否为空
47. return ;//如果不为空，则直接后继为左子节点
48. }//否则如果右子树不为空，则直接后继为右子节点
49. else if ( != null) {//如果左子节点为空，则看右子节点是否为空 50. return ;//如果右子节点不为空，则返回
51. }//左右子节点都为空的情况下
52. else {
53. Entry s = t;
54. Entry c = e;
55.
56. /*
57. * 一直向上，直到c是s的左子树，且s的右子树不为空。请试着找一下36与68节点的
58. * 直接后继节点，36的应该是75，而68则没有后继节点了
59. *
60. * 50
61. * /
62. * 37 75
63. * / /
64. * 25 61
65. * / /
66. * 15 30 55 68
67. * /
68. * 28 32 59
69. *
70. * 36
71. */
72. while (s != null && (c == || == null)) {
73. c = s;
74. s = t;
75. }
76. //退出循环时 s 可以为null，比如查找 68 节点的直接后继时退出循环时s=null
77. if (s == null) {
78. return null;
79. } else {
80. return ;
81. }
82. }
83. }
84.
85. /**
86. * 查找前序遍历（根左右）直接前驱节点
87. *
88. * 以非递归 右左根 的方式遍历树
89. *
90. * @param e 需要查找哪个节点的直接前驱节点 91. * @return Entry 前序遍历直接前驱节点
92. */
93. public Entry preOrderAncestor(Entry e) {
94. if (e == null) {
95. return null;
96. }//如果节点为父节点的左节点，则父节点就是直接前驱节点
97. else if (t != null && e == ) {
98. return t;
99. }//如果节点为父节点的右节点
100. else if (t != null && e == ) {
101.
102. Entry s = t;//前驱节点默认为父节点
103. if ( != null) {//如果父节点没有左子，前驱节点就为父节点
104. s = ;//如果父节点的左子节点不空，则初始为父节点左子节点
105.
106. /*
107. * 只要父节点左子节点还有子节点，则前驱节点要从其子树中找。请试着找
108. * 一下75直接前驱节点，应该是36
109. *
110. * 50
111. * /
112. * 37 75
113. * / /
114. * 25 61
115. * / /
116. * 15 30 55 68
117. * /
118. * 28 32 59
119. *
120. * 36
121. */
122. while ( != null || != null)
{
123. //在父节点的左子节点的子树中查找时，一定要先向右边拐
124. if ( != null) {
125. s = ;
126. } else {//如果右边没有，然后才能向左边拐
127. s = ; 128. }
129. }
130. }
131. return s;
132. } else {//如果是根节点，则没有直接前驱节点了
133. return null;
134. }
135. }
136.
137. /**
138. * 查找后序遍历（左右根）直接后继节点
139. *
140. * 以非递归 左右根 的方式遍历树
141. *
142. * @param e 需要查找哪个节点的直接后继节点
143. * @return Entry 后序遍历直接后继节点
144. */
145. public Entry postOrderSuccessor(Entry e) {
146. if (e == null) {
147. return null;
148. }//如果节点为父节点的右子节点，则父节点就是直接后继节点
149. else if (t != null && e == ) {
150. return t;
151. }//如果节点为父节点的左子节点
152. else if (t != null && e == ) {
153. Entry s = t;//后继节点默认为父节点
154. if ( != null) {//如果父节点没有右子，后继节点就为父节点
155. s = ;//如果父节点的右子节点不空，则初始为父节点右子节点
156. /*
157. * 只要父节点右子节点还有子节点，则后断节点要从其子树中找，
158. * 如15的后继节点为28
159. * 50
160. * /
161. * 37 75
162. * / /
163. * 25 61
164. * / /
165. * 15 30 55 68 166. * /
167. * 28 32 59
168. *
169. * 36
170. */
171.
172. while ( != null || != null)
{
173. //在父节点的右子节点的子树中查找时，一定要先向左边拐
174. if ( != null) {
175. s = ;
176. } else {//如果左边没有，然后才能向右边拐
177. s = ;
178. }
179. }
180. }
181. return s;
182. } else {
183. //如果是根节点，则没有后继节点了
184. return null;
185. }
186. }
187.
188. /**
189. * 查找后序遍历（左右根）直接前驱节点
190. *
191. * 以非递归 根右左 的方式遍历树
192. *
193. * @param e 需要查找哪个节点的直接前驱节点
194. * @return Entry 后序遍历直接前驱节点
195. */
196. public Entry postOrderAncestor(Entry e) {
197.
198. if (e == null) {
199. return null;
200. }//如果右子树不为空，则直接前驱为右子节点
201. else if ( != null) {//先看右子节点是否为空
202. return ;//如果不为空，则直接后继为右子节点
203. }//否则如果左子树不为空，则直接前驱为左子节点
204. else if ( != null) { 205. return ;
206. }//左右子节点都为空的情况下
207. else {
208. Entry s = t;
209. Entry c = e;
210.
211. /*
212. * 一直向上，直到c是s的右子树，且s的左子树不为空。请试着找一下59与15节点的
213. * 直接后继节点，59的应该是37，而15则没有后继节点了
214. *
215. * 50
216. * /
217. * 37 75
218. * / /
219. * 25 61
220. * / /
221. * 15 30 55 68
222. * /
223. * 28 32 59
224. *
225. * 36
226. */
227. while (s != null && (c == || ==
null)) {
228. c = s;
229. s = t;
230. }
231. if (s == null) {
232. return null;
233. } else {
234. return ;
235. }
236. }
237. }
238.
239. /**
240. * 查找中序遍历（左根右）直接后继节点
241. *
242. * 以非递归 左根右 的方式遍历树
243. *
244. * @param e 需要查找哪个节点的直接后继节点
245. * @return Entry 中序遍历直接后继节点 246. */
247. public Entry inOrderSuccessor(Entry e) {
248. if (e == null) {
249. return null;
250. }//如果待找的节点有右子树，则在右子树上查找
251. else if ( != null) {
252. //默认后继节点为右子节点（如果右子节点没有左子树时即为该节点）
253. Entry p = ;
254. while ( != null) {
255. //注，如果右子节点的左子树不为空，则在左子树中查找，且后面找时要一直向左拐
256. p = ;
257. }
258. return p;
259. }//如果待查节点没有右子树，则要在祖宗节点中查找后继节点
260. else {
261. //默认后继节点为父节点（如果待查节点为父节点的左子树，则后继为父节点）
262. Entry p = t;
263. Entry current = e;//当前节点，如果其父不为后继，则下次指向父节点
264. //如果待查节点为父节点的右节点时，继续向上找，一直要找到current为左子节点，则s才是后继
265. while (p != null && current == ) {
266. current = p;
267. p = t;
268. }
269. return p;
270. }
271. }
272.
273. /**
274. * 查找中序遍历（左根右）直接前驱节点
275. *
276. * 以非递归 右根左 的方式遍历树
277. *
278. * @param e 需要查找哪个节点的直接前驱节点
279. * @return Entry 中序遍历直接前驱节点
280. */
281. public Entry inOrderAncestor(Entry e) {
282. if (e == null) {
283. return null; 284. }//如果待找的节点有左子树，则在在子树上查找
285. else if ( != null) {
286. //默认直接前驱节点为左子节点（如果左子节点没有右子树时即为该节点）
287. Entry p = ;
288. while ( != null) {
289. //注，如果左子节点的右子树不为空，则在右子树中查找，且后面找时要一直向右拐
290. p = ;
291. }
292. return p;
293. }//如果待查节点没有左子树，则要在祖宗节点中查找前驱节点
294. else {
295. //默认前驱节点为父节点（如果待查节点为父节点的右子树，则前驱为父节点）
296. Entry p = t;
297. Entry current = e;//当前节点，如果其父不为前驱，则下次指向父节点
298. //如果待查节点为父节点的左节点时，继续向上找，一直要找到current为p的右子节点，则s才是前驱
299. while (p != null && current == ) {
300. current = p;
301. p = t;
302. }
303. return p;
304. }
305. }
306.
307. /**
308. * 查找指定的节点
309. * @param num
310. * @return Entry
311. */
312. public Entry getEntry(int num) {
313. return getEntry(root, num);
314. }
315.
316. /**
317. * 使用树的先序遍历递归方式查找指定的节点
318. *
319. * @param entry
320. * @param num
321. * @return 322. */
323. private Entry getEntry(Entry entry, int num) {
324.
325. //如果找到，则停止后续搜索，并把查找到的节点返回给上层调用者
326. if ( == num) {//1、先与父节点比对
327. return entry;
328. }
329.
330. Entry tmp = null;
331.
332. if ( != null) {//2、再在左子树上找
333. tmp = getEntry(, num);
334. //如果左子树上找到，返回并停止查找，否则继续在后续节点中找
335. if (tmp != null) {
336. //节点在左子树中找到，返回给上层调用者
337. return tmp;
338. }
339. }
340.
341. if ( != null) {//3、否则在右子树上找
342. tmp = getEntry(, num);
343. //如果右子树上找到，返回并停止查找，否则继续在后续节点中找
344. if (tmp != null) {
345. //节点在右子树中找到，返回给上层调用者
346. return tmp;
347. }
348. }
349.
350. //当前比较节点 entry 子树为空或不为空时没有找到，直接返回给上层调用者null
351. return null;
352. }
353.
354. /**
355. * 根据给定的数组创建一棵树，这个棵树可以是完全二叉树也可是普通二叉树
356. * 数组中为0的表示不创建该位置上的节点
357. * @param nums 数组中指定了要创建的节点的编号，如果为0，表示不创建
358. */
359. public void createBinTree(int[] nums) { 360. root = recurCreateBinTree(nums, null, 0);
361. }
362.
363. /**
364. * 递归创建二叉树
365. * @param nums 数组中指定了要创建的节点的编号，如果为0，表示不创建
366. * @param paraent 父节点
367. * @param index 需要使用数组中的哪个元素创建节点，如果为元素为0，则不创建
368. * @return Entry 返回创建的节点，最终会返回树的根节点
369. */
370. private Entry recurCreateBinTree(int[] nums, Entry pararent, int index) {
371. //指定索引上的编号不为零上才需创建节点
372. if (nums[index] != 0) {
373. size++;
374. Entry root = new Entry(nums[index], pararent);//根节点
375. //如果有左子树则创建左子树
376. if ((index + 1) * 2 <= ) {
377. = (Entry) recurCreateBinTree(nums, root, (index + 1) * 2 - 1);
378. //如果还可以创建右子树，则创建
379. if ((index + 1) * 2 + 1 <= ) {
380. = (Entry) recurCreateBinTree(nums, root, (index + 1) * 2);
381. }
382. }
383. return (Entry) root;
384. }
385. return null;
386.
387. }
388.
389. public int size() {
390. return size;
391. }
392.
393. //测试
394. public static void main(String[] args) {
395.
396. //创建一棵非完全二叉树 397. BackBinTree binTree = new BackBinTree();
398. /*
399. * 50
400. * /
401. * 37 75
402. * / /
403. * 25 61
404. * / /
405. * 15 30 55 68
406. * /
407. * 28 32 59
408. *
409. * 36
410. */
411. int[] nums = new int[] {
15, 30,
412.
0, 0, 0,
413. BinTree(nums);
414.
415. Entry entry = ry(416. ("417. while (entry != null) {
418. ( + " ");
419. entry = erSuccessor(entry);
420. }
421. n();
422. entry = ry(423. ("424. while (entry != null) {
425. ( + " ");
426. entry = erAncestor(entry);
427. }
428. n();
429. entry = ry(430. ("431. while (entry != null) {
432. ( + " ");
433. entry = derSuccessor(entry);
434. }
435. n();
436.
437. entry = ry(438. ("50, 37, 75, 25, 0, 61, 0,0, 0, 55, 68, 0, 0, 0,
0, 28, 32, 0, 0, 0, 0, 0, 59, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 36 };
50);
根左右（先序遍历）- ");
68);
右左根（先序的逆）- ");
15);
左右根（后序遍历）- ");
50);
根右左（后序的逆）- "); 439. while (entry != null) {
440. ( + " ");
441. entry = derAncestor(entry);
442. }
443. n();
444.
445. entry = ry(15);
446. ("左根右（中序遍历）- ");
447. while (entry != null) {
448. ( + " ");
449. entry = rSuccessor(entry);
450. }
451. n();
452.
453. entry = ry(75);
454. ("右根左（中序的逆）- ");
455. while (entry != null) {
456. ( + " ");
457. entry = rAncestor(entry);
458. }
459. n();
460. /*
461. * output:
462. * 根左右（先序遍历）- 50 37 25 15 30 28 32 36 75 61 55 59 68
463. * 右左根（先序的逆）- 68 59 55 61 75 36 32 28 30 15 25 37 50
464. * 左右根（后序遍历）- 15 28 36 32 30 25 37 59 55 68 61 75 50
465. * 根右左（后序的逆）- 50 75 61 68 55 59 37 25 30 32 36 28 15
466. * 左根右（中序遍历）- 15 25 28 30 32 36 37 50 55 59 61 68 75
467. * 右根左（中序的逆）- 75 68 61 59 55 50 37 36 32 30 28 25 15
468. */
469. }
470. }
大小: 1.4 KB
大小: 12.3 KB
package e;
/**
* 创建 非完全二叉树、完全二叉树、满二叉树
*
* 由于二叉树的节点增加没有什么规则，所以这里只是简单的使用了递一 * 次性把整棵树创建出来，而没有设计出一个一个添加节点的方法与删除
*
* @author jzj
* @date 2009-12-23
*/
public class BinTree {// Bin=Binary(二进位的, 二元的)
protected Entry root;//根
private int size;//树的节点数
/**
* 树的节点结构
* @author jzj
* @date 2009-12-23
*/
protected static class Entry {
int elem;//数据域，这里我们作为编号
Entry left;//左子树
Entry right;//右子树
public Entry(int elem) {
= elem;
}
public String toString() {
return " number=" + elem;
}
}
/**
* 根据给定的节点数创建一个完全二叉树或是满二叉树
* @param nodeCount 要创建节点总数
*/
public void createFullBiTree(int nodeCount) {
root = recurCreateFullBiTree(1, nodeCount);
}
/**
* 递归创建完全二叉树
* @param num 节点编号
* @param nodeCount 节点总数
* @return TreeNode 返回创建的节点
*/
private Entry recurCreateFullBiTree(int num, int nodeCount) {
}
size++;
Entry rootNode = new Entry(num);//根节点
//如果有左子树则创建左子树
if (num * 2 <= nodeCount) {
= recurCreateFullBiTree(num * 2, nodeCount);
//如果还可以创建右子树，则创建
if (num * 2 + 1 <= nodeCount) {
= recurCreateFullBiTree(num * 2 + 1, nodeCount);
}
}
return (Entry) rootNode;
/**
* 根据给定的数组创建一棵树，这个棵树可以是完全二叉树也可是普通二叉树
* 数组中为0的表示不创建该位置上的节点
* @param nums 数组中指定了要创建的节点的编号，如果为0，表示不创建
*/
public void createBinTree(int[] nums) {
root = recurCreateBinTree(nums, 0);
}
/**
* 递归创建二叉树
* @param nums 数组中指定了要创建的节点的编号，如果为0，表示不创建
* @param index 需要使用数组中的哪个元素创建节点，如果为元素为0，则不创建
* @return TreeNode 返回创建的节点，最终会返回树的根节点
*/
private Entry recurCreateBinTree(int[] nums, int index) {
//指定索引上的编号不为零上才需创建节点
if (nums[index] != 0) {
size++;
Entry rootNode = new Entry(nums[index]);//根节点
//如果有左子树则创建左子树
if ((index + 1) * 2 <= ) {
= (Entry) recurCreateBinTree(nums, (index + 1) * 2 - 1);
//如果还可以创建右子树，则创建
if ((index + 1) * 2 + 1 <= ) {
= (Entry) recurCreateBinTree(nums, (index + 1) * 2);
}
}
return (Entry) rootNode;
}
return null; }
public int size() {
return size;
}
//取树的最左边的节点
public int getLast() {
Entry e = root;
while ( != null) {
e = ;
}
return ;
}
//测试
public static void main(String[] args) {
//创建一个满二叉树
BinTree binTree = new BinTree();
FullBiTree(15);
n(());//15
n(t());//15
//创建一个完全二叉树
binTree = new BinTree();
FullBiTree(14);
n(());//14
n(t());//7
//创建一棵非完全二叉树
binTree = new BinTree();
int[] nums = new int[] { 1, 2, 3, 4, 0, 0, 5, 0, 6, 0, 0, 0, 0, 7, 8 };
BinTree(nums);
n(());//8
n(t());//8
}
}
package e;
/**
* 二叉树的三种 内部 遍历：前序、中序、后序
* 但不管是哪种方式，左子树的遍历在右子树的遍历之前遍历是这有三种遍历方式都
* 必须遵循的约定
* @author jzj
* @date 2009-12-23
*/
public class BinTreeInOrder extends BinTree {
/**
* 节点访问者，可根据需要重写visit方法
*/
static abstract class Visitor {
void visit(Object ele) {
(ele + " ");
}
}
public void preOrder(Visitor v) {
preOrder(v, root);
}
/**
* 树的前序递归遍历 pre=prefix(前缀)
* @param node 要遍历的节点
*/
private void preOrder(Visitor v, Entry node) {
//如果传进来的节点不为空，则遍历，注，叶子节点的子节点为null
if (node != null) {
();//先遍历父节点
preOrder(v, );//再遍历左节点
preOrder(v, );//最后遍历右节点
}
}
public void inOrder(Visitor v) {
inOrder(v, root);
}
/**
* 树的中序递归遍历 in=infix(中缀)
* @param node 要遍历的节点
*/
private void inOrder(Visitor v, Entry node) {
//如果传进来的节点不为空，则遍历，注，叶子节点的子节点为null
if (node != null) {
inOrder(v, );//先遍历左节点
();//再遍历父节点
inOrder(v, );//最后遍历右节点
}
}
public void postOrder(Visitor v) {
postOrder(v, root);
}
/**
* 树的后序递归遍历 post=postfix(后缀)
* @param node 要遍历的节点
*/
private void postOrder(Visitor v, Entry node) {
//如果传进来的节点不为空，则遍历，注，叶子节点的子节点为null
if (node != null) {
postOrder(v, );//先遍历左节点
postOrder(v, );//再遍历右节点
();//最后遍历父节点
}
} //测试
public static void main(String[] args) {
//创建二叉树
int[] nums = new int[] { 1, 2, 3, 4, 0, 0, 5, 0, 6, 0, 0, 0, 0, 7, 8 };
BinTreeInOrder treeOrder = new BinTreeInOrder();
BinTree(nums);
("前序遍历 - ");
er(new Visitor() {
});
n();
("中序遍历 - ");
r(new Visitor() {
});
n();
("后序遍历 - ");
der(new Visitor() {
});
/*
* output:
* 前序遍历 - 1 2 4 6 3 5 7 8
* 中序遍历 - 4 6 2 1 3 7 5 8
* 后序遍历 - 6 4 2 7 8 5 3 1
*/
}
}
package e;
import or;
import List;
import ;
/**
* 二叉树的外部遍历：深度优先（先根）、广度（层次）优先遍历
*
* @author jzj
* @date 2009-12-23
*/
public class BinTreeOutOrder extends BinTree {
/**
* 二叉树深序优先遍历（即二叉树的先根遍历）迭代器，外部可以使用该迭代器
* 进行非递归的遍历，这是一种在二叉树结构外部的一种遍历算法，它没有使用
* 二叉树本身的结构特点（左右子树递归）进行递归遍历
* @author jzj
*/
private class DepthOrderIterator implements Iterator {
//栈里存放的是每个节点
private Stack stack = new Stack();
public DepthOrderIterator(Entry node) {
//根入栈，但在放入左右子节点前会马上出栈，即根先优于左右子节点访问
(node);
}
//是否还有下一个元素
public boolean hasNext() {
if (y()) {
return false;
}
return true;
}
//取下一个元素
public Entry next() {
if (hasNext()) {
//取栈顶元素
Entry treeNode = (Entry) ();//先访问根
if ( != null) {
();//再放入右子节点
}
if ( != null) {
}
}
}
();//最后放入左子节点，但访问先于右节点
// 返回遍历得到的节点
return treeNode;
} else {
// 如果栈为空
return null;
}
public void remove() {
throw new UnsupportedOperationException();
}
/**
* 向外界提供先根遍历迭代器
* @return Iterator 返回先根遍历迭代器
*/
public Iterator createPreOrderItr() {
return new DepthOrderIterator(root);
}
/**
* 二叉树广度优先遍历迭代器，外部可以使用该迭代器
* 进行非递归的遍历，这是一种在二叉树结构外部的一种遍历算法，它没有使用
* 二叉树本身的结构特点（左右子树递归）进行递归遍历
* @author jzj
*/
private class LevelOrderIterator implements Iterator {
//使用队列结构实现层次遍历，队列里存储的为节点
private LinkedList queue = new LinkedList();
public LevelOrderIterator(Entry node) {
}
if (node != null) {
//将根入队
t(node);
}
}
//是否还有下一个元素
public boolean hasNext() {
if (y()) {
return false;
}
return true;
}
//取下一个元素
public Entry next() {
if (hasNext()) {
//取栈顶迭元素
Entry treeNode = (Entry) First();
}
if ( != null) {//如果有左子树，加入有序列表中
t();
}
if ( != null) {//如果有右子树，加入有序列表中
t();
}
// 返回遍历得到的节点
return treeNode;
} else {
// 如果队列为空
return null;
}
public void remove() {
throw new UnsupportedOperationException();
}
/**
* 向外界提供广度优先迭代器
* @return Iterator 返回遍历迭代器
*/
public Iterator createLayerOrderItr() {
return new LevelOrderIterator(root);
} public static void main(String[] args) {
//创建一棵满二叉树
BinTreeOutOrder treeOrder = new BinTreeOutOrder();
FullBiTree(15);
Iterator preOrderItr = PreOrderItr();
("深度优先（先根）遍历 - ");
while (t()) {
(((Entry) ()).elem + " ");
}
n();
("广度优先（层次）遍历 - ");
Iterator layerOrderItr = LayerOrderItr();
while (t()) {
(((Entry) ()).elem + " ");
}
/*
* output:
* 深度优先（先根）遍历 - 1 2 4 8 9 5 10 11 3 6 12 13 7 14 15
* 广度优先（层次）遍历 - 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
*/
}
}
package e;
/**
*
* 可回溯的二叉树
* 二叉树的非递归遍历 *
* @author jzj
* @date 2009-12-23
*/
public class BackBinTree {// Bin=Binary(二进位的, 二元的)
protected Entry root;//根
private int size;//树的节点数
/**
* 树的节点结构
* @author jzj
* @date 2009-12-23
*/
private static class Entry {
int elem;//数据域，这里为了测试，就作为节点编号吧
Entry paraent;//父节点
Entry left;//左节点
Entry right;//右节点
//构造函数只有两个参数，左右节点是调用add方法时设置
public Entry(int elem, Entry parent) {
= elem;
t = parent;
}
}
/**
* 查找前序遍历（根左右）直接后继节点
*
* 以非递归 根左右 的方式遍历树
*
* @param e 需要查找哪个节点的直接后继节点
* @return Entry 前序遍历直接后继节点
*/
public Entry preOrderSuccessor(Entry e) {
if (e == null) {
return null;
}//如果左子树不为空，则直接后继为左子节点
else if ( != null) {//先看左子节点是否为空
return ;//如果不为空，则直接后继为左子节点
}//否则如果右子树不为空，则直接后继为右子节点
else if ( != null) {//如果左子节点为空，则看右子节点是否为空
return ;//如果右子节点不为空，则返回 }//左右子节点都为空的情况下
else {
Entry s = t;
Entry c = e;
/*
* 一直向上，直到c是s的左子树，且s的右子树不为空。请试着找一下36与68节点的
* 直接后继节点，36的应该是75，而68则没有后继节点了
*
* 50
* /
* 37 75
* / /
* 25 61
* / /
* 15 30 55 68
* /
* 28 32 59
*
* 36
*/
while (s != null && (c == || == null)) {
c = s;
s = t;
}
//退出循环时 s 可以为null，比如查找 68 节点的直接后继时退出循环时s=null
if (s == null) {
return null;
} else {
return ;
}
}
}
/**
* 查找前序遍历（根左右）直接前驱节点
*
* 以非递归 右左根 的方式遍历树
*
* @param e 需要查找哪个节点的直接前驱节点
* @return Entry 前序遍历直接前驱节点
*/
找
public Entry preOrderAncestor(Entry e) {
if (e == null) {
return null;
}//如果节点为父节点的左节点，则父节点就是直接前驱节点
else if (t != null && e == ) {
return t;
}//如果节点为父节点的右节点
else if (t != null && e == ) {
}
Entry s = t;//前驱节点默认为父节点
if ( != null) {//如果父节点没有左子，前驱节点就为父节点
s = ;//如果父节点的左子节点不空，则初始为父节点左子节点
/*
* 只要父节点左子节点还有子节点，则前驱节点要从其子树中找。请试着 * 一下75直接前驱节点，应该是36
*
* 50
* /
* 37 75
* / /
* 25 61
* / /
* 15 30 55 68
* /
* 28 32 59
*
* 36
*/
while ( != null || != null) {
//在父节点的左子节点的子树中查找时，一定要先向右边拐
if ( != null) {
s = ;
} else {//如果右边没有，然后才能向左边拐
s = ;
}
}
}
return s;
} else {//如果是根节点，则没有直接前驱节点了
return null;
}
/**
* 查找后序遍历（左右根）直接后继节点
*
* 以非递归 左右根 的方式遍历树
*
* @param e 需要查找哪个节点的直接后继节点
* @return Entry 后序遍历直接后继节点
*/
public Entry postOrderSuccessor(Entry e) {
if (e == null) {
return null;
}//如果节点为父节点的右子节点，则父节点就是直接后继节点
else if (t != null && e == ) {
return t;
}//如果节点为父节点的左子节点
else if (t != null && e == ) {
Entry s = t;//后继节点默认为父节点
if ( != null) {//如果父节点没有右子，后继节点就为父节点
s = ;//如果父节点的右子节点不空，则初始为父节点右子节点
/*
* 只要父节点右子节点还有子节点，则后断节点要从其子树中找，
* 如15的后继节点为28
* 50
* /
* 37 75
* / /
* 25 61
* / /
* 15 30 55 68
* /
* 28 32 59
*
* 36
*/
while ( != null || != null) {
//在父节点的右子节点的子树中查找时，一定要先向左边拐
if ( != null) {
s = ;
} else {//如果左边没有，然后才能向右边拐
s = ;
}
} }
return s;
} else {
//如果是根节点，则没有后继节点了
return null;
}
}
/**
* 查找后序遍历（左右根）直接前驱节点
*
* 以非递归 根右左 的方式遍历树
*
* @param e 需要查找哪个节点的直接前驱节点
* @return Entry 后序遍历直接前驱节点
*/
public Entry postOrderAncestor(Entry e) {
if (e == null) {
return null;
}//如果右子树不为空，则直接前驱为右子节点
else if ( != null) {//先看右子节点是否为空
return ;//如果不为空，则直接后继为右子节点
}//否则如果左子树不为空，则直接前驱为左子节点
else if ( != null) {
return ;
}//左右子节点都为空的情况下
else {
Entry s = t;
Entry c = e;
/*
* 一直向上，直到c是s的右子树，且s的左子树不为空。请试着找一下59与15节点的
* 直接后继节点，59的应该是37，而15则没有后继节点了
*
* 50
* /
* 37 75
* / /
* 25 61
* / /
* 15 30 55 68
* / * 28 32 59
*
* 36
*/
while (s != null && (c == || == null)) {
c = s;
s = t;
}
if (s == null) {
return null;
} else {
return ;
}
}
}
/**
* 查找中序遍历（左根右）直接后继节点
*
* 以非递归 左根右 的方式遍历树
*
* @param e 需要查找哪个节点的直接后继节点
* @return Entry 中序遍历直接后继节点
*/
public Entry inOrderSuccessor(Entry e) {
if (e == null) {
return null;
}//如果待找的节点有右子树，则在右子树上查找
else if ( != null) {
//默认后继节点为右子节点（如果右子节点没有左子树时即为该节点）
Entry p = ;
while ( != null) {
//注，如果右子节点的左子树不为空，则在左子树中查找，且后面找时要一直向左拐
p = ;
}
return p;
}//如果待查节点没有右子树，则要在祖宗节点中查找后继节点
else {
//默认后继节点为父节点（如果待查节点为父节点的左子树，则后继为父节点）
Entry p = t;
Entry current = e;//当前节点，如果其父不为后继，则下次指向父节点
//如果待查节点为父节点的右节点时，继续向上找，一直要找到current为左子节点，则s才是后继 while (p != null && current == ) {
current = p;
p = t;
}
return p;
}
}
/**
* 查找中序遍历（左根右）直接前驱节点
*
* 以非递归 右根左 的方式遍历树
*
* @param e 需要查找哪个节点的直接前驱节点
* @return Entry 中序遍历直接前驱节点
*/
public Entry inOrderAncestor(Entry e) {
if (e == null) {
return null;
}//如果待找的节点有左子树，则在在子树上查找
else if ( != null) {
//默认直接前驱节点为左子节点（如果左子节点没有右子树时即为该节点）
Entry p = ;
while ( != null) {
//注，如果左子节点的右子树不为空，则在右子树中查找，且后面找时要一直向右拐
p = ;
}
return p;
}//如果待查节点没有左子树，则要在祖宗节点中查找前驱节点
else {
//默认前驱节点为父节点（如果待查节点为父节点的右子树，则前驱为父节点）
Entry p = t;
Entry current = e;//当前节点，如果其父不为前驱，则下次指向父节点
//如果待查节点为父节点的左节点时，继续向上找，一直要找到current为p的右子节点，则s才是前驱
while (p != null && current == ) {
current = p;
p = t;
}
return p;
}
}
/**
* 查找指定的节点
* @param num
* @return Entry
*/
public Entry getEntry(int num) {
return getEntry(root, num);
}
/**
* 使用树的先序遍历递归方式查找指定的节点
*
* @param entry
* @param num
* @return
*/
private Entry getEntry(Entry entry, int num) {
//如果找到，则停止后续搜索，并把查找到的节点返回给上层调用者
if ( == num) {//1、先与父节点比对
return entry;
}
Entry tmp = null;
if ( != null) {//2、再在左子树上找
tmp = getEntry(, num);
//如果左子树上找到，返回并停止查找，否则继续在后续节点中找
if (tmp != null) {
//节点在左子树中找到，返回给上层调用者
return tmp;
}
}
if ( != null) {//3、否则在右子树上找
tmp = getEntry(, num);
//如果右子树上找到，返回并停止查找，否则继续在后续节点中找
if (tmp != null) {
//节点在右子树中找到，返回给上层调用者
return tmp;
}
}
//当前比较节点 entry 子树为空或不为空时没有找到，直接返回给上层调用者null
}
return null;
/**
* 根据给定的数组创建一棵树，这个棵树可以是完全二叉树也可是普通二叉树
* 数组中为0的表示不创建该位置上的节点
* @param nums 数组中指定了要创建的节点的编号，如果为0，表示不创建
*/
public void createBinTree(int[] nums) {
root = recurCreateBinTree(nums, null, 0);
}
/**
* 递归创建二叉树
* @param nums 数组中指定了要创建的节点的编号，如果为0，表示不创建
* @param paraent 父节点
* @param index 需要使用数组中的哪个元素创建节点，如果为元素为0，则不创建
* @return Entry 返回创建的节点，最终会返回树的根节点
*/
private Entry recurCreateBinTree(int[] nums, Entry pararent, int index) {
//指定索引上的编号不为零上才需创建节点
if (nums[index] != 0) {
size++;
Entry root = new Entry(nums[index], pararent);//根节点
//如果有左子树则创建左子树
if ((index + 1) * 2 <= ) {
= (Entry) recurCreateBinTree(nums, root, (index + 1) * 2 - 1);
//如果还可以创建右子树，则创建
if ((index + 1) * 2 + 1 <= ) {
= (Entry) recurCreateBinTree(nums, root, (index + 1) * 2);
}
}
return (Entry) root;
}
return null;
}
public int size() {
return size;
}
//测试
public static void main(String[] args) {
//创建一棵非完全二叉树
BackBinTree binTree = new BackBinTree();
/*
* 50
* /
* 37 75
* / /
* 25 61
* / /
* 15 30 55 68
* /
* 28 32 59
*
* 36
*/
int[] nums = new int[] { 50, 37, 75, 25, 0, 61, 0, 15, 30, 0, 0, 55, 68, 0, 0, 0,
0, 28, 32, 0, 0, 0, 0, 0, 59, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 36 };
BinTree(nums);
Entry entry = ry(50);
("根左右（先序遍历）- ");
while (entry != null) {
( + " ");
entry = erSuccessor(entry);
}
n();
entry = ry(68);
("右左根（先序的逆）- ");
while (entry != null) {
( + " ");
entry = erAncestor(entry);
}
n();
entry = ry(15);
("左右根（后序遍历）- ");
while (entry != null) {
( + " ");
entry = derSuccessor(entry);
}
n();
entry = ry(50);
("根右左（后序的逆）- ");
}
}
while (entry != null) {
( + " ");
entry = derAncestor(entry);
}
n();
entry = ry(15);
("左根右（中序遍历）- ");
while (entry != null) {
( + " ");
entry = rSuccessor(entry);
}
n();
entry = ry(75);
("右根左（中序的逆）- ");
while (entry != null) {
( + " ");
entry = rAncestor(entry);
}
n();
/*
* output:
* 根左右（先序遍历）- 50 37 25 15 30 28 32 36 75 61 55 59 68
* 右左根（先序的逆）- 68 59 55 61 75 36 32 28 30 15 25 37 50
* 左右根（后序遍历）- 15 28 36 32 30 25 37 59 55 68 61 75 50
* 根右左（后序的逆）- 50 75 61 68 55 59 37 25 30 32 36 28 15
* 左根右（中序遍历）- 15 25 28 30 32 36 37 50 55 59 61 68 75
* 右根左（中序的逆）- 75 68 61 59 55 50 37 36 32 30 28 25 15
*/
发布者：admin，转转请注明出处：http://www.yc00.com/web/1687384944a6091.html
评论列表（0条）