Java实现二叉树的多种遍历 - 执念saying

  • Z时代
  • 2024-01-10
  • 分类：综合

java

Java实现二叉树的多种遍历

简述：

用Java实现二叉树的前序，中序，后序，层序遍历, S型层序遍历

算法简述：

前三个算法在于输出当前节点的位置，

1 前序： 在递归左右儿子之前，输出当前节点

[java] view plain copy

  1. void PreOrderPrint(){  

  2.     System.out.print(value.toString() + " ");  

  3. if(left != null)  

  4.         left.PreOrderPrint();  

  5. if(right != null)  

  6.         right.PreOrderPrint();  

  7. } 

2 中序：在递归左右儿子中间，输出

[java] view plain copy

  1. void InOrderPrint(){  

  2. if(left != null)  

  3.         left.InOrderPrint();  

  4.     System.out.print(value.toString() + " ");  

  5. if(right != null)  

  6.         right.InOrderPrint();  

  7. } 

后序：在递归左右儿子之后输出

[java] view plain copy

  1. void PostOrderPrint(){  

  2. if(left != null)  

  3.         left.PostOrderPrint();  

  4. if(right != null)  

  5.         right.PostOrderPrint();  

  6.     System.out.print(value.toString() + " ");  

  7. } 

3 层序遍历，这里的实现方式类似于两个簸箕（queue1 和 queue2)之间互相倒，知道谁都没有后继节点位置，即两个簸箕都为空，此处是两个队列都为空

[java] view plain copy

  1. void LevelOrderPrint(){  

  2. if(this == null)  

  3. throw new IllegalArgumentException("null node !");  

  4.     Queue<Node<E>> queue1 = new LinkedList<Node<E>>();  

  5.     Queue<Node<E>> queue2 = new LinkedList<Node<E>>();  

  6.     queue1.add(this);  

  7. while(!queue1.isEmpty() || !queue2.isEmpty()){  

  8. if(queue2.isEmpty()){  

  9. while(!queue1.isEmpty()){  

  10.                 Node<E> currentNode = queue1.poll();  

  11.                 System.out.print(currentNode.value.toString() + " ");  

  12. if(currentNode.left != null){  

  13.                     queue2.add(currentNode.left);  

  14.                 }  

  15. if(currentNode.right != null){  

  16.                     queue2.add(currentNode.right);  

  17.                 }  

  18.             }  

  19.         }  

  20. else{  

  21. while(!queue2.isEmpty()){  

  22.                 Node<E> currentNode = queue2.poll();  

  23.                 System.out.print(currentNode.value.toString() + " ");  

  24. if(currentNode.left != null){  

  25.                     queue1.add(currentNode.left);  

  26.                 }  

  27. if(currentNode.right != null){  

  28.                     queue1.add(currentNode.right);  

  29.                 }  

  30.             }  

  31.         }  

  32.         System.out.println();  

  33.     }  

  34. } 

4  S型层序遍历，就是把上面使用的queue换为stack，注意左右子节点添加顺序，就可以了

[java] view plain copy

  1. //Print By Level S-style

  2. public void S_LevelOrderPrint(){  

  3.     Stack<Node<E>> stack1 = new Stack<Node<E>>();  

  4.     Stack<Node<E>> stack2 = new Stack<Node<E>>();  

  5.     stack1.add(this);  

  6. while(!stack1.isEmpty() || !stack2.isEmpty()){  

  7. if(stack1.isEmpty()){  

  8. while(!stack2.isEmpty()){  

  9.                 Node<E> currentNode = stack2.pop();  

  10.                 System.out.print(currentNode.value + " ");  

  11. if(currentNode.left != null)  

  12.                     stack1.push(currentNode.left);  

  13. if(currentNode.right != null)  

  14.                     stack1.push(currentNode.right);  

  15.             }  

  16.         }else{  

  17. while(!stack1.isEmpty()){  

  18.                 Node<E> currentNode = stack1.pop();  

  19.                 System.out.print(currentNode.value + " ");  

  20. if(currentNode.right != null)  

  21.                     stack2.add(currentNode.right);  

  22. if(currentNode.left != null)  

  23.                     stack2.add(currentNode.left);  

  24.             }  

  25.         }  

  26.         System.out.println();  

  27.     }  

  28. } 

下面是主要代码，包括测试代码

代码：

