Java实现二叉树的遍历.doc

一、数据结构分类（一）按逻辑结构1. 集合(无辑关系) 2. 线性结构(线性表)：数组、链表、栈、队列 3. 非线性结构：树、图、多维数组 （二）按存储结构顺序（数组）储结构、链式储结构、索引储结构、散列储结构 二、二叉树相关性质 结点的度：一个结点的子树的个数记为该结点的度 树的度：所有节点中度数最大的结节的度数，叶子节点的度为零。 树的高度：一棵树的最大层次数记为树的高度(或深度)。 有序(无序)树：若将树中结点的各子树看成是从左到右具有次序的，即不能交换，则称该树为有序树。否则称为无序树。 二叉树第i层（i1）上至多有2(i-1)个节点。 深度为k的二叉树至多有2k-1个节点（k1）。 对任何一棵二叉，若叶子节点数为n0，度为2的节点数为n2，则n0=n2+1。 具有n个节点的完全二叉树的深度为 (2n)(向下取整)+1。 对一棵有n个节点的完全二叉树的节点按层次从上到下，自左至右进行编号，则对任一节点i(1in)有：若 i=1，则节点i是二叉树的根，无双亲；若 i1，则其双亲为 i/2(向下取整)。若2in，则节点i没有孩子节点，否则其左孩子为2i。若2i+1n，则节点i没有右孩子，否则其右孩子为2i+1。 若深度为k的二叉树有2k-1个节点，则称其为满二叉树。满二叉树是一棵完全二叉树。 对于完全二叉树中，度为1的节点个数只可能为1个或0个。 对于二叉树，如果叶子节点数为n0，度为1的节点数为n1，度为2的节点数为n2，则节点总数n = n0 + n1 + n2。 对于任意树，总节点数 = 每个节点度数和 + 1 二叉树的高度等于根与最远叶节点（具有最多祖先的节点）之间分支数目。空树的高度是-1。只有单个元素的二叉树，其高度为0。.三、二叉树的遍历遍历是按某种策略访问树中的每个节点，且仅访问一次。 （一） 二叉树结构实现Java代码1. packagetree.bintree;2. /* 3. *创建非完全二叉树、完全二叉树、满二叉树 4. * 5. *由于二叉树的节点增加没有什么规则，所以这里只是简单的使用了递一 6. *次性把整棵树创建出来，而没有设计出一个一个添加节点的方法与删除 7. * 8. *authorjzj 9. *date2009-12-23 10. */11. publicclassBinTree/Bin=Binary(二进位的,二元的) 12. 13. protectedEntryroot;/根 14. privateintsize;/树的节点数 15. 16. /* 17. *树的节点结构 18. *authorjzj 19. *date2009-12-23 20. */21. protectedstaticclassEntry 22. intelem;/数据域，这里我们作为编号 23. Entryleft;/左子树 24. Entryright;/右子树 25. 26. publicEntry(intelem) 27. this.elem=elem; 28. 29. 30. publicStringtoString() 31. returnnumber=+elem; 32. 33. 34. 35. /* 36. *根据给定的节点数创建一个完全二叉树或是满二叉树 37. *paramnodeCount要创建节点总数 38. */39. publicvoidcreateFullBiTree(intnodeCount) 40. root=recurCreateFullBiTree(1,nodeCount); 41. 42. 43. /* 44. *递归创建完全二叉树 45. *paramnum节点编号 46. *paramnodeCount节点总数 47. *returnTreeNode返回创建的节点 48. */49. privateEntryrecurCreateFullBiTree(intnum,intnodeCount) 50. size+; 51. EntryrootNode=newEntry(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. *paramnums数组中指定了要创建的节点的编号，如果为0，表示不创建 67. */68. publicvoidcreateBinTree(intnums) 69. root=recurCreateBinTree(nums,0); 70. 71. 72. /* 73. *递归创建二叉树 74. *paramnums数组中指定了要创建的节点的编号，如果为0，表示不创建 75. *paramindex需要使用数组中的哪个元素创建节点，如果为元素为0，则不创建 76. *returnTreeNode返回创建的节点，最终会返回树的根节点 77. */78. privateEntryrecurCreateBinTree(intnums,intindex) 79. /指定索引上的编号不为零上才需创建节点 80. if(numsindex!=0) 81. size+; 82. EntryrootNode=newEntry(numsindex);/根节点 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. returnnull; 94. 95. 96. 97. publicintsize() 98. returnsize; 99. 100. 101. /取树的最左边的节点 102. publicintgetLast() 103. Entrye=root; 104. while(e.right!=null) 105. e=e.right; 106. 107. returne.elem; 108. 109. 110. /测试 111. publicstaticvoidmain(Stringargs) 112. 113. /创建一个满二叉树 114. BinTreebinTree=newBinTree(); 115. binTree.createFullBiTree(15); 116. System.out.println(binTree.size();/15 117. System.out.println(binTree.getLast();/15 118. 119. /创建一个完全二叉树 120. binTree=newBinTree(); 121. binTree.createFullBiTree(14); 122. System.out.println(binTree.size();/14 123. System.out.println(binTree.getLast();/7 124. 125. /创建一棵非完全二叉树 126. binTree=newBinTree(); 127. intnums=newint1,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 (numsindex != 0) size+;Entry rootNode = new Entry(numsindex);/根节点/如果有左子树则创建左子树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();/15System.out.println(binTree.getLast();/15/创建一个完全二叉树binTree = new BinTree();binTree.createFullBiTree(14);System.out.println(binTree.size();/14System.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();/8System.out.println(binTree.getLast();/8（二）利用二叉树本身特点进行递归遍历（属内部遍历）由于二叉树所具有的递归性质，一棵非空的二叉树可以看作是由根节点、左子树和右子树3部分构成，因为若能依次遍历这3部分的信息，也就遍历了整个二叉树。按照左子树的遍历在右子树的遍历之前进行的约定，根据访问根节点位置的不同，可以得到二叉的前序、中序、后序3种遍历方法。 Java代码1. packagetree.bintree; 2. 3. /* 4. *二叉树的三种内部遍历：前序、中序、后序 5. *但不管是哪种方式，左子树的遍历在右子树的遍历之前遍历是这有三种遍历方式都 6. *必须遵循的约定 7. *authorjzj 8. *date2009-12-23 9. */10. publicclassBinTreeInOrderextendsBinTree 11. 12. /* 13. *节点访问者，可根据需要重写visit方法 14. */15. staticabstractclassVisitor 16. voidvisit(Objectele) 17. System.out.print(ele+); 18. 19. 20. 21. publicvoidpreOrder(Visitorv) 22. preOrder(v,root); 23. 24. 25. /* 26. *树的前序递归遍历pre=prefix(前缀) 27. *paramnode要遍历的节点 28. */29. privatevoidpreOrder(Visitorv,Entrynode) 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. publicvoidinOrder(Visitorv) 39. inOrder(v,root); 40. 41. 42. /* 43. *树的中序递归遍历in=infix(中缀) 44. *paramnode要遍历的节点 45. */46. privatevoidinOrder(Visitorv,Entrynode) 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. publicvoidpostOrder(Visitorv) 56. postOrder(v,root); 57. 58. 59. /* 60. *树的后序递归遍历post=postfix(后缀) 61. *paramnode要遍历的节点 62. */63. privatevoidpostOrder(Visitorv,Entrynode) 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. publicstaticvoidmain(Stringargs) 74. 75. /创建二叉树 76. intnums=newint1,2,3,4,0,0,5,0,6,0,0,0,0,7,8; 77. BinTreeInOrdertreeOrder=newBinTreeInOrder(); 78. treeOrder.createBinTree(nums); 79. System.out.print(前序遍历-); 80. treeOrder.preOrder(newVisitor() 81. ); 82. System.out.println(); 83. System.out.print(中序遍历-); 84. treeOrder.inOrder(newVisitor() 85. ); 86. System.out.println(); 87. System.out.print(后序遍历-); 88. treeOrder.postOrder(newVisitor() 89. ); 90. /* 91. *output: 92. *前序遍历-12463578 93. *中序遍历-46213758 94. *后序遍历-64278531 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) /如果传进来的节点不为空，则遍历，注，叶子节点的子节点为nullif (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) /如果传进来的节点不为空，则遍历，注，叶子节点的子节点为nullif (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) /如果传进来的节点不为空，则遍历，注，叶子节点的子节点为nullif (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. packagetree.bintree; 2. 3. importjava.util.Iterator; 4. importjava.util.LinkedList; 5. importjava.util.Stack; 6. 7. /* 8. *二叉树的外部遍历：深度优先（先根）、广度（层次）优先遍历 9. * 10. *authorjzj 11. *date2009-12-23 12. */13. publicclassBinTreeOutOrderextendsBinTree 14. 15. /* 16. *二叉树深序优先遍历（即二叉树的先根遍历）迭代器，外部可以使用该迭代器 17. *进行非递归的遍历，这是一种在二叉树结构外部的一种遍历算法，它没有使用 18. *二叉树本身的结构特点（左右子树递归）进行递归遍历 19. *authorjzj 20. */21. privateclassDepthOrderIteratorimplementsIterator 22. /栈里存放的是每个节点 23. privateStackstack=newStack(); 24. 25. publicDepthOrderIterator(Entrynode) 26. 27. /根入栈，但在放入左右子节点前会马上出栈，即根先优于左右子节点访问 28. stack.push(node); 29. 30. 31. 32. /是否还有下一个元素 33. publicbooleanhasNext() 34. if(stack.isEmpty() 35. returnfalse; 36. 37. returntrue; 38. 39. 40. /取下一个元素 41. publicEntrynext() 42. if(hasNext() 43. /取栈顶元素 44. EntrytreeNode=(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. returntreeNode; 56. 57. else 58. /如果栈为空 59. returnnull; 60. 61. 62. 63. publicvoidremove() 64. thrownewUnsupportedOperationException(); 65. 66. 67. 68. 69. /* 70. *向外界提供先根遍历迭代器 71. *returnIterator返回先根遍历迭代器 72. */73. publicIteratorcreatePreOrderItr() 74. returnnewDepthOrderIterator(root); 75. 76. 77. /* 78. *二叉树广度优先遍历迭代器，外部可以使用该迭代器 79. *进行非递归的遍历，这是一种在二叉树结构外部的一种遍历算法，它没有使用 80. *二叉树本身的结构特点（左右子树递归）进行递归遍历 81. *authorjzj 82. */83. privateclassLevelOrderIteratorimplementsIterator 84. /使用队列结构实现层次遍历，队列里存储的为节点 85. privateLinkedListqueue=newLinkedList(); 86. 87. publicLevelOrderIterator(Entrynode) 88. 89. if(node!=null) 90. /将根入队 91. queue.addLast(node); 92. 93. 94. 95. /是否还有下一个元素 96. publicbooleanhasNext() 97. if(queue.isEmpty() 98. returnfalse; 99. 100. returntrue; 101. 102. 103. /取下一个元素 104. publicEntrynext() 105. if(hasNext() 106. /取栈顶迭元素 107. EntrytreeNode=(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. returntreeNode; 118. 119. else 120. /如果队列为空 121. returnnull; 122. 123. 124. 125. publicvoidremove() 126. thrownewUnsupportedOperationException(); 127. 128. 129. 130. 131. /* 132. *向外界提供广度优先迭代器 133. *returnIterator返回遍历迭代器 134. */135. publicIteratorcreateLayerOrderItr() 136. returnnewLevelOrderIterator(root); 137. 138. 139. publicstaticvoidmain(Stringargs) 140. /创建一棵满二叉树 141. BinTreeOutOrdertreeOrder=newBinTreeOutOrder(); 142. treeOrder.createFullBiTree(15); 143. IteratorpreOrderItr=treeOrder.createPreOrderItr(