Java实现二叉树的遍历

1、-、数据结构分类（一）按逻辑结构1. 集合（无辑关系）2. 线性结构（线性表）：数组、链表、栈、队列3. 非线性结构：树、图、多维数组（二）按存储结构顺序（数组）储结构、链式储结构、索引储结构、散列储结构二、二叉树相关性质结点的度：一个结点的子树的个数记为该结点的度.*树的度：所有节点中度数最大的结节的度数，叶子节点的度为零。*树的高度：一棵树的最大层次数记为树的高度 （或深度）。有序（无序）树：若将树中结点的各子树看成是从左到右具有次序的，即不能交换，则称该树为有序树。否则称为无序树。二叉树第i层（i > 1） 上至多有2A（i-1）个节点。深度为k的二叉树至多有2Ak-1个节点（k

2、> 1）。*对任何一棵二叉，若叶子节点数为nO,度为2的节点数为n2,则n0=n2+1。具有n个节点的完全二叉树的深度为（炯2An）（向下取整）+1。对一棵有n个节点的完全二叉树的节点按层次从上到下，自左至右进行编号，则对任一节点i（1 <i <n）有：若i=1 ,则节点i是二叉树的根，无 双亲；若i>1，贝U其双亲为i/2（向下取整）。若2i>n，贝U节点i没有孩 子节点，否则其左孩子为2i。若2i+1>n，则节点i没有右孩子，否则其 右孩子为2i+1 o*若深度为k的二叉树有2Ak-1个节点，则称其为满二叉树。满二叉树是一 棵完全二叉树。（b）宪全:*对

3、于完全二叉树中，度为1的节点个数只可能为1个或0个«对于二叉树，如果叶子节点数为 nO,度为1的节点数为n 1,度为2的节 点数为n2,则节点总数n = nO + n1 + n2 。*对于任意树，总节点数=每个节点度数和+ 1二叉树的高度等于根与最远叶节点（具有最多祖先的节点）之间分支数目。 空树的高度是-1。只有单个元素的二叉树，其高度为 0。1）5/2二？取比阳空b的最犬整数.第果畑2）5/2 = ?取比5赵大的摄小整数，结果为33）5/2=7要看上下文作若的约定了.一股指地都是向下軀整.三、二叉树的遍历遍历是按某种策略访问树中的每个节点，且仅访问一次。（一）二叉树结构实现Jav

4、a代码.5.package tree.b in tree;/*由于二叉树的节点增加没有什么规则，所以这里只是简单的使用了递6. *次性把整棵树创建出来，而没有设计出一个一个添加节点的方法与删 除7. *8. * author jzj9. * date 2009-12-2310. */11. public class BinTree / Bin=Binary（二进位的,二元的）12.12. protected En try root;/根13. private int size;/树的节点数15.14. /*15. *树的节点结构16. * author jzj17. * date

5、 2009-12-2318. */0.61.protected static class Entry int elem;/ 数据域，这里我们作为编号Entry left;/ 左子树Entry right;/ 右子树public Entry(int elem) this.elem = elem;public String toString() return &qu

6、ot; 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

7、) size+;Entry rootNode = new Entry(num);/ 根节点/ 如果有左子树则创建左子树if (num * 2 <= nodeCount) 2, noderootNode.left = recurCreateFullBiTree(num * Count);/ 如果还可以创建右子树，则创建if (num * 2 + 1 <= nodeCount) rootNode.right = recurCreateFullBiTree(num * + 1, nodeCount);return (Entry) rootNode;262.63. /*64. *根据给定的

8、数组创建一棵树，这个棵树可以是完全二叉树也可是普通二叉树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

9、，则不创建76. * return TreeNode返回创建的节点，最终会返回树的根节点77. */78. private Entry recurCreateBinTree(int nums, int index) 79. / 指定索引上的编号不为零上才需创建节点80. if (numsindex !=0) 81. size+;82. Entry rootNode = new Entry(numsindex);/根节点83. /如果有左子树则创建左子树84. if (index +1) * 2 <= nums.length) 85. rootNode.left = (Entry) rec

