17

我必须使用级别顺序遍历但以螺旋形式打印二叉树的节点，即不同级别的节点应以螺旋形式打印。

例如：如果树看起来像：

输出应该是 10 5 20 25 15 6 4。

我使用的算法很简单，只是级别顺序遍历的一个小变化。我只是取了一个变量 p。如果变量等于 1，而不是从左到右打印给定级别的订单，如果它是 -1，则从右到左打印。

void getlevel(struct node *root,int n,int p)
{
        if(root==NULL)
        return;
        if(n==0)
        {
                printf("%d ",root->info);
                return;
        }
        if(n>0)
        {
            if(p==1)
            {
                 getlevel(root->left,n-1,p);
                 getlevel(root->right,n-1,p);
            }
            if(p==-1)
            {
                 getlevel(root->right,n-1,p);
                 getlevel(root->left,n-1,p);
            }
        }
}

我得到了答案，但在倾斜树的情况下，最坏的情况复杂性可能是 O(n^2)。

这个任务有更好的算法吗？

我的整个程序都在这里

4

6 回答 6

18

是的。

您可以执行类似于正常级别顺序遍历的操作。

你必须使用两个堆栈

  1. 从左到右打印的第一个堆栈
  2. 第二叠从右到左打印。

从根节点开始。将它的孩子存储在一个堆栈中。在每次迭代中，您在其中一个堆栈中都有一个级别的节点。打印节点，并将下一级节点推送到其他堆栈中。重复直到达到最终水平。

时间复杂度 O(n) 和空间复杂度 O(n)。

于 2013-07-05T10:11:24.487 回答
6

用于二叉树的螺旋级顺序遍历的伪代码。

//Define two stacks S1, S2

//At each level,
// S1 carries the nodes to be traversed in that level
// S2 carries the child nodes of the nodes in S1

spiralLevelOrder(root) {
    S1 = new Stack()
    S2 = new Stack()
    S1.push(root)
    spiralLevelOrderRecursion(S1, S2, 1)
}

spiralLevelOrderRecursion(S1, S2, level) {
    while(S1 not empty) {
    node = S1.pop()
        visit(node)
        if (level is odd) {
            S2.push(node.rightNode)
            S2.push(node.leftNode)
        }
        else {
            S2.push(node.leftNode)
            S2.push(node.rightNode)
        }
    }
    if (S2 not empty)
        spiralLevelOrderRecursion(S2, S1, level+1)
}

样本树：1-(2-(4,5),3-(5,6)) 格式：root-(leftchild, rightchild)

应用伪代码：

螺旋层级递归([1], [], 1)

S2 - [] -> [3] -> [2, 3]
visit order : 1

螺旋级递归([2,3], [], 2)

S2 - [] -> [4] -> [5,4] -> [6, 5, 4] -> [7, 6, 5, 4]
visit order : 2, 3

螺旋级递归（[7,6,5,4]，[]，3）

visit order : 7, 6, 5, 4
于 2013-12-20T09:48:25.613 回答
1

以下代码将完成这项工作：

使用语言：Java

//  Algorithm for printing nodes in Zigzag order(zigzag tree traversal)
static void zigzagTreeTraversal(Node root)
{
    int count=0,c=1,i=0;
    boolean odd=false;
    Queue<Node> queue=new LinkedList<Node>();
    Node temp = null;
    queue.add(root);
    System.out.print("Printing Tree Traversal in Zigzag form :");
    while(true)
    {
        if(queue.isEmpty())
        {
            break;
        }

        for(i=0;i<c;i++)
        {
            temp=queue.remove();
            System.out.print(", " + temp.data);
            if(odd)
            {
                if(temp.right!=null)
                {
                    queue.add(temp.right);
                    count++;
                }

                if(temp.left!=null)
                {
                    queue.add(temp.left);
                    count++;
                }

            }
            else
            {
                if(temp.left!=null)
                {
                    queue.add(temp.left);
                    count++;
                }
                if(temp.right!=null)
                {
                    queue.add(temp.right);
                    count++;
                }

            }
        }
        c=count;
        count=0;
        odd=!odd;
    }
}
于 2016-11-24T17:17:37.433 回答
1

我相信其中最简单的一个，没有任何变量，只有两个堆栈。

