Go语言视频零基础入门到精通

javalearner

二叉树的层次遍历(广度优先遍历)

1. import java.util.*;   
   
2.   
   
3. public class BinaryTree {   
   
4.     protected Node root;   
   
5.   
   
6.     public BinaryTree(Node root) {   
   
7.         this.root = root;   
   
8.     }   
   
9.   
   
10.     public Node getRoot() {   
    
11.         return root;   
    
12.     }   
    
13.   
    
14.     /** 构造树 */  
    
15.     public static Node init() {   
    
16.         Node a = new Node("A");   
    
17.         Node b = new Node("B", null, a);   
    
18.         Node c = new Node("C");   
    
19.         Node d = new Node("D", b, c);   
    
20.         Node e = new Node("E");   
    
21.         Node f = new Node("F", e, null);   
    
22.         Node g = new Node("G", null, f);   
    
23.         Node h = new Node("H", d, g);   
    
24.         return h;// root   
    
25.     }   
    
26.   
    
27.     /** 访问节点 */  
    
28.     public static void visit(Node p) {   
    
29.         System.out.print(p.getKey() + " ");   
    
30.     }   
    
31.   
    
32.     /** 递归实现前序遍历 */  
    
33.      static void preorder(Node p) {   
    
34.         if (p != null) {   
    
35.             visit(p);   
    
36.             preorder(p.getLeft());   
    
37.             preorder(p.getRight());   
    
38.         }   
    
39.     }   
    
40.   
    
41.     /** 递归实现中序遍历 */  
    
42.      static void inorder(Node p) {   
    
43.         if (p != null) {   
    
44.             inorder(p.getLeft());   
    
45.             visit(p);   
    
46.             inorder(p.getRight());   
    
47.         }   
    
48.     }   
    
49.   
    
50.     /** 递归实现后序遍历 */  
    
51.      static void postorder(Node p) {   
    
52.         if (p != null) {   
    
53.             postorder(p.getLeft());   
    
54.             postorder(p.getRight());   
    
55.             visit(p);   
    
56.         }   
    
57.     }   
    
58.    /** 层次遍历*/
    
59.    static void levelorder(Node p){   
    
60.         if(p==null) return;   
    
61.         Queue< Node> queue=new LinkedList< Node>();   
    
62.         queue.offer(p);   
    
63.         while(queue.size()>0){   
    
64.             Node temp=queue.poll();   
    
65.             visit(temp);
    
66.             if(temp.getLeft()!=null){   
    
67.                 queue.offer(temp.getLeft());   
    
68.             }   
    
69.             if(temp.getRight()!=null){   
    
70.                 queue.offer(temp.getRight());   
    
71.             }   
    
72.         }   
    
73.       
    
74.     }   
    
75.   
    
76.   
    
77.     // 求二叉树的高度
    
78. static int height(Node tree) {
    
79.     if (tree == null)
    
80.         return 0;
    
81.     else {
    
82.         int leftTreeHeight = height(tree.getLeft());
    
83.         int rightTreeHeight = height(tree.getRight());;
    
84.         return leftTreeHeight > rightTreeHeight ? leftTreeHeight + 1: rightTreeHeight + 1;
    
85.     }
    
86. }
    
87. // 求二叉树的结点总数
    
88.   static int nodes(Node tree) {
    
89.    if (tree == null)
    
90.         return 0;
    
91.    else {
    
92.         int left = nodes(tree.getLeft());
    
93.         int right = nodes(tree.getRight());
    
94.         return left + right + 1;
    
95.   }
    
96. }
    
97. // 求二叉树叶子节点的总数
    
98. static int leaf(Node tree) {
    
99.    if (tree == null)
    
100.         return 0;
     
101.    else {
     
102.         int left = leaf(tree.getLeft());
     
103.         int right = leaf(tree.getRight());
     
104.         if (tree.getLeft() == null && tree.getRight() == null)
     
105.                 return left + right + 1;
     
106.         else
     
107.                 return left + right;
     
108.     }
     
109. }
     
110. //将二叉树所有结点的左右子树交换
     
111. static void swapTree(Node root){
     
112.   if(root != null) {
     
113.    Node tmp = root.getLeft();
     
114.    root.setLeft(root.getRight());
     
115.    root.setRight(tmp);
     
116.    swapTree(root.getLeft());
     
117.    swapTree(root.getRight());
     
118.   }
     
119. }
     
120.      /**
     
121.      * getLeafNodes: 递归求解给定二叉树的所有叶子结点
     
122.      * @param root   给定二叉树的根结点
     
123.      * @param leaflist 给定二叉树的所有叶子结点
     
124.      */  
     
125.   static void  getLeafNodes(Node root, List< Node> leaflist)  
     
126.     {  
     
127.         if (root != null) {  
     
128.             if (root.getLeft() == null && root.getRight() == null) {  
     
129.                 leaflist.add(root);  
     
130.                 return ;  
     
131.             }  
     
132.             getLeafNodes(root.getLeft(), leaflist);  
     
133.             getLeafNodes(root.getRight(), leaflist);  
     
134.         }  
     
135.     }  
     
136.   
     
137.   /**
     
138.      * longestPath: 递归求解给定二叉树的一条最长路径 如果有多条，输出其中一条
     
139.      * @param root  给定二叉树的根结点
     
140.      * @param longestPath 存放二叉树的最长路径上的结点
     
141.      */  
     
142.     static void longestPath(Node root, List< Node> longestPath)  
     
143.     {  
     
144.         if (root != null) {  
     
145.             longestPath.add(root);  
     
146.             if (root.getLeft() == null && root.getRight() == null) { // 左右子树均空  
     
147.                  return ;  
     
148.             }  
     
149.          
     
150.                 List< Node> leftLongestPath = new ArrayList< Node>();  
     
151.                 List< Node> rightLongestPath = new ArrayList< Node>();  
     
152.                 longestPath(root.getLeft(), leftLongestPath);  
     
153.                 longestPath(root.getRight(), rightLongestPath);  
     
154.                 if (leftLongestPath.size() >= rightLongestPath.size()) {  
     
155.                     longestPath.addAll(leftLongestPath);  
     
156.                 } else if (leftLongestPath.size() < rightLongestPath.size()) {  
     
157.                     longestPath.addAll(rightLongestPath);  
     
158.                                 
     
159.             }  
     
160.         }  
     
161.     }  
     
162. 
     
163.     /**  
     
164.      * @param args  
     
165.      */  
     
166.     public static void main(String[] args) {   
     
167.         BinaryTree tree = new BinaryTree(init());   
     
168.         System.out.print(" 前序遍历:");   
     
169.         preorder(tree.getRoot());   
     
170.         System.out.println();   
     
171.         System.out.print(" 中序遍历:");   
     
172.         inorder(tree.getRoot());   
     
173.         System.out.println();   
     
174.         System.out.print(" 后序遍历:");   
     
175.         postorder(tree.getRoot());   
     
176.         System.out.println();
     
177.         System.out.println();
     
178.       
     
179.         System.out.println("层次遍历");
     
180.         levelorder(tree.getRoot());
     
181.         System.out.println();   
     
182.         System.out.println();   
     
183.          System.out.println("叶子结点数");
     
184.          System.out.println(leaf(tree.getRoot()));
     
185.          System.out.println("总结点数");
     
186.          System.out.println(nodes(tree.getRoot()));
     
187.          System.out.println("树的高度");
     
188.          System.out.println(height(tree.getRoot()));
     
189.      
     
190.     }   
     
191.   
     
192. }  
     
193. public class Node {   
     
194.     private char key;   
     
195.     private Node left, right;   
     
196.   
     
197.     public Node(char key) {   
     
198.         this(key, null, null);   
     
199.     }   
     
200.   
     
201.     public Node(char key, Node left, Node right) {   
     
202.         this.key = key;   
     
203.         this.left = left;   
     
204.         this.right = right;   
     
205.     }   
     
206.   
     
207.     public char getKey() {   
     
208.         return key;   
     
209.     }   
     
210.   
     
211.     public void setKey(char key) {   
     
212.         this.key = key;   
     
213.     }   
     
214.   
     
215.     public Node getLeft() {   
     
216.         return left;   
     
217.     }   
     
218.   
     
219.     public void setLeft(Node left) {   
     
220.         this.left = left;   
     
221.     }   
     
222.   
     
223.     public Node getRight() {   
     
224.         return right;   
     
225.     }   
     
226.   
     
227.     public void setRight(Node right) {   
     
228.         this.right = right;   
     
229.     }   
     
230. }
     

复制代码

   
     
     
      
      

        
      

        
      
     
   

  


源码下载：http://file.javaxxz.com/2014/11/28/000601468.zip