バイナリツリートラバーサルアルゴリズム

A. バイナリツリートラバーサル

1. バイナリツリーの事前順序トラバーサル:

(1) バイナリツリーが空の場合、それは何も行わず、空を返します。
(2) ルートノードにアクセスします。
(3) 左側のサブツリーの事前順序走査。
(4) Preorder は、右のサブツリーをトラバースします。

a. バイナリツリーの事前順序走査のための再帰的アルゴリズム:

# #

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

ログイン後にコピー

b. スタックを使用して各ノードの正しいサブツリーを保存するバイナリツリー事前順序トラバーサルの非再帰アルゴリズム:

( 1) ツリーが空の場合、ポインタ p はルートノードを指します。p は現在のノードポインタです。
(2) まず現在のノード p にアクセスし、p をスタック S にプッシュします。
(3) p がその左の子を指すようにします。
(4) p が空になるまで手順 (2) と (3) を繰り返します。
(5) スタック S から最上位の要素をポップし、p をこの要素の右側の子にポイントします。
(6) p が空になり、スタック S も空になるまで、手順 (2) ～ (5) を繰り返します。
(7) トラバースが終了します。
スタックの事前順序走査を使用する非再帰アルゴリズム:

      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. バイナリリンクリストを使用するstorage バイナリツリーの事前順序走査のための非再帰アルゴリズム:

    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. バイナリツリーの順序どおりの走査:

( 1) バイナリツリーが空の場合、それは何も行わず、何も返しません。
(2) 左側のサブツリーを順番に走査します。
(3) ルートノードにアクセスします。
(4) 右側のサブツリーを順番に走査します。

# a. バイナリツリーを順番に走査するための再帰的アルゴリズム:

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

ログイン後にコピー

b. スタックストレージを使用したバイナリツリーの順序トラバーサルのための非再帰アルゴリズム:

(1) ツリーが空の場合、ポインタ p はルートノードを指します。p は現在のノードポインタです。
(2) p をスタック S にプッシュし、p がその左の子を指すようにします。
(3) p が空になるまで手順 (2) を繰り返します。
(4) スタック S から最上位の要素をポップし、p がこの要素を指すようにします。
(5) 現在のノード p にアクセスし、p をその右側の子にポイントします。
(6) p が空になり、スタック S も空になるまで、手順 (2) ～ (5) を繰り返します。
(7) トラバースが終了します。
スタックの順序トラバーサルを使用した非再帰アルゴリズム:

     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. 次を使用します。バイナリフォークリンクリストに格納されたバイナリツリーを順番に走査するための非再帰アルゴリズム:

    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. 事後走査バイナリツリー:

(1) バイナリツリーが空の場合、それは何も行わず、空を返します。
(2) 左側のサブツリーの事後走査。
(3) 右サブツリーの事後走査。
(4) ルートノードにアクセスします。

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

ログイン後にコピー

一般的な問題に関連する技術的な記事については、FAQ 列にアクセスして学習してください。

以上がバイナリツリートラバーサルアルゴリズムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。