public void zigzagNew() {
    TreeNode t = this.root;
    Stack<TreeNode> cs = new Stack<>();
    Stack<TreeNode> ns = new Stack<>();
    cs.add(t);
    while(cs.isEmpty()==false || ns.isEmpty() == false) {
        while(cs.isEmpty() == false) {
            TreeNode cur = cs.pop();
            System.out.print(cur.val + " ");
            if(cur.left != null) {
                ns.push(cur.left);
            }
            if(cur.right != null) {
                ns.push(cur.right);
            }
        }
        System.out.println();
        while(ns.isEmpty()==false) {
            TreeNode cur = ns.pop();
            System.out.print(cur.val + " ");
            if(cur.right != null) {
                cs.push(cur.right);
            }
            if(cur.left != null) {
                cs.push(cur.left);
            }
        }
        System.out.println();
    }
}
于 2020-05-28T17:29:10.147 回答
0 
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Stack;

public class ZigZagTraversal {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        BinaryTree bt = new BinaryTree();
        int[] array = {2,5,1,3,11,7,8,9,4,10,6};
        /*
         *                  2
         *                 / \
         *                /   \
         *               /     \
         *              5       1
         *             / \     / \
         *            /   \   /   \
         *           3    11 7     8
         *          / \   / \
         *         9   4 10  6 
         * 
         * */
        bt=BinaryTree.buildATree(bt, array);
        //BinaryTree.inOrderTraversal(bt);
        zigZagTraversal(llForAllNodesAtEachDepth(bt));
        zigZagDisplay(bt);
    }
    public static void zigZagDisplay(BinaryTree bt){
        Stack<BinaryTree> s = new Stack<>();
        if(s.isEmpty())
            s.push(bt);
        boolean flag = true;
        while(!s.isEmpty()){
            Stack<BinaryTree> temp = new Stack<>();
            while(!s.isEmpty()){
                BinaryTree b = s.pop();
                System.out.print(b.data+" ");
                if(flag){
                    if(b.left!=null)
                        temp.push(b.left);
                    if(b.right!=null)
                        temp.push(b.right);
                }
                else{
                    if(b.right!=null)
                        temp.push(b.right);
                    if(b.left!=null)
                        temp.push(b.left);
                }
            }
            s=temp;
            flag=!flag;
        }
    }
    public static ArrayList<LinkedList<BinaryTree>> llForAllNodesAtEachDepth(BinaryTree bt){
        ArrayList<LinkedList<BinaryTree>> res = new ArrayList<LinkedList<BinaryTree>>();
        return createLlForAllNodesAtEachDepth(res,bt, 0);
    }
    public static ArrayList<LinkedList<BinaryTree>> createLlForAllNodesAtEachDepth(ArrayList<LinkedList<BinaryTree>> res, BinaryTree bt, int level){
        if(bt==null)
            return null;
        if(level==res.size()){
            LinkedList<BinaryTree> list = new LinkedList<BinaryTree>();
            list.add(bt);
            res.add(list);
            createLlForAllNodesAtEachDepth(res,bt.left,level+1);
            createLlForAllNodesAtEachDepth(res,bt.right,level+1);
        }
        else{
            res.get(level).add(bt);
            createLlForAllNodesAtEachDepth(res,bt.left,level+1);
            createLlForAllNodesAtEachDepth(res,bt.right,level+1);
        }
        return res;
    }
    public static void zigZagTraversal(ArrayList<LinkedList<BinaryTree>> res){
        boolean flag=true;
        for(int i=0;i<res.size();i++){
            LinkedList<BinaryTree> temp = res.get(i);
            if(flag){
                for(int j=0;j<temp.size();j++){
                    System.out.print(temp.get(j).data+" -> ");
                }
                flag=false;
            }
            else{
                for(int j=temp.size()-1;j>=0;j--){
                    System.out.print(temp.get(j).data+" -> ");
                }
                flag=true;
            }
            System.out.println();
        }
    }
}
于 2015-07-30T14:58:39.790 回答
-1

// 使用两个堆栈的简单 C++ 代码

<pre> void zigzag(struct node *root)
         { 
            int lefttoright = 1 ;
            struct node *temp ;
            if(root == NULL)
              return ;
            stack<struct node *> current , next ,temp2 ;// temp is used to swap 
                                                         ////current and next            
            current.push(root);
            while(!current.empty())
            {temp = current.top();
             current.pop();
             cout<< temp->data << " " ;
             if(lefttoright)
             { if(temp->left)
                next.push(temp->left) ;
                if(temp->right) 
                 next.push(temp->right) ;
                 
                
                }
             else
                {if(temp->right)
                next.push(temp->right) ;
                if(temp->left) 
                 next.push(temp->left) ;
                }
             if(current.empty())  // make current as next and next  as current 
                                   //to hold next level nodes
             {lefttoright = 1-lefttoright ;
             temp2 = current ;
             current = next ;
             next = temp2 ;
             }
             
              
            }
            
        </pre>

于 2015-05-10T02:41:52.333 回答