二叉树—前序遍历、中序遍历(非递归)-蒲公英云

二叉树—前序遍历、中序遍历(非递归)

朱雀 2021-09-18 05:06 504阅读 0赞

【转载】https://www.cnblogs.com/bigsai/p/11393609.html
层级遍历

public void cengxu(node t) {//层序遍历
    Queue<node> q1 = new ArrayDeque<node>();
    if (t == null)
        return;
    if (t != null) {
        q1.add(t);
    }
    while (!q1.isEmpty()) {
        node t1 = q1.poll();
        if (t1.left != null)
            q1.add(t1.left);
        if (t1.right != null)
            q1.add(t1.right);
        System.out.print(t1.value + " ");
    }
    System.out.println();
}

非递归前序

public void qianxu3(node t)// 非递归前序 栈 先左后右  t一般为root
{
    Stack<node> q1 = new Stack<node>();
    if (t == null)
        return;
    if (t != null) {
        q1.push(t);
    }
    while (!q1.empty()) {
        node t1 = q1.pop();
        if (t1.right != null) {
            q1.push(t1.right);
        }
        if (t1.left != null) {
            q1.push(t1.left);
        }
        System.out.print(t1.value + " ");
    }
}
public void qianxu2(node t) {
        Stack<node> q1 = new Stack();    
        while(!q1.isEmpty()||t!=null)
        {
            if (t!=null) {
                System.out.print(t.value+" ");
                q1.push(t);                
                t=t.left;
            }
            else {
                t=q1.pop();
                t=t.right;
            }
        }
    }

中序遍历

public void zhongxu2(node t) {
    Stack<node> q1 = new Stack();    
    while(!q1.isEmpty()||t!=null)
    {
        if (t!=null) {
            q1.push(t);
            t=t.left;
        }
        else {
            t=q1.pop();
            System.out.print(t.value+" ");
            t=t.right;
        }
    }
}