一、数据结构分类 （一）按逻辑结构 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 tree.bintree; 2. /** 3. * 创建 非完全二叉树、完全二叉树、满二叉树 4. * 5. * 由于二叉树的节点增加没有什么规则，所以这里只是简单的使用了递一 6. * 次性把整棵树创建出来，而没有设计出一个一个添加节点的方法与删除 7. * 8. * @author jzj 9. * @date 2009-12-23 10. */ 11. public 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. this.elem = 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. rootNode.left = recurCreateFullBiTree(num * 2, nodeCount); 55. //如果还可以创建右子树，则创建 56. if (num * 2 + 1 <= nodeCount) { 57. rootNode.right = 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 <= nums.length) { 85. rootNode.left = (Entry) recurCreateBinTree(nums, (index + 1) * 2 - 1); 86. //如果还可以创建右子树，则创建 87. if ((index + 1) * 2 + 1 <= nums.length) { 88. rootNode.right = (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 (e.right != null) { 105. e = e.right; 106. } 107. return e.elem; 108. } 109. 110. //测试 111. public static void main(String[] args) { 112. 113. //创建一个满二叉树 114. BinTree binTree = new BinTree(); 115. binTree.createFullBiTree(15); 116. System.out.println(binTree.size());//15 117. System.out.println(binTree.getLast());//15 118. 119. //创建一个完全二叉树 120. binTree = new BinTree(); 121. binTree.createFullBiTree(14); 122. System.out.println(binTree.size());//14 123. System.out.println(binTree.getLast());//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.createBinTree(nums); 129. System.out.println(binTree.size());//8 130. System.out.println(binTree.getLast());//8 131. 132. } 133. } package tree.bintree; /** * 创建 非完全二叉树、完全二叉树、满二叉树 * * 由于二叉树的节点增加没有什么规则，所以这里只是简单的使用了递一 * 次性把整棵树创建出来，而没有设计出一个一个添加节点的方法与删除 * * @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) { this.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) { rootNode.left = recurCreateFullBiTree(num * 2, nodeCount); //如果还可以创建右子树，则创建 if (num * 2 + 1 <= nodeCount) { rootNode.right = 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 <= nums.length) { rootNode.left = (Entry) recurCreateBinTree(nums, (index + 1) * 2 - 1); //如果还可以创建右子树，则创建 if ((index + 1) * 2 + 1 <= nums.length) { rootNode.right = (Entry) recurCreateBinTree(nums, (index + 1) * 2); } } return (Entry) rootNode; } return null; } public int size() { return size; } //取树的最左边的节点 public int getLast() { Entry e = root; while (e.right != null) { e = e.right; } return e.elem; } //测试 public static void main(String[] args) { //创建一个满二叉树 BinTree binTree = new BinTree(); binTree.createFullBiTree(15); System.out.println(binTree.size());//15 System.out.println(binTree.getLast());//15 //创建一个完全二叉树 binTree = new BinTree(); binTree.createFullBiTree(14); System.out.println(binTree.size());//14 System.out.println(binTree.getLast());//7 //创建一棵非完全二叉树 binTree = new BinTree(); int[] nums = new int[] { 1, 2, 3, 4, 0, 0, 5, 0, 6, 0, 0, 0, 0, 7, 8 }; binTree.createBinTree(nums); System.out.println(binTree.size());//8 System.out.println(binTree.getLast());//8 } } （二）利用二叉树本身特点进行递归遍历（属内部遍历） 由于二叉树所具有的递归性质，一棵非空的二叉树可以看作是由根节点、左子树和右子树3部分构成，因为若能依次遍历这3部分的信息，也就遍历了整个二叉树。按照左子树的遍历在右子树的遍历之前进行的约定，根据访问根节点位置的不同，可以得到二叉的前序、中序、后序3种遍历方法。 Java代码 1. package tree.bintree; 2. 3. /** 4. * 二叉树的三种 内部 遍历：前序、中序、后序 5. * 但不管是哪种方式，左子树的遍历在右子树的遍历之前遍历是这有三种遍历方式都 6. * 必须遵循的约定 7. * @author jzj 8. * @date 2009-12-23 9. */ 10. public class BinTreeInOrder extends BinTree { 11. 12. /** 13. * 节点访问者，可根据需要重写visit方法 14. */ 15. static abstract class Visitor { 16. void visit(Object ele) { 17. System.out.print(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. v.visit(node.elem);//先遍历父节点 33. preOrder(v, node.left);//再遍历左节点 34. preOrder(v, node.right);//最后遍历右节点 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, node.left);//先遍历左节点 50. v.visit(node.elem);//再遍历父节点 51. inOrder(v, node.right);//最后遍历右节点 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, node.left);//先遍历左节点 67. postOrder(v, node.right);//再遍历右节点 68. v.visit(node.elem);//最后遍历父节点 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. treeOrder.createBinTree(nums); 79. System.out.print("前序遍历 - "); 80. treeOrder.preOrder(new Visitor() { 81. }); 82. System.out.println(); 83. System.out.print("中序遍历 - "); 84. treeOrder.inOrder(new Visitor() { 85. }); 86. System.out.println(); 87. System.out.print("后序遍历 - "); 88. treeOrder.postOrder(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. } package tree.bintree; /** * 二叉树的三种 内部 遍历：前序、中序、后序 * 但不管是哪种方式，左子树的遍历在右子树的遍历之前遍历是这有三种遍历方式都 * 必须遵循的约定 * @author jzj * @date 2009-12-23 */ public class BinTreeInOrder extends BinTree { /** * 节点访问者，可根据需要重写visit方法 */ static abstract class Visitor { void visit(Object ele) { System.out.print(ele + " "); } } public void preOrder(Visitor v) { preOrder(v, root); } /** * 树的前序递归遍历 pre=prefix(前缀) * @param node 要遍历的节点 */ private void preOrder(Visitor v, Entry node) { //如果传进来的节点不为空，则遍历，注，叶子节点的子节点为null if (node != null) { v.visit(node.elem);//先遍历父节点 preOrder(v, node.left);//再遍历左节点 preOrder(v, node.right);//最后遍历右节点 } } 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, node.left);//先遍历左节点 v.visit(node.elem);//再遍历父节点 inOrder(v, node.right);//最后遍历右节点 } } 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, node.left);//先遍历左节点 postOrder(v, node.right);//再遍历右节点 v.visit(node.elem);//最后遍历父节点 } } //测试 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(); treeOrder.createBinTree(nums); System.out.print("前序遍历 - "); treeOrder.preOrder(new Visitor() { }); System.out.println(); System.out.print("中序遍历 - "); treeOrder.inOrder(new Visitor() { }); System.out.println(); System.out.print("后序遍历 - "); treeOrder.postOrder(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 */ } } （三）二叉树的非递归遍历（属外部遍历） 1、利用栈与队列对二叉树进行非递归遍历 Java代码 1. package tree.bintree; 2. 3. import java.util.Iterator; 4. import java.util.LinkedList; 5. import java.util.Stack; 6. 7. /** 8. * 二叉树的外部遍历：深度优先（先根）、广度（层次）优先遍历 9. * 10. * @author jzj 11. * @date 2009-12-23 12. */ 13. public 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. stack.push(node); 29. 30. } 31. 32. //是否还有下一个元素 33. public boolean hasNext() { 34. if (stack.isEmpty()) { 35. return false; 36. } 37. return true; 38. } 39. 40. //取下一个元素 41. public Entry next() { 42. if (hasNext()) { 43. //取栈顶元素 44. Entry treeNode = (Entry) stack.pop();//先访问根 45. 46. if (treeNode.right != null) { 47. stack.push(treeNode.right);//再放入右子节点 48. } 49. 50. if (treeNode.left != null) { 51. stack.push(treeNode.left);//最后放入左子节点，但访问先于右节点 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. queue.addLast(node); 92. } 93. } 94. 95. //是否还有下一个元素 96. public boolean hasNext() { 97. if (queue.isEmpty()) { 98. return false; 99. } 100. return true; 101. } 102. 103. //取下一个元素 104. public Entry next() { 105. if (hasNext()) { 106. //取栈顶迭元素 107. Entry treeNode = (Entry) queue.removeFirst(); 108. 109. if (treeNode.left != null) {//如果有左子树，加入有序列表中 110. queue.addLast(treeNode.left); 111. } 112. if (treeNode.right != null) {//如果有右子树，加入有序列表中 113. queue.addLast(treeNode.right); 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. treeOrder.createFullBiTree(15); 143. Iterator preOrderItr = treeOrder.createPreOrderItr(); 144. System.out.print("深度优先（先根）遍历 - "); 145. while (preOrderItr.hasNext()) { 146. System.out.print(((Entry) preOrderItr.next()).elem + " "); 147. } 148. System.out.println(); 149. System.out.print("广度优先（层次）遍历 - "); 150. Iterator layerOrderItr = treeOrder.createLayerOrderItr(); 151. while (layerOrderItr.hasNext()) { 152. System.out.print(((Entry) layerOrderItr.next()).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. } package tree.bintree; import java.util.Iterator; import java.util.LinkedList; import java.util.Stack; /** * 二叉树的外部遍历：深度优先（先根）、广度（层次）优先遍历 * * @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) { //根入栈，但在放入左右子节点前会马上出栈，即根先优于左右子节点访问 stack.push(node); } //是否还有下一个元素 public boolean hasNext() { if (stack.isEmpty()) { return false; } return true; } //取下一个元素 public Entry next() { if (hasNext()) { //取栈顶元素 Entry treeNode = (Entry) stack.pop();//先访问根 if (treeNode.right != null) { stack.push(treeNode.right);//再放入右子节点 } if (treeNode.left != null) { stack.push(treeNode.left);//最后放入左子节点，但访问先于右节点 } // 返回遍历得到的节点 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) { //将根入队 queue.addLast(node); } } //是否还有下一个元素 public boolean hasNext() { if (queue.isEmpty()) { return false; } return true; } //取下一个元素 public Entry next() { if (hasNext()) { //取栈顶迭元素 Entry treeNode = (Entry) queue.removeFirst(); if (treeNode.left != null) {//如果有左子树，加入有序列表中 queue.addLast(treeNode.left); } if (treeNode.right != null) {//如果有右子树，加入有序列表中 queue.addLast(treeNode.right); } // 返回遍历得到的节点 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(); treeOrder.createFullBiTree(15); Iterator preOrderItr = treeOrder.createPreOrderItr(); System.out.print("深度优先（先根）遍历 - "); while (preOrderItr.hasNext()) { System.out.print(((Entry) preOrderItr.next()).elem + " "); } System.out.println(); System.out.print("广度优先（层次）遍历 - "); Iterator layerOrderItr = treeOrder.createLayerOrderItr(); while (layerOrderItr.hasNext()) { System.out.print(((Entry) layerOrderItr.next()).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 */ } } 2、利用二叉树节点的父节点指针进行非递归遍历 要想采用非递归的方法遍历树，又不借助于前面的队列与栈，我们需要该树是一棵可回溯的二叉树，即从子节点要能够知道他的父节点及祖先节点，与前面的二叉树不同的是，树的节点结构体中多一个指向父的节点指针，这样外界可以以非递归的方式来遍历二叉树了 。 Java代码 1. package tree.bintree; 2. 3. /** 4. * 5. * 可回溯的二叉树 6. * 二叉树的非递归遍历 7. * 8. * @author jzj 9. * @date 2009-12-23 10. */ 11. public 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. this.elem = elem; 30. this.paraent = 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 (e.left != null) {//先看左子节点是否为空 47. return e.left;//如果不为空，则直接后继为左子节点 48. }//否则如果右子树不为空，则直接后继为右子节点 49. else if (e.right != null) {//如果左子节点为空，则看右子节点是否为空 50. return e.right;//如果右子节点不为空，则返回 51. }//左右子节点都为空的情况下 52. else { 53. Entry s = e.paraent; 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 == s.right || s.right == null)) { 73. c = s; 74. s = s.paraent; 75. } 76. //退出循环时 s 可以为null，比如查找 68 节点的直接后继时退出循环时s=null 77. if (s == null) { 78. return null; 79. } else { 80. return s.right; 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 (e.paraent != null && e == e.paraent.left) { 98. return e.paraent; 99. }//如果节点为父节点的右节点 100. else if (e.paraent != null && e == e.paraent.right) { 101. 102. Entry s = e.paraent;//前驱节点默认为父节点 103. if (s.left != null) {//如果父节点没有左子，前驱节点就为父节点 104. s = s.left;//如果父节点的左子节点不空，则初始为父节点左子节点 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 (s.left != null || s.right != null) { 123. //在父节点的左子节点的子树中查找时，一定要先向右边拐 124. if (s.right != null) { 125. s = s.right; 126. } else {//如果右边没有，然后才能向左边拐 127. s = s.left; 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 (e.paraent != null && e == e.paraent.right) { 150. return e.paraent; 151. }//如果节点为父节点的左子节点 152. else if (e.paraent != null && e == e.paraent.left) { 153. Entry s = e.paraent;//后继节点默认为父节点 154. if (s.right != null) {//如果父节点没有右子，后继节点就为父节点 155. s = s.right;//如果父节点的右子节点不空，则初始为父节点右子节点 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 (s.left != null || s.right != null) { 173. //在父节点的右子节点的子树中查找时，一定要先向左边拐 174. if (s.left != null) { 175. s = s.left; 176. } else {//如果左边没有，然后才能向右边拐 177. s = s.right; 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 (e.right != null) {//先看右子节点是否为空 202. return e.right;//如果不为空，则直接后继为右子节点 203. }//否则如果左子树不为空，则直接前驱为左子节点 204. else if (e.left != null) { 205. return e.left; 206. }//左右子节点都为空的情况下 207. else { 208. Entry s = e.paraent; 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 == s.left || s.left == null)) { 228. c = s; 229. s = s.paraent; 230. } 231. if (s == null) { 232. return null; 233. } else { 234. return s.left; 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 (e.right != null) { 252. //默认后继节点为右子节点（如果右子节点没有左子树时即为该节点） 253. Entry p = e.right; 254. while (p.left != null) { 255. //注，如果右子节点的左子树不为空，则在左子树中查找，且后面找时要一直向左拐 256. p = p.left; 257. } 258. return p; 259. }//如果待查节点没有右子树，则要在祖宗节点中查找后继节点 260. else { 261. //默认后继节点为父节点（如果待查节点为父节点的左子树，则后继为父节点） 262. Entry p = e.paraent; 263. Entry current = e;//当前节点，如果其父不为后继，则下次指向父节点 264. //如果待查节点为父节点的右节点时，继续向上找，一直要找到current为左子节点，则s才是后继 265. while (p != null && current == p.right) { 266. current = p; 267. p = p.paraent; 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 (e.left != null) { 286. //默认直接前驱节点为左子节点（如果左子节点没有右子树时即为该节点） 287. Entry p = e.left; 288. while (p.right != null) { 289. //注，如果左子节点的右子树不为空，则在右子树中查找，且后面找时要一直向右拐 290. p = p.right; 291. } 292. return p; 293. }//如果待查节点没有左子树，则要在祖宗节点中查找前驱节点 294. else { 295. //默认前驱节点为父节点（如果待查节点为父节点的右子树，则前驱为父节点） 296. Entry p = e.paraent; 297. Entry current = e;//当前节点，如果其父不为前驱，则下次指向父节点 298. //如果待查节点为父节点的左节点时，继续向上找，一直要找到current为p的右子节点，则s才是前驱 299. while (p != null && current == p.left) { 300. current = p; 301. p = p.paraent; 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 (entry.elem == num) {//1、先与父节点比对 327. return entry; 328. } 329. 330. Entry tmp = null; 331. 332. if (entry.left != null) {//2、再在左子树上找 333. tmp = getEntry(entry.left, num); 334. //如果左子树上找到，返回并停止查找，否则继续在后续节点中找 335. if (tmp != null) { 336. //节点在左子树中找到，返回给上层调用者 337. return tmp; 338. } 339. } 340. 341. if (entry.right != null) {//3、否则在右子树上找 342. tmp = getEntry(entry.right, 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 <= nums.length) { 377. root.left = (Entry) recurCreateBinTree(nums, root, (index + 1) * 2 - 1); 378. //如果还可以创建右子树，则创建 379. if ((index + 1) * 2 + 1 <= nums.length) { 380. root.right = (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[] { 50, 37, 75, 25, 0, 61, 0, 15, 30, 0, 0, 55, 68, 0, 0, 0, 412. 0, 28, 32, 0, 0, 0, 0, 0, 59, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 36 }; 413. binTree.createBinTree(nums); 414. 415. Entry entry = binTree.getEntry(50); 416. System.out.print("根左右（先序遍历）- "); 417. while (entry != null) { 418. System.out.print(entry.elem + " "); 419. entry = binTree.preOrderSuccessor(entry); 420. } 421. System.out.println(); 422. entry = binTree.getEntry(68); 423. System.out.print("右左根（先序的逆）- "); 424. while (entry != null) { 425. System.out.print(entry.elem + " "); 426. entry = binTree.preOrderAncestor(entry); 427. } 428. System.out.println(); 429. entry = binTree.getEntry(15); 430. System.out.print("左右根（后序遍历）- "); 431. while (entry != null) { 432. System.out.print(entry.elem + " "); 433. entry = binTree.postOrderSuccessor(entry); 434. } 435. System.out.println(); 436. 437. entry = binTree.getEntry(50); 438. System.out.print("根右左（后序的逆）- "); 439. while (entry != null) { 440. System.out.print(entry.elem + " "); 441. entry = binTree.postOrderAncestor(entry); 442. } 443. System.out.println(); 444. 445. entry = binTree.getEntry(15); 446. System.out.print("左根右（中序遍历）- "); 447. while (entry != null) { 448. System.out.print(entry.elem + " "); 449. entry = binTree.inOrderSuccessor(entry); 450. } 451. System.out.println(); 452. 453. entry = binTree.getEntry(75); 454. System.out.print("右根左（中序的逆）- "); 455. while (entry != null) { 456. System.out.print(entry.elem + " "); 457. entry = binTree.inOrderAncestor(entry); 458. } 459. System.out.println(); 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. } package tree.bintree; /** * * 可回溯的二叉树 * 二叉树的非递归遍历 * * @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) { this.elem = elem; this.paraent = parent; } } /** * 查找前序遍历（根左右）直接后继节点 * * 以非递归 根左右 的方式遍历树 * * @param e 需要查找哪个节点的直接后继节点 * @return Entry 前序遍历直接后继节点 */ public Entry preOrderSuccessor(Entry e) { if (e == null) { return null; }//如果左子树不为空，则直接后继为左子节点 else if (e.left != null) {//先看左子节点是否为空 return e.left;//如果不为空，则直接后继为左子节点 }//否则如果右子树不为空，则直接后继为右子节点 else if (e.right != null) {//如果左子节点为空，则看右子节点是否为空 return e.right;//如果右子节点不为空，则返回 }//左右子节点都为空的情况下 else { Entry s = e.paraent; 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 == s.right || s.right == null)) { c = s; s = s.paraent; } //退出循环时 s 可以为null，比如查找 68 节点的直接后继时退出循环时s=null if (s == null) { return null; } else { return s.right; } } } /** * 查找前序遍历（根左右）直接前驱节点 * * 以非递归 右左根 的方式遍历树 * * @param e 需要查找哪个节点的直接前驱节点 * @return Entry 前序遍历直接前驱节点 */ public Entry preOrderAncestor(Entry e) { if (e == null) { return null; }//如果节点为父节点的左节点，则父节点就是直接前驱节点 else if (e.paraent != null && e == e.paraent.left) { return e.paraent; }//如果节点为父节点的右节点 else if (e.paraent != null && e == e.paraent.right) { Entry s = e.paraent;//前驱节点默认为父节点 if (s.left != null) {//如果父节点没有左子，前驱节点就为父节点 s = s.left;//如果父节点的左子节点不空，则初始为父节点左子节点 /* * 只要父节点左子节点还有子节点，则前驱节点要从其子树中找。请试着找 * 一下75直接前驱节点，应该是36 * * 50 * /\ * 37 75 * / / * 25 61 * /\ /\ * 15 30 55 68 * /\ \ * 28 32 59 * \ * 36 */ while (s.left != null || s.right != null) { //在父节点的左子节点的子树中查找时，一定要先向右边拐 if (s.right != null) { s = s.right; } else {//如果右边没有，然后才能向左边拐 s = s.left; } } } return s; } else {//如果是根节点，则没有直接前驱节点了 return null; } } /** * 查找后序遍历（左右根）直接后继节点 * * 以非递归 左右根 的方式遍历树 * * @param e 需要查找哪个节点的直接后继节点 * @return Entry 后序遍历直接后继节点 */ public Entry postOrderSuccessor(Entry e) { if (e == null) { return null; }//如果节点为父节点的右子节点，则父节点就是直接后继节点 else if (e.paraent != null && e == e.paraent.right) { return e.paraent; }//如果节点为父节点的左子节点 else if (e.paraent != null && e == e.paraent.left) { Entry s = e.paraent;//后继节点默认为父节点 if (s.right != null) {//如果父节点没有右子，后继节点就为父节点 s = s.right;//如果父节点的右子节点不空，则初始为父节点右子节点 /* * 只要父节点右子节点还有子节点，则后断节点要从其子树中找， * 如15的后继节点为28 * 50 * /\ * 37 75 * / / * 25 61 * /\ /\ * 15 30 55 68 * /\ \ * 28 32 59 * \ * 36 */ while (s.left != null || s.right != null) { //在父节点的右子节点的子树中查找时，一定要先向左边拐 if (s.left != null) { s = s.left; } else {//如果左边没有，然后才能向右边拐 s = s.right; } } } return s; } else { //如果是根节点，则没有后继节点了 return null; } } /** * 查找后序遍历（左右根）直接前驱节点 * * 以非递归 根右左 的方式遍历树 * * @param e 需要查找哪个节点的直接前驱节点 * @return Entry 后序遍历直接前驱节点 */ public Entry postOrderAncestor(Entry e) { if (e == null) { return null; }//如果右子树不为空，则直接前驱为右子节点 else if (e.right != null) {//先看右子节点是否为空 return e.right;//如果不为空，则直接后继为右子节点 }//否则如果左子树不为空，则直接前驱为左子节点 else if (e.left != null) { return e.left; }//左右子节点都为空的情况下 else { Entry s = e.paraent; 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 == s.left || s.left == null)) { c = s; s = s.paraent; } if (s == null) { return null; } else { return s.left; } } } /** * 查找中序遍历（左根右）直接后继节点 * * 以非递归 左根右 的方式遍历树 * * @param e 需要查找哪个节点的直接后继节点 * @return Entry 中序遍历直接后继节点 */ public Entry inOrderSuccessor(Entry e) { if (e == null) { return null; }//如果待找的节点有右子树，则在右子树上查找 else if (e.right != null) { //默认后继节点为右子节点（如果右子节点没有左子树时即为该节点） Entry p = e.right; while (p.left != null) { //注，如果右子节点的左子树不为空，则在左子树中查找，且后面找时要一直向左拐 p = p.left; } return p; }//如果待查节点没有右子树，则要在祖宗节点中查找后继节点 else { //默认后继节点为父节点（如果待查节点为父节点的左子树，则后继为父节点） Entry p = e.paraent; Entry current = e;//当前节点，如果其父不为后继，则下次指向父节点 //如果待查节点为父节点的右节点时，继续向上找，一直要找到current为左子节点，则s才是后继 while (p != null && current == p.right) { current = p; p = p.paraent; } return p; } } /** * 查找中序遍历（左根右）直接前驱节点 * * 以非递归 右根左 的方式遍历树 * * @param e 需要查找哪个节点的直接前驱节点 * @return Entry 中序遍历直接前驱节点 */ public Entry inOrderAncestor(Entry e) { if (e == null) { return null; }//如果待找的节点有左子树，则在在子树上查找 else if (e.left != null) { //默认直接前驱节点为左子节点（如果左子节点没有右子树时即为该节点） Entry p = e.left; while (p.right != null) { //注，如果左子节点的右子树不为空，则在右子树中查找，且后面找时要一直向右拐 p = p.right; } return p; }//如果待查节点没有左子树，则要在祖宗节点中查找前驱节点 else { //默认前驱节点为父节点（如果待查节点为父节点的右子树，则前驱为父节点） Entry p = e.paraent; Entry current = e;//当前节点，如果其父不为前驱，则下次指向父节点 //如果待查节点为父节点的左节点时，继续向上找，一直要找到current为p的右子节点，则s才是前驱 while (p != null && current == p.left) { current = p; p = p.paraent; } 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 (entry.elem == num) {//1、先与父节点比对 return entry; } Entry tmp = null; if (entry.left != null) {//2、再在左子树上找 tmp = getEntry(entry.left, num); //如果左子树上找到，返回并停止查找，否则继续在后续节点中找 if (tmp != null) { //节点在左子树中找到，返回给上层调用者 return tmp; } } if (entry.right != null) {//3、否则在右子树上找 tmp = getEntry(entry.right, 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 <= nums.length) { root.left = (Entry) recurCreateBinTree(nums, root, (index + 1) * 2 - 1); //如果还可以创建右子树，则创建 if ((index + 1) * 2 + 1 <= nums.length) { root.right = (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.createBinTree(nums); Entry entry = binTree.getEntry(50); System.out.print("根左右（先序遍历）- "); while (entry != null) { System.out.print(entry.elem + " "); entry = binTree.preOrderSuccessor(entry); } System.out.println(); entry = binTree.getEntry(68); System.out.print("右左根（先序的逆）- "); while (entry != null) { System.out.print(entry.elem + " "); entry = binTree.preOrderAncestor(entry); } System.out.println(); entry = binTree.getEntry(15); System.out.print("左右根（后序遍历）- "); while (entry != null) { System.out.print(entry.elem + " "); entry = binTree.postOrderSuccessor(entry); } System.out.println(); entry = binTree.getEntry(50); System.out.print("根右左（后序的逆）- "); while (entry != null) { System.out.print(entry.elem + " "); entry = binTree.postOrderAncestor(entry); } System.out.println(); entry = binTree.getEntry(15); System.out.print("左根右（中序遍历）- "); while (entry != null) { System.out.print(entry.elem + " "); entry = binTree.inOrderSuccessor(entry); } System.out.println(); entry = binTree.getEntry(75); System.out.print("右根左（中序的逆）- "); while (entry != null) { System.out.print(entry.elem + " "); entry = binTree.inOrderAncestor(entry); } System.out.println(); /* * 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 */ } } · · 大小: 1.4 KB · · 大小: 12.3 KB package tree.bintree; /** * 创建 非完全二叉树、完全二叉树、满二叉树 * * 由于二叉树的节点增加没有什么规则，所以这里只是简单的使用了递一 * 次性把整棵树创建出来，而没有设计出一个一个添加节点的方法与删除 * * @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) { this.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) { rootNode.left = recurCreateFullBiTree(num * 2, nodeCount); //如果还可以创建右子树，则创建 if (num * 2 + 1 <= nodeCount) { rootNode.right = 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 <= nums.length) { rootNode.left = (Entry) recurCreateBinTree(nums, (index + 1) * 2 - 1); //如果还可以创建右子树，则创建 if ((index + 1) * 2 + 1 <= nums.length) { rootNode.right = (Entry) recurCreateBinTree(nums, (index + 1) * 2); } } return (Entry) rootNode; } return null; } public int size() { return size; } //取树的最左边的节点 public int getLast() { Entry e = root; while (e.right != null) { e = e.right; } return e.elem; } //测试 public static void main(String[] args) { //创建一个满二叉树 BinTree binTree = new BinTree(); binTree.createFullBiTree(15); System.out.println(binTree.size());//15 System.out.println(binTree.getLast());//15 //创建一个完全二叉树 binTree = new BinTree(); binTree.createFullBiTree(14); System.out.println(binTree.size());//14 System.out.println(binTree.getLast());//7 //创建一棵非完全二叉树 binTree = new BinTree(); int[] nums = new int[] { 1, 2, 3, 4, 0, 0, 5, 0, 6, 0, 0, 0, 0, 7, 8 }; binTree.createBinTree(nums); System.out.println(binTree.size());//8 System.out.println(binTree.getLast());//8 } } package tree.bintree; /** * 二叉树的三种 内部 遍历：前序、中序、后序 * 但不管是哪种方式，左子树的遍历在右子树的遍历之前遍历是这有三种遍历方式都 * 必须遵循的约定 * @author jzj * @date 2009-12-23 */ public class BinTreeInOrder extends BinTree { /** * 节点访问者，可根据需要重写visit方法 */ static abstract class Visitor { void visit(Object ele) { System.out.print(ele + " "); } } public void preOrder(Visitor v) { preOrder(v, root); } /** * 树的前序递归遍历 pre=prefix(前缀) * @param node 要遍历的节点 */ private void preOrder(Visitor v, Entry node) { //如果传进来的节点不为空，则遍历，注，叶子节点的子节点为null if (node != null) { v.visit(node.elem);//先遍历父节点 preOrder(v, node.left);//再遍历左节点 preOrder(v, node.right);//最后遍历右节点 } } 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, node.left);//先遍历左节点 v.visit(node.elem);//再遍历父节点 inOrder(v, node.right);//最后遍历右节点 } } 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, node.left);//先遍历左节点 postOrder(v, node.right);//再遍历右节点 v.visit(node.elem);//最后遍历父节点 } } //测试 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(); treeOrder.createBinTree(nums); System.out.print("前序遍历 - "); treeOrder.preOrder(new Visitor() { }); System.out.println(); System.out.print("中序遍历 - "); treeOrder.inOrder(new Visitor() { }); System.out.println(); System.out.print("后序遍历 - "); treeOrder.postOrder(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 tree.bintree; import java.util.Iterator; import java.util.LinkedList; import java.util.Stack; /** * 二叉树的外部遍历：深度优先（先根）、广度（层次）优先遍历 * * @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) { //根入栈，但在放入左右子节点前会马上出栈，即根先优于左右子节点访问 stack.push(node); } //是否还有下一个元素 public boolean hasNext() { if (stack.isEmpty()) { return false; } return true; } //取下一个元素 public Entry next() { if (hasNext()) { //取栈顶元素 Entry treeNode = (Entry) stack.pop();//先访问根 if (treeNode.right != null) { stack.push(treeNode.right);//再放入右子节点 } if (treeNode.left != null) { stack.push(treeNode.left);//最后放入左子节点，但访问先于右节点 } // 返回遍历得到的节点 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) { //将根入队 queue.addLast(node); } } //是否还有下一个元素 public boolean hasNext() { if (queue.isEmpty()) { return false; } return true; } //取下一个元素 public Entry next() { if (hasNext()) { //取栈顶迭元素 Entry treeNode = (Entry) queue.removeFirst(); if (treeNode.left != null) {//如果有左子树，加入有序列表中 queue.addLast(treeNode.left); } if (treeNode.right != null) {//如果有右子树，加入有序列表中 queue.addLast(treeNode.right); } // 返回遍历得到的节点 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(); treeOrder.createFullBiTree(15); Iterator preOrderItr = treeOrder.createPreOrderItr(); System.out.print("深度优先（先根）遍历 - "); while (preOrderItr.hasNext()) { System.out.print(((Entry) preOrderItr.next()).elem + " "); } System.out.println(); System.out.print("广度优先（层次）遍历 - "); Iterator layerOrderItr = treeOrder.createLayerOrderItr(); while (layerOrderItr.hasNext()) { System.out.print(((Entry) layerOrderItr.next()).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 tree.bintree; /** * * 可回溯的二叉树 * 二叉树的非递归遍历 * * @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) { this.elem = elem; this.paraent = parent; } } /** * 查找前序遍历（根左右）直接后继节点 * * 以非递归 根左右 的方式遍历树 * * @param e 需要查找哪个节点的直接后继节点 * @return Entry 前序遍历直接后继节点 */ public Entry preOrderSuccessor(Entry e) { if (e == null) { return null; }//如果左子树不为空，则直接后继为左子节点 else if (e.left != null) {//先看左子节点是否为空 return e.left;//如果不为空，则直接后继为左子节点 }//否则如果右子树不为空，则直接后继为右子节点 else if (e.right != null) {//如果左子节点为空，则看右子节点是否为空 return e.right;//如果右子节点不为空，则返回 }//左右子节点都为空的情况下 else { Entry s = e.paraent; 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 == s.right || s.right == null)) { c = s; s = s.paraent; } //退出循环时 s 可以为null，比如查找 68 节点的直接后继时退出循环时s=null if (s == null) { return null; } else { return s.right; } } } /** * 查找前序遍历（根左右）直接前驱节点 * * 以非递归 右左根 的方式遍历树 * * @param e 需要查找哪个节点的直接前驱节点 * @return Entry 前序遍历直接前驱节点 */ public Entry preOrderAncestor(Entry e) { if (e == null) { return null; }//如果节点为父节点的左节点，则父节点就是直接前驱节点 else if (e.paraent != null && e == e.paraent.left) { return e.paraent; }//如果节点为父节点的右节点 else if (e.paraent != null && e == e.paraent.right) { Entry s = e.paraent;//前驱节点默认为父节点 if (s.left != null) {//如果父节点没有左子，前驱节点就为父节点 s = s.left;//如果父节点的左子节点不空，则初始为父节点左子节点 /* * 只要父节点左子节点还有子节点，则前驱节点要从其子树中找。请试着找 * 一下75直接前驱节点，应该是36 * * 50 * /\ * 37 75 * / / * 25 61 * /\ /\ * 15 30 55 68 * /\ \ * 28 32 59 * \ * 36 */ while (s.left != null || s.right != null) { //在父节点的左子节点的子树中查找时，一定要先向右边拐 if (s.right != null) { s = s.right; } else {//如果右边没有，然后才能向左边拐 s = s.left; } } } return s; } else {//如果是根节点，则没有直接前驱节点了 return null; } } /** * 查找后序遍历（左右根）直接后继节点 * * 以非递归 左右根 的方式遍历树 * * @param e 需要查找哪个节点的直接后继节点 * @return Entry 后序遍历直接后继节点 */ public Entry postOrderSuccessor(Entry e) { if (e == null) { return null; }//如果节点为父节点的右子节点，则父节点就是直接后继节点 else if (e.paraent != null && e == e.paraent.right) { return e.paraent; }//如果节点为父节点的左子节点 else if (e.paraent != null && e == e.paraent.left) { Entry s = e.paraent;//后继节点默认为父节点 if (s.right != null) {//如果父节点没有右子，后继节点就为父节点 s = s.right;//如果父节点的右子节点不空，则初始为父节点右子节点 /* * 只要父节点右子节点还有子节点，则后断节点要从其子树中找， * 如15的后继节点为28 * 50 * /\ * 37 75 * / / * 25 61 * /\ /\ * 15 30 55 68 * /\ \ * 28 32 59 * \ * 36 */ while (s.left != null || s.right != null) { //在父节点的右子节点的子树中查找时，一定要先向左边拐 if (s.left != null) { s = s.left; } else {//如果左边没有，然后才能向右边拐 s = s.right; } } } return s; } else { //如果是根节点，则没有后继节点了 return null; } } /** * 查找后序遍历（左右根）直接前驱节点 * * 以非递归 根右左 的方式遍历树 * * @param e 需要查找哪个节点的直接前驱节点 * @return Entry 后序遍历直接前驱节点 */ public Entry postOrderAncestor(Entry e) { if (e == null) { return null; }//如果右子树不为空，则直接前驱为右子节点 else if (e.right != null) {//先看右子节点是否为空 return e.right;//如果不为空，则直接后继为右子节点 }//否则如果左子树不为空，则直接前驱为左子节点 else if (e.left != null) { return e.left; }//左右子节点都为空的情况下 else { Entry s = e.paraent; 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 == s.left || s.left == null)) { c = s; s = s.paraent; } if (s == null) { return null; } else { return s.left; } } } /** * 查找中序遍历（左根右）直接后继节点 * * 以非递归 左根右 的方式遍历树 * * @param e 需要查找哪个节点的直接后继节点 * @return Entry 中序遍历直接后继节点 */ public Entry inOrderSuccessor(Entry e) { if (e == null) { return null; }//如果待找的节点有右子树，则在右子树上查找 else if (e.right != null) { //默认后继节点为右子节点（如果右子节点没有左子树时即为该节点） Entry p = e.right; while (p.left != null) { //注，如果右子节点的左子树不为空，则在左子树中查找，且后面找时要一直向左拐 p = p.left; } return p; }//如果待查节点没有右子树，则要在祖宗节点中查找后继节点 else { //默认后继节点为父节点（如果待查节点为父节点的左子树，则后继为父节点） Entry p = e.paraent; Entry current = e;//当前节点，如果其父不为后继，则下次指向父节点 //如果待查节点为父节点的右节点时，继续向上找，一直要找到current为左子节点，则s才是后继 while (p != null && current == p.right) { current = p; p = p.paraent; } return p; } } /** * 查找中序遍历（左根右）直接前驱节点 * * 以非递归 右根左 的方式遍历树 * * @param e 需要查找哪个节点的直接前驱节点 * @return Entry 中序遍历直接前驱节点 */ public Entry inOrderAncestor(Entry e) { if (e == null) { return null; }//如果待找的节点有左子树，则在在子树上查找 else if (e.left != null) { //默认直接前驱节点为左子节点（如果左子节点没有右子树时即为该节点） Entry p = e.left; while (p.right != null) { //注，如果左子节点的右子树不为空，则在右子树中查找，且后面找时要一直向右拐 p = p.right; } return p; }//如果待查节点没有左子树，则要在祖宗节点中查找前驱节点 else { //默认前驱节点为父节点（如果待查节点为父节点的右子树，则前驱为父节点） Entry p = e.paraent; Entry current = e;//当前节点，如果其父不为前驱，则下次指向父节点 //如果待查节点为父节点的左节点时，继续向上找，一直要找到current为p的右子节点，则s才是前驱 while (p != null && current == p.left) { current = p; p = p.paraent; } 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 (entry.elem == num) {//1、先与父节点比对 return entry; } Entry tmp = null; if (entry.left != null) {//2、再在左子树上找 tmp = getEntry(entry.left, num); //如果左子树上找到，返回并停止查找，否则继续在后续节点中找 if (tmp != null) { //节点在左子树中找到，返回给上层调用者 return tmp; } } if (entry.right != null) {//3、否则在右子树上找 tmp = getEntry(entry.right, 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 <= nums.length) { root.left = (Entry) recurCreateBinTree(nums, root, (index + 1) * 2 - 1); //如果还可以创建右子树，则创建 if ((index + 1) * 2 + 1 <= nums.length) { root.right = (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.createBinTree(nums); Entry entry = binTree.getEntry(50); System.out.print("根左右（先序遍历）- "); while (entry != null) { System.out.print(entry.elem + " "); entry = binTree.preOrderSuccessor(entry); } System.out.println(); entry = binTree.getEntry(68); System.out.print("右左根（先序的逆）- "); while (entry != null) { System.out.print(entry.elem + " "); entry = binTree.preOrderAncestor(entry); } System.out.println(); entry = binTree.getEntry(15); System.out.print("左右根（后序遍历）- "); while (entry != null) { System.out.print(entry.elem + " "); entry = binTree.postOrderSuccessor(entry); } System.out.println(); entry = binTree.getEntry(50); System.out.print("根右左（后序的逆）- "); while (entry != null) { System.out.print(entry.elem + " "); entry = binTree.postOrderAncestor(entry); } System.out.println(); entry = binTree.getEntry(15); System.out.print("左根右（中序遍历）- "); while (entry != null) { System.out.print(entry.elem + " "); entry = binTree.inOrderSuccessor(entry); } System.out.println(); entry = binTree.getEntry(75); System.out.print("右根左（中序的逆）- "); while (entry != null) { System.out.print(entry.elem + " "); entry = binTree.inOrderAncestor(entry); } System.out.println(); /* * 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 */ } }