树的遍历（先中后序，非递归，层次遍历）

柔情只为你懂 2022-06-09 01:12 126阅读 0赞

树的遍历分为先序遍历，中序遍历以及后续遍历。其中分为递归形式与非递归形式，及层次遍历。

先序遍历：

首先访问根节点，然后访问左子树，最后访问右子树。

void PreOrder(BiTree T)
    {
        if(p)
        {
              visit(p);
              PreOrder(p->lchild);
              PreOrder(p->rchild);
         }
    }

中序遍历：

首先访问左子树，然后访问根节点，最后访问右子树。

void InOrder(BiTree T)
    {
        if(p)
        {
              InOrder(p->lchild);
              visit(p);
              InOrder(p->rchild);
         }
    }

后序遍历：

首先访问左子树，然后访问右子树，最后访问根节点。

void InOrder(BiTree T)
    {
        if(p)
        {
              PostOrder(p->lchild);
              PostOrder(p->rchild);
              visit(p);
         }
    }

以上三种都是递归形式，下面说一下非递归形式的中序遍历。这里采用了栈：

void InOrder2(BiTree T)
    
    {
    
            InitStack(S);
    
            BiTree p = T;
    
           while(p || ! isEmpty(S))
    
           {
    
                   if(p)
    
                   {
    
                           Push(S,p);
    
                           p = p->lchild;
    
                    }
    
                    else
    
                   {
    
                          Pop(S,p);
    
                          visit(p);
    
                          p = p->rchild;
    
                   }
    
            }
    
    }

层次遍历：

就是将节点一层一层的输出,这里利用了队列：

void levelOrder(BiTree T)
    {
    	InitQueue(Q);
    	BiTree p = T;
    	EnQueue(Q,p);
    	while(p || !isEmpty(Q))
    	{
    		DeQueue(Q,p);
    		visit(p);
    		if(p->lchild)
    			EnQueue(Q,p->lchild);
    		if(p->rchild)
    			EnQueue(Q,p->rchild);
    	}
    }