搜尋
首頁常見問題二元樹的遍歷演算法

二元樹的遍歷演算法

Jun 20, 2019 am 11:51 AM
二元樹演算法遍歷

二元樹的遍歷演算法

 A.  二元樹的遍歷 

   ## 

##    1.前序遍歷二元樹:
       
 (1)若二元樹為空,則為空操作,則返回空白。
        (2)存取根結點。
        (3)前序遍歷左子樹。

        (4)前序遍歷右子樹。     

#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)重複步驟(2)、(3),直到p為空。
      (5)從堆疊S彈出堆疊頂部元素,並將p指向此元素的右小孩。
      (6)重複執行步驟(2)~(5),直到p為空且堆疊S也為空。

      (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.使用二元鍊錶儲存的二元樹前序遍歷非遞歸演算法:

    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)重複步驟(2),直到p為空白。
     (4)從堆疊S彈出堆疊頂部元素,並將p指向此元素。
     (5)存取目前結點p,並將p指向其右子。
     (6)重複執行步驟(2)~(5),直到p為空且堆疊S也為空。
     (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);
        }
      }
    }

更多常見問題的相關技術文章,請造訪常見問題欄位進行學習!

以上是二元樹的遍歷演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
deepseek網頁版官方入口deepseek網頁版官方入口Mar 12, 2025 pm 01:42 PM

國產AI黑馬DeepSeek強勢崛起,震撼全球AI界!這家成立僅一年半的中國人工智能公司,憑藉其免費開源的大模型DeepSeek-V3和DeepSeek-R1,在性能上與OpenAI等國際巨頭比肩,甚至在成本控制方面實現了突破性進展,贏得了全球用戶的廣泛讚譽。 DeepSeek-R1現已全面上線,性能媲美OpenAIo1正式版!您可以在網頁端、APP以及API接口體驗其強大的功能。下載方式:支持iOS和安卓系統,用戶可通過應用商店下載;網頁版也已正式開放! DeepSeek網頁版官方入口:ht

deepseek服務器繁忙怎麼解決deepseek服務器繁忙怎麼解決Mar 12, 2025 pm 01:39 PM

DeepSeek:火爆AI遭遇服務器擁堵,如何應對? DeepSeek作為2025年開年爆款AI,免費開源且性能媲美OpenAIo1正式版,其受歡迎程度可見一斑。然而,高並發也帶來了服務器繁忙的問題。本文將分析原因並提供應對策略。 DeepSeek網頁版入口:https://www.deepseek.com/DeepSeek服務器繁忙的原因:高並發訪問:DeepSeek的免費和強大功能吸引了大量用戶同時使用,導致服務器負載過高。網絡攻擊:據悉,DeepSeek對美國金融界造成衝擊,

深度求索deepseek官網入口深度求索deepseek官網入口Mar 12, 2025 pm 01:33 PM

2025年開年,國產AI“深度求索”(deepseek)驚艷亮相!這款免費開源的AI模型,性能堪比OpenAI的o1正式版,並已在網頁端、APP和API全面上線,支持iOS、安卓和網頁版多端同步使用。深度求索deepseek官網及使用指南:官網地址:https://www.deepseek.com/網頁版使用步驟:點擊上方鏈接進入deepseek官網。點擊首頁的“開始對話”按鈕。首次使用需進行手機驗證碼登錄。登錄後即可進入對話界面。 deepseek功能強大,可進行代碼編寫、文件讀取、創

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

AI Hentai Generator

AI Hentai Generator

免費產生 AI 無盡。

熱門文章

R.E.P.O.能量晶體解釋及其做什麼(黃色晶體)
3 週前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳圖形設置
3 週前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.如果您聽不到任何人,如何修復音頻
3 週前By尊渡假赌尊渡假赌尊渡假赌
WWE 2K25:如何解鎖Myrise中的所有內容
3 週前By尊渡假赌尊渡假赌尊渡假赌

熱工具

SecLists

SecLists

SecLists是最終安全測試人員的伙伴。它是一個包含各種類型清單的集合,這些清單在安全評估過程中經常使用,而且都在一個地方。 SecLists透過方便地提供安全測試人員可能需要的所有列表,幫助提高安全測試的效率和生產力。清單類型包括使用者名稱、密碼、URL、模糊測試有效載荷、敏感資料模式、Web shell等等。測試人員只需將此儲存庫拉到新的測試機上,他就可以存取所需的每種類型的清單。

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

Atom編輯器mac版下載

Atom編輯器mac版下載

最受歡迎的的開源編輯器

SublimeText3漢化版

SublimeText3漢化版

中文版,非常好用