第五章树与二叉树

4. 层次遍历 ---- BUG FREE

 1 public void levelTraverse(){
 2         BiTreeNode T = root;
 3         if(T != null){
 4             LinkQueue Q = new LinkQueue();
 5             Q.offer(T);
 6             while(! Q.isEmpty()){
 7                 T = (BiTreeNode)Q.peek();
 8                 System.out.print(T.data);
 9                 Q.poll();
10                 if(T.lchild != null){
11                     Q.offer(T.lchild);
12                 }
13                 if(T.rchild != null){
14                     Q.offer(T.rchild);
15                 }
16             }
17         }
18     }

View Code

3. 后根遍历 ----　NOT BUG FREE

 1     public void postRootTraverse(){
 2         BiTreeNode T = root;
 3         if(T != null){
 4             LinkStack S = new LinkStack();
 5             S.push(T);
 6             boolean flag;
 7             BiTreeNode p = null;
 8             while(!S.isEmpty()){
 9                 while(S.peek() != null){
10                     T = (BiTreeNode)S.peek();
11                     S.push(T.lchild);
12                 }
13                 S.pop();
14                 while(!S.isEmpty()){
15                     T = (BiTreeNode)S.peek();
16                     if(T.rchild == null || T.rchild == P){
17                         System.out.print(T.data);
18                         S.pop();
19                         p = T;
20                         flag = true;
21                     }else{
22                         S.push(T.rchild);
23                         flag = false;
24                     }
25                     if(! false)
26                         break;
27                 }
28             }
29         }
30     }

View Code

2. 中根遍历 ---- NOT BUG FREE

 1     public void inRootTraverse(){
 2         BiTreeNode T = root;
 3         if(T != null){
 4             LinkStack S = new LinkStack();
 5             S.push(T);
 6             while( ! S.isEmpty()){
 7                 while(S.seek() != null){
 8                     S.push(((BiTreeNode)S.seek()).lchild);
 9                 }
10                 S.pop();
11                 if(! S.isEmpty()){
12                     T = (BiTreeNode)S.pop();
13                     System.out.print(T.data);
14                     S.push(T.lchild);
15                 }
16                 /*if(S.seek().rchild != null){
17                     T = S.pop();
18                     System.out.print(T);
19                     S.push(T.rchild);
20                 }*/
21             }
22         }
23     }

View Code

1. 递归算法与非递归算法实现二叉树的遍历（先根遍历） ---- NOT BUG FREE

 1 public class BiTree{
 2     private BiTreeNode root;
 3     public BiTree(){
 4         this.root = null;
 5     }
 6     public BiTree(BiTreeNode root){
 7         this.root = root
 8     }
 9     //遍历法
10     public void preRootTraverse(BiTreeNode T){
11         if(T != null){
12             System.out.printIn(T.data);
13             preRootTraverse(T.lchild);
14             preRootTraverse(T.rchild);
15         }
16     }
17     //非遍历法**创建栈对象，根节点入栈；栈非空时，栈顶弹出并访问结点；
18     //对当前访问结点的非空左孩子结点相继依次访问，并将当前访问结点的非空右孩子结点压入栈内。
19     //循环执行，直到栈空。
20     public void preRootTraverse(){
21         BiTreeNode T = root;
22         if(T != null){
23             LinkStack s = new LinkStack();
24             s.push(T);
25             while(!s.isEmpty){
26                 T = (BiTreeNode)s.pop();
27                 System.out.print(T.data);
28                 /*while(T.lchild != null){
29                     T = T.lchild;
30                     System.out.print(T.data);
31                     if(T.rchild != null){
32                         s.push(T.rchild)
33                     }
34                 }*/
35                 while(T != null){
36                     if(T.lchild != null){
37                         System.out.print(T.lchild.data);
38                     }
39                     if(T.rchild != null){
40                         s.push(T.rchild);
41                     }
42                     T = T.lchild;
43                 }
44             }
45         }
46     }
47 }

View Code

第五章 树与二叉树

第五章树与二叉树