此文介绍了二叉树的使用递归和非递归算法遍历先序、中序、后序

本文会随着作者日常学习进行补充及内容修正

树的结构定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class BinTree{
    private char data;
    private BinTree left;
    private BinTree right;
    public static BinTree(char c){
        data=c;
    }
    
    public static void main(String[] args){
        BinTree b1 = new BinTree('a');
        BinTree b2 = new BinTree('b');
        BinTree b3 = new BinTree('c');
        BinTree b4 = new BinTree('d');
        BinTree b5 = new BinTree('e');

        /**
         *      a
         *     / \
         *    b   c
         *   / \
         *  d   e
         *
         */
        
        b1.left = b2;
        b1.right = b3;
        b2.left = b4;
        b2.right = b5;
    }
}

递归算法

先序遍历

1
2
3
4
5
6
7
8
public static void pre(BinTree t){
    if(t==null){
        return;
    }
    System.out.print(t.data);
    pre(t.left);
    pre(t.right);
}

中序遍历

1
2
3
4
5
6
7
8
public static void in(BinTree t){
    if(t==null){
        return;
    }
    iN(t.left);
    System.out.print(t.data);
    in(t.right);
}

后序遍历

1
2
3
4
5
6
7
8
public static void pos(BinTree t){
    if(t==null){
        return;
    }
    pos(t.left);
    pos(t.right);
    System.out.print(t.data);
}

非递归算法

push()入栈

pop()返回栈顶元素，并在栈中删除它

peek() 返回栈顶元素，但不在栈中删除它。

先序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void pre1(BinTree t){
	Stack<BinTree> s=new Stack<BinTree>();
    while(t != null || !s.empty()){
        while(t!=null){
            System.out.print(t.data);
            s.push(t);
            t=t.left;
        }
        //从左边切换到右边
        if(!s.empty()){
            t=s.pop();
            t=t.right;
        }
    }
}

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void in1(BinTree t){
	Stack<BinTree> s = new Stack<BinTree>();
    while(t!=null || !s.empty()){
        while(t!=null){
            s.push(t);
            t=t.left;
        }
    	if(!s.empey()){
            t=s.pop();
            System.out.print(t.data);
            t=t.right;
        }
    }
}

后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void Pos1(BinTree t) {
    if(t!=null){
		Stack<BinTree> stack = new Stack<BinTree>();
        stack.push(t);
        BinTree c= null;
        while(!stack.isEmpty()){
            c=stack.peek();
            if(c.left!=null&&c.left!=t&&c.right!=t){
                stack.push(c.left);
            }else if(c.right!=null&&c.right!=t){
                stack.push(c.right);
            }else{
                System.out.print(stack.pop().data);
                t=c;
            }
        }
    }
}