[java] view plain copy

  1. package offer;  

  2. import java.util.LinkedList;  

  3. import java.util.Queue;  

  4. import java.util.Stack;  

  5. class Node<E extends Comparable<E>>{  

  6.     Node<E> left;  

  7.     Node<E> right;  

  8.     E value;  

  9.     Node(){  

  10.         left = null;  

  11.         right = null;  

  12.         value = null;  

  13.     }  

  14.     Node(E value){  

  15. this.value = value;  

  16.         left = null;  

  17.         right = null;  

  18.     }  

  19. void PreOrderPrint(){  

  20.         System.out.print(value.toString() + " ");  

  21. if(left != null)  

  22.             left.PreOrderPrint();  

  23. if(right != null)  

  24.             right.PreOrderPrint();  

  25.     }  

  26. void InOrderPrint(){  

  27. if(left != null)  

  28.             left.InOrderPrint();  

  29.         System.out.print(value.toString() + " ");  

  30. if(right != null)  

  31.             right.InOrderPrint();  

  32.     }  

  33. void PostOrderPrint(){  

  34. if(left != null)  

  35.             left.PostOrderPrint();  

  36. if(right != null)  

  37.             right.PostOrderPrint();  

  38.         System.out.print(value.toString() + " ");  

  39.     }  

  40. //Print By Level

  41. void LevelOrderPrint(){  

  42. if(this == null)  

  43. throw new IllegalArgumentException("null node !");  

  44.         Queue<Node<E>> queue1 = new LinkedList<Node<E>>();  

  45.         Queue<Node<E>> queue2 = new LinkedList<Node<E>>();  

  46.         queue1.add(this);  

  47. while(!queue1.isEmpty() || !queue2.isEmpty()){  

  48. if(queue2.isEmpty()){  

  49. while(!queue1.isEmpty()){  

  50.                     Node<E> currentNode = queue1.poll();  

  51.                     System.out.print(currentNode.value.toString() + " ");  

  52. if(currentNode.left != null){  

  53.                         queue2.add(currentNode.left);  

  54.                     }  

  55. if(currentNode.right != null){  

  56.                         queue2.add(currentNode.right);  

  57.                     }  

  58.                 }  

  59.             }  

  60. else{  

  61. while(!queue2.isEmpty()){  

  62.                     Node<E> currentNode = queue2.poll();  

  63.                     System.out.print(currentNode.value.toString() + " ");  

  64. if(currentNode.left != null){  

  65.                         queue1.add(currentNode.left);  

  66.                     }  

  67. if(currentNode.right != null){  

  68.                         queue1.add(currentNode.right);  

  69.                     }  

  70.                 }  

  71.             }  

  72.             System.out.println();  

  73.         }  

  74.     }  

  75. //Print By Level S-style

  76. public void S_LevelOrderPrint(){  

  77.         Stack<Node<E>> stack1 = new Stack<Node<E>>();  

  78.         Stack<Node<E>> stack2 = new Stack<Node<E>>();  

  79.         stack1.add(this);  

  80. while(!stack1.isEmpty() || !stack2.isEmpty()){  

  81. if(stack1.isEmpty()){  

  82. while(!stack2.isEmpty()){  

  83.                     Node<E> currentNode = stack2.pop();  

  84.                     System.out.print(currentNode.value + " ");  

  85. if(currentNode.left != null)  

  86.                         stack1.push(currentNode.left);  

  87. if(currentNode.right != null)  

  88.                         stack1.push(currentNode.right);  

  89.                 }  

  90.             }else{  

  91. while(!stack1.isEmpty()){  

  92.                     Node<E> currentNode = stack1.pop();  

  93.                     System.out.print(currentNode.value + " ");  

  94. if(currentNode.right != null)  

  95.                         stack2.add(currentNode.right);  

  96. if(currentNode.left != null)  

  97.                         stack2.add(currentNode.left);  

  98.                 }  

  99.             }  

  100.             System.out.println();  

  101.         }  

  102.     }  

  103. }  

  104. class BinarySearchTree<E extends Comparable<E>>{  

  105. private Node<E> root;  

  106. public Node<E> getRoot(){  

  107. return root;  

  108.     }  

  109.     BinarySearchTree(){  

  110.         root = null;  

  111.     }  

  112. public void InsertNode(E value){  

  113. if(root == null){  

  114.             root = new Node<E>(value);  

  115. return;  

  116.         }  

  117.         Node<E> currentNode = root;  

  118. while(true){  

  119. if(value.compareTo(currentNode.value) > 0){  

  120. if(currentNode.right == null){  

  121.                     currentNode.right = new Node<E>(value);  

  122. break;  

  123.                 }  

  124.                 currentNode = currentNode.right;  

  125.             }else{  

  126. if(currentNode.left == null){  

  127.                     currentNode.left = new Node<E>(value);  

  128. break;  

  129.                 }  

  130.                 currentNode = currentNode.left;  

  131.             }  

  132.         }  

  133.     }  

  134. }  

  135. public class LevelPrintOfBinaryTree<E extends Comparable<E>> {  

  136. public static void main(String[] args) {  

  137.         BinarySearchTree<Integer> tree = new BinarySearchTree<Integer>();  

  138.         {  

  139.             tree.InsertNode(4);  

  140.             tree.InsertNode(2);  

  141.             tree.InsertNode(1);  

  142.             tree.InsertNode(3);  

  143.             tree.InsertNode(6);  

  144.             tree.InsertNode(5);  

  145.             tree.InsertNode(7);  

  146.             tree.InsertNode(8);  

  147.         }  

  148.         System.out.print("PreOrderPrint: ");  

  149.         tree.getRoot().PreOrderPrint();  

  150.         System.out.print("\nInOrderPrint: ");  

  151.         tree.getRoot().InOrderPrint();  

  152.         System.out.print("\nPostOrderPrint: ");  

  153.         tree.getRoot().PostOrderPrint();  

  154.         System.out.println("\nLevelOrderPrint: ");  

  155.         tree.getRoot().LevelOrderPrint();  

  156.         System.out.println("\nS_LevelOrderPrint: ");  

  157.         tree.getRoot().S_LevelOrderPrint();  

  158.     }  

  159. } 

 

输入测试的树：

输出：

来源： http://blog.csdn.net/anialy/article/details/8145114

以上是 Java实现二叉树的多种遍历 - 执念saying 的全部内容， 来源链接： utcz.com/z/391109.html

回到顶部