10、urCreateBinTree(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. / 取树

11、的最左边的节点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(bi

12、nTree.size();/15117. System.out.println(binTree.getLast();/15118.119. / 创建一个完全二叉树120. binTree = new BinTree();121. binTree.createFullBiTree( 14);122. System.out.println(binTree.size();/14123. System.out.println(binTree.getLast();/7124.125. / 创建一棵非完全二叉树126. binTree = new BinTree();127. int nums = new

13、 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();/8130. System.out.println(binTree.getLast();/8131.132. 133. （二）利用二叉树本身特点进行递归遍历（属内部遍 历）由于二叉树所具有的递归性质， 一棵非空的二叉树可以看作是由根节点、 左子树 和右子树 3 部分构成，因为若能依次遍历这 3部分的信息，也就遍历了整个二叉树。按照左子树的遍历在右子树的遍

14、历之前进行的约定， 根据访问根节点位置的 不同，可以得到二叉的前序、中序、后序 3 种遍历方法。Java 代码1. package tree.bintree;2.3./*4. * 二叉树的三种 内部 遍历：前序、中序、后序5. * 但不管是哪种方式，左子树的遍历在右子树的遍历之前遍历是这有 种遍历方式都6. * 必须遵循的约定7. * author jzj8. * date 2009-12-239. */10. public class BinTreeInOrder extends BinTree 11.12. /*13. * 节点访问者，可根据需要重写 visit 方法14. */15. s

15、tatic 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. / 如果传进来

16、的节点不为空， 则遍历， 注，叶子节点的子节点为 null31.if (node != null) 32.v.visit(node.elem);/33.preOrder(v, node.left);/34.preOrder(v, node.right);/35.36.37.先遍历父节点 再遍历左节点 最后遍历右节点7.78.public void inOrder

17、(Visitor v) inOrder(v, root);/* 树的中序递归遍历 in=infix（ 中缀 ）* param node要遍历的节点*/private void inOrder(Visitor v, Entry node) / 如果传进来的节点不为空，则遍历，注，叶子节点的子节点为nullif (node != null) inOrder(v, node.left);/先遍历左节点v.visit(node.elem);/再遍历父节点inOrder(v, node.right);/最后遍历右节点public void postOrder(Visitor v) postOrder(v

18、, 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

19、 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);79. System.out.print(" 前序遍历 - ");80. treeOrder.preOrder(new Visitor() 81. );82. System.out.println();83. System.out.print(" 中序遍历 - ");84. tre

20、eOrder.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 893. *中序遍历 - 4 6 2 1 3 7 5 894. * 后序遍历 - 6 4 2 7 8 5 3 195. */96. 97. 三）二叉树的非递归遍历（属外部遍历）1、利用栈与队列对二叉树进行非递归遍历J

21、ava 代码1. package tree.bintree;2.3. import java.util.Iterator;4. import java.util.LinkedList;5. import java.util.Stack;./*二叉树的外部遍历：深度优先（先根）、广度（层次）优先遍历10. * author jzj11. * date 2009-12-2312. */13. public class BinTreeOutOrder extends BinTree 14.15. /*16. * 二叉树深序优先遍历（即二叉树的先根遍历）迭代器，外部可以 使用该迭代器17

22、.4.55.*进行非递归的遍历， 这是一种在二叉树结构外部的一种遍历算法，它没有使用* 二叉树本身的结构特点(左右子树递归)进行递归遍历* author jzj*/private class DepthOrderIterator implements Iterator / 栈里存放的是每个节点 private Stack stack = new Stack();public De

23、pthOrderIterator(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) st

24、ack.push(treeNode.right);/ 点八、if (treeNode.left != null) stack.push(treeNode.left);/ 点，但访问先于右节点 / 返回遍历得到的节点 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 Itera

25、tor返回先根遍历迭代器72. */73. public Iterator createPreOrderItr() 74. return new DepthOrderIterator(root);75. 76.77. /*78. * 二叉树广度优先遍历迭代器，外部可以使用该迭代器79. * 进行非递归的遍历， 这是一种在二叉树结构外部的一种遍历算法， 它没有使用80. * 二叉树本身的结构特点(左右子树递归)进行递归遍历81. * author jzj82. */83. private class LevelOrderIterator implements Iterator 84. / 使用队

26、列结构实现层次遍历，队列里存储的为节点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.

27、 / 取下一个元素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.11

28、6./返回遍历得到的节点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 n

29、ew LevelOrderIterator(root);137. 138.139.public static void main(String args) 140.141./ 创建一棵满二叉树BinTreeOutOrder treeOrder = new BinTreeOutOrder();142.143.(、treeOrder.createFullBiTree( 15);Iterator preOrderItr = treeOrder.createPreOrderItr();144. 145. 146.System.out.print(" 深度优先(先根)遍历 - ");

30、 while (preOrderItr.hasNext() System.out.print(Entry) preOrderItr.next().elem + " "50.rItr();151.152.System.out.println();System.out.print(" 广度优先(层次)遍历 - "); Iterator layerOrderItr = treeOrder.createLayerOrdewhile (layerOrderItr.hasNext() System.out.print(Entry) laye

31、rOrderItr.next().elem + " "56./* output:* 深度优先（先根）遍历 - 1 2 4 8 9 5 10 11 3 6 12 13 7 14 15157.* 广度优先（层次）遍历 - 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15158. */159. 160. 2、利用二叉树节点的父节点指针进行非递归遍历要想采用非递归的方法遍历树， 又不借助于前面的队列与栈， 我们需要该树是一 棵可回溯的二叉树， 即从子节点要能够知道他的父节点及祖先节点， 与前面的二 叉树不同的是， 树的节点结构体中多一

32、个指向父的节点指针， 这样外界可以以非 递归的方式来遍历二叉树了 。Java 代码1. package tree.bintree;2.3. /*4. *5. * 可回溯的二叉树6. * 二叉树的非递归遍历7. *8. * author jzj9. * date 2009-12-2310. */11. public class BackBinTree / Bin=Binary(二进位的 , 二元的 )12.13. protected Entry root;/ 根14. private int size;/ 树的节点数15.16. /*17. * 树的节点结构18. * author jzj19.

33、 * date 2009-12-2320. */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. * 查找

34、前序遍历(根左右)直接后继节点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. / 否则如果右

35、子树不为空，则直接后继为右子节点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. *5061. */62. *37 7563. */

36、/64. *25 68./ /15 30 55 68 / 28 32 5969.3670.71. */72. while (s != null && (c = s.right | s.right = null) 73. c = s;74. s = s.paraent;75. 76. /退出循环时 s 可以为 null ，比如查找 68 节点的直接后继时退出循环时 s=null77. if (s = null) 78. return null;79. else 80. return s.right;81. 82. 83. 84.85. /*86. *查找前序

37、遍历(根左右)直接前驱节点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.

38、 / 如果节点为父节点的右节点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.108.*一下 75 直接前驱节点，应该是 36109.*110.*50111.*/112.*37 75113.*/ /114.*25 61115.*/ /116.

39、*15 30 55 68117.*/ 118.*28 32 59119.*120.*36121.*/122.123.while (s.left != null | s.right != null)/在父节点的左子节点的子树中查找时定要先向右边拐106.107. * 只要父节点左子节点还有子节点，则前驱节点 要从其子树中找。请试着找124.125.126.拐127.如果右边没有，然后才能向左边if (s.right != null) s = s.right; else /s = s.left;128. 129. 130. 131. return s;132. else /如果是根节点，则没有直接

40、前驱节点了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.para

41、ent != 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. *要从其子树中找，只要父节点右

42、子节点还有子节点，则后断节点64.165.如 15 的后继节点为 2850/37 75/ /25 61/ /15 30 55 6872.173.*/ *28 32 59*36*/while (s.left != null | s.right != null)/ 在父节点的右子节点的子树中查找时，一定要先向左边拐174.175.176.拐95.196.1

43、00.201.空202.点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;/ 如果右子树不为空

44、，则直接前驱为右子节点else if (e.right != null) / 先看右子节点是否为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 的右子树，且为空。请试着找一下 59 与 15 节点的213.* 直接后继节点， 59 的应

45、该是 37，而节点了214.*215.* 50216.* /217.* 37 75218.* / /219.* 25 61220.* / /221.* 15 30 55 68222.* / 223.* 28 32 59224.* 225.* 36226.*/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;38.2

46、39./*240.* 查找中序遍历（左根右）直接后继节点241.*242.* 以非递归 左根右 的方式遍历树243.*244.* param e 需要查找哪个节点的直接后继节点245.* return Entry 中序遍历直接后继节点s 的左子树不15则没有后继246. */247. public Entry inOrderSuccessor(Entry e) 248. if (e = null) 249. return null;250. / 如果待找的节点有右子树，则在右子树上查找251. else if (e.right != null) 252. / 默认后继节点为右子节点(如果右子节

47、点没有左子 树时即为该节点)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;/当前节点， 如果其父不为后继，则下次指向父节点2

48、64. / 如果待查节点为父节点的右节点时，继续向上找，一直要找到 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 中序遍历直接前驱

49、节点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.

50、 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 =

51、 p;301. p = p.paraent;302. 303. return p;304. 305. 306.307. /*308. * 查找指定的节点309. * param num310. * return Entry311. */312. public Entry getEntry(int num) 313. return getEntry(root, num);314. 315.316. /*317. * 使用树的先序遍历递归方式查找指定的节点318. *319. * param entry320. * param num321. * return322.323.324.325.*/ p