Binary tree traversal algorithm

A. Binary tree traversal

1. Preorder traversal of the binary tree:

(1) If the binary tree is empty, it is a no-op operation and returns empty.
(2) Visit the root node.
(3) Preorder traversal of the left subtree.
(4) Preorder traverse the right subtree.

##a. Recursive algorithm for pre-order traversal of binary trees:

   void PreOrderTraverse(BiTree BT)
   {     if(BT)
     {
        printf("%c",BT->data);              //访问根结点
        PreOrderTraverse(BT->lchild);       //前序遍历左子树
        PreOrderTraverse(BT->rchild);       //前序遍历右子树     }
   }

b. Non-recursive algorithm for binary tree pre-order traversal using stack to store the right subtree of each node:

( 1) When the tree is empty, point the pointer p to the root node, and p is the current node pointer.
(2) First visit the current node p and push p into the stack S.
(3) Let p point to its left child.
(4) Repeat steps (2) and (3) until p is empty.
(5) Pop the top element from stack S and point p to the right child of this element.
(6) Repeat steps (2)~(5) until p is empty and stack S is also empty.
(7) The traversal ends.
Non-recursive algorithm using pre-order traversal of the stack:

      void PreOrderNoRec(BiTree BT)
      {
        stack S;
        BiTree p=BT->root;        while((NULL!=p)||!StackEmpty(S))
        {          if(NULL!=p)
          {
            printf("%c",p->data);
            Push(S,p);
            p=p->lchild;
          }          else
          {
            p=Top(S);
            Pop(S);
            p=p->rchild;
          }
        }
      }

c. Use binary linked list storage Non-recursive algorithm for pre-order traversal of a binary tree:

    void PreOrder(pBinTreeNode pbnode)
    {
      pBinTreeNode stack[100];
      pBinTreeNode p;      int top;
      top=0;
      p=pbnode;      do
      {        while(p!=NULL)
        {
          printf("%d\n",p->data);      //访问结点p
          top=top+1;
          stack[top]=p;
          p=p->llink;                  //继续搜索结点p的左子树        }        if(top!=0)
        {
          p=stack[top];
          top=top-1;
          p=p->rlink;                  //继续搜索结点p的右子树        }
      }while((top!=0)||(p!=NULL));
    }

2. In-order traversal of a binary tree:

( 1) If the binary tree is empty, it is a no-op operation and returns empty.
(2) In-order traversal of the left subtree.
(3) Visit the root node.
(4) In-order traversal of the right subtree.

a. Recursive algorithm for in-order traversal of binary trees:

##

    void InOrderTraverse(BiTree BT)
    {      if(BT)
      {
         InOrderTraverse(BT->lchild);        //中序遍历左子树
         printf("%c",BT->data);              //访问根结点
         InOrderTraverse(BT->rchild);        //中序遍历右子树      }
    }

b. Non-recursive algorithm for in-order traversal of binary trees using stack storage:

(1) When the tree When it is empty, point the pointer p to the root node, and p is the current node pointer.

(2) Push p onto stack S and make p point to its left child.
(3) Repeat step (2) until p is empty.
(4) Pop the top element from stack S and point p to this element.
(5) Access the current node p and point p to its right child.
(6) Repeat steps (2)~(5) until p is empty and stack S is also empty.
(7) The traversal ends.
Non-recursive algorithm using in-order traversal of the stack:

     void IneOrderNoRec(BiTree BT)
     {
       stack S;
       BiTree p=BT->root;       while((NULL!=p)||!StackEmpty(S))
       {         if(NULL!=p)
         {
           Push(S,p);
           p=p->lchild;
         }         else
         {
           p=Top(S);
           Pop(S);
           printf("%c",p->data);
           p=p->rchild;
         }
       }
     }

c. Use binary fork Non-recursive algorithm for in-order traversal of a binary tree stored in a linked list:

    void InOrder(pBinTreeNode pbnode)
    {
         pBinTreeNode stack[100];
         pBinTreeNode p;         int top;
         top=0;
         p=pbnode;         do
         {           while(p!=NULL)
           {
             top=top+1;
             stack[top]=p;                //结点p进栈
             p=p->llink;                  //继续搜索结点p的左子树           }           if(top!=0)
           {
             p=stack[top];                //结点p出栈
             top=top-1;
             printf("%d\n",p->data);      //访问结点p
             p=p->rlink;                  //继续搜索结点p的右子树           }
         }while((top!=0)||(p!=NULL));
    }

3. Post-order traversal of a binary tree:

(1) If the binary tree is empty, it is a no-op operation and returns empty.

(2) Post-order traversal of the left subtree.
(3) Post-order traversal of the right subtree.
(4) Visit the root node.

     a.二叉树后序遍历的递归算法：

     void PostOrderTraverse(BiTree BT)
     {       if(BT)
       {
          PostOrderTraverse(BT->lchild);        //后序遍历左子树
          PostOrderTraverse(BT->rchild);        //后序遍历右子树
          printf("%c",BT->data);                //访问根结点       }
     }

     b.使用栈存储的二叉树后序遍历的非递归算法：

      算法思想：首先扫描根结点的所有左结点并入栈，然后出栈一个结点，扫描该结点的右结点并入栈，再扫描该右结点的所有左结点并入栈，当一个结点的左、右子树均被访问后再访问该结点。因为在递归算法中，左子树和右子树都进行了返回，因此为了区分这两种情况，还需要设置一个标识栈tag，当tag的栈顶元素为0时表示从左子树返回，为1表示从右子树返回。
       (1)当树为空时，将指针p指向根结点，p为当前结点指针。
       (2)将p压入栈S中，0压入栈tag中，并令p指向其左孩子。
       (3)重复执行步骤(2)，直到p为空。
       (4)如果tag栈中的栈顶元素为1，跳至步骤(6)。
       (5)如果tag栈中的栈顶元素为0，跳至步骤(7)。
       (6)将栈S的栈顶元素弹出，并访问此结点，跳至步骤(8)。
       (7)将p指向栈S的栈顶元素的右孩子。
       (8)重复执行步骤(2)~(7)，直到p为空并且栈S也为空。
       (9)遍历结束。
        使用栈的后序遍历非递归算法：

       void PostOrderNoRec(BiTree BT)
       {
         stack S;
         stack tag;
         BiTree p=BT->root;         while((NULL!=p)||!StackEmpty(S))
         {           while(NULL!=p)
           {
             Push(S,p);
             Push(tag,0);
             p=p->lchild;
           }           if(!StackEmpty(S))
           {             if(Pop(tag)==1)
             {
               p=Top(S);
               Pop(S);
               printf("%c",p->data);
               Pop(tag);    //栈tag要与栈S同步             }             else
             {
               p=Top(S);               if(!StackEmpty(S))
               {
                 p=p->rchild;
                 Pop(tag);
                 Push(tag,1);
               }
             }
           }
         }
       }

     c.使用二叉链表存储的二叉树后序遍历非递归算法：

     void PosOrder(pBinTreeNode pbnode)
     {
          pBinTreeNode stack[100];       //结点的指针栈          int count[100];                //记录结点进栈次数的数组          pBinTreeNode p;          int top;
          top=0;
          p=pbnode;          do
          {            while(p!=NULL)
            {
              top=top+1;
              stack[top]=p;                //结点p首次进栈
              count[top]=0;
              p=p->llink;                  //继续搜索结点p的左子树            }
            p=stack[top];                  //结点p出栈
            top=top-1;            if(count[top+1]==0)
            {
              top=top+1;
              stack[top]=p;                //结点p首次进栈
              count[top]=1;
              p=p->rlink;                  //继续搜索结点p的右子树            }            else
            {
              printf("%d\n",p->data);      //访问结点p
              p=NULL;
            }
          }while((top>0));
     }

 B 线索化二叉树：

       线索化二叉树的结点结构图：

                 

     线索化二叉树的结点类型说明：

      typedef struct node
      {
        DataType data;        struct node *lchild, *rchild;       //左、右孩子指针        int ltag, rtag;                     //左、右线索
      }TBinTNode;         //结点类型
      typedef TBinTNode *TBinTree;

     在线索化二叉树中，一个结点是叶子结点的充分必要条件是其左、右标志均为1.

    中序线索化二叉树及其对应的线索链表如下图：

            

   (1)中序线索化二叉树的算法：

   void InOrderThreading(TBinTree p)
      {        if(p)
        {
          InOrderThreading(p->lchild);   //左子树线索化          if(p->lchild)
            p->ltag=0;          else
            p->ltag=1;          if(p->rchild)
            p->rtag=0;          else
            p->rtag=1;          if(*(pre))      //若*p的前驱*pre存在          {            if(pre->rtag==1)
              pre->rchild=p;            if(p->ltag==1)
              p->lchild=pre;
          }
          pre=p;                         //另pre是下一访问结点的中序前驱
          InOrderThreading(p->rchild);   //右子树线索化        }
      }

   (2)在中序线索化二叉树下，结点p的后继结点有以下两种情况：

      ①结点p的右子树为空，那么p的右孩子指针域为右线索，直接指向结点p的后继结点。
     ②结点p的右子树不为空，那么根据中序遍历算法，p的后继必是其右子树中第1个遍历到的结点。

     中序线索化二叉树求后继结点的算法：

 TBinTNode *InOrderSuc(BiThrTree p)
    {
       TBinTNode *q;       if(p->rtag==1)   //第①情况         return p->rchild;       else            //第②情况       {
         q=p->rchild;         while(q->ltag==0)
           q=q->lchild;         return q;
       }
    }

     中序线索化二叉树求前驱结点的算法：

TBinTNode *InOrderPre(BiThrTree p)
    {
       TBinTNode *q;       if(p->ltag==1)         return p->lchild;       else
       {
         q=p->lchild;         //从*p的左孩子开始查找         while(q->rtag==0)
           q=q->rchild;         return q;
       }
    }

   (3)遍历中序线索化二叉树的算法

void TraversInOrderThrTree(BiThrTree p)
    {      if(p)
      {        while(p->ltag==0)
          p=p->lchild;        while(p)
        {
          printf("%c",p->data);
          p=InOrderSuc(p);
        }
      }
    }

For more technical articles related to common problems, please visit the FAQ column to learn!

The above is the detailed content of Binary tree traversal algorithm. For more information, please follow other related articles on the PHP Chinese website!