Binärbaum-Traversalalgorithmus

A. Binärer Baumdurchlauf

1. Durchqueren des Binärbaums vorbestellen:

(1) Wenn der Binärbaum leer ist, ist er ein No-Op und gibt nichts zurück.
(2) Besuchen Sie den Wurzelknoten.
(3) Durchqueren des linken Teilbaums vorbestellen.
(4) Vorbestellung durchläuft den rechten Teilbaum.

a. Rekursiver Algorithmus für die Vorbestellungsdurchquerung von Binärbäumen:

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

b. Nichtrekursiver Algorithmus für die Binärbaum-Vorordnungsdurchquerung unter Verwendung eines Stapels zum Speichern des rechten Teilbaums jedes Knotens:

( 1) Wenn der Baum leer ist, zeigen Sie mit dem Zeiger p auf den Wurzelknoten, und p ist der aktuelle Knotenzeiger.
(2) Besuchen Sie zuerst den aktuellen Knoten p und schieben Sie p in den Stapel S.
(3) Lassen Sie p auf sein linkes Kind zeigen.
(4) Wiederholen Sie die Schritte (2) und (3), bis p leer ist.
(5) Platzieren Sie das oberste Element aus Stapel S und zeigen Sie p auf das rechte untergeordnete Element dieses Elements.
(6) Wiederholen Sie die Schritte (2)~(5), bis p leer ist und Stapel S ebenfalls leer ist.
(7) Ende der Durchquerung.
Nicht rekursiver Algorithmus mit Vorbestellungsdurchlauf des Stapels:

      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. Verwenden Sie eine binär verknüpfte Liste Speicher Nichtrekursiver Algorithmus für die Durchquerung eines Binärbaums vor der Reihenfolge:

    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. Durchquerung eines Binärbaums in der Reihenfolge :

( 1) Wenn der Binärbaum leer ist, handelt es sich um eine No-Op-Operation und gibt nichts zurück.
(2) Durchlauf des linken Teilbaums in der richtigen Reihenfolge.
(3) Besuchen Sie den Wurzelknoten.
(4) Durchquerung des rechten Teilbaums in der richtigen Reihenfolge.

a. Rekursiver Algorithmus für das Durchlaufen von Binärbäumen in der richtigen Reihenfolge:

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

b. Nichtrekursiver Algorithmus zum Durchlaufen von Binärbäumen in der richtigen Reihenfolge unter Verwendung von Stapelspeicher:

(1) Wenn der Baum leer ist, zeigt der Zeiger p auf den Wurzelknoten, und p ist der aktuelle Knotenzeiger.
(2) Schieben Sie p in den Stapel S und lassen Sie p auf sein linkes untergeordnetes Element zeigen.
(3) Wiederholen Sie Schritt (2), bis p leer ist.
(4) Ziehen Sie das oberste Element vom Stapel S ab und zeigen Sie p auf dieses Element.
(5) Besuchen Sie den aktuellen Knoten p und zeigen Sie p auf sein rechtes Kind.
(6) Wiederholen Sie die Schritte (2)~(5), bis p leer ist und Stapel S ebenfalls leer ist.
(7) Die Durchquerung endet.
Nicht-rekursiver Algorithmus mit In-Order-Traversierung des Stapels:

     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;
         }
       }
     }

Verwendung binärer Fork Nicht rekursiver Algorithmus zum Durchlaufen eines in einer verknüpften Liste gespeicherten Binärbaums in der Reihenfolge:

    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 ein Binärbaum:

(1) Wenn der Binärbaum leer ist, handelt es sich um eine No-Op-Operation und gibt nichts zurück.
(2) Durchquerung des linken Teilbaums nach der Bestellung.
(3) Durchqueren des rechten Teilbaums nach der Bestellung.
(4) Besuchen Sie den Wurzelknoten.

     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);
        }
      }
    }

Weitere technische Artikel zu häufig gestellten Fragen finden Sie in der Spalte FAQ.

Das obige ist der detaillierte Inhalt vonBinärbaum-Traversalalgorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!