搜尋
首頁常見問題二元樹的遍歷演算法
二元樹的遍歷演算法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
基于因果森林算法的决策定位应用基于因果森林算法的决策定位应用Apr 08, 2023 am 11:21 AM

译者 | 朱先忠​审校 | 孙淑娟​在我之前的​​博客​​中,我们已经了解了如何使用因果树来评估政策的异质处理效应。如果你还没有阅读过,我建议你在阅读本文前先读一遍,因为我们在本文中认为你已经了解了此文中的部分与本文相关的内容。为什么是异质处理效应(HTE:heterogenous treatment effects)呢?首先,对异质处理效应的估计允许我们根据它们的预期结果(疾病、公司收入、客户满意度等)选择提供处理(药物、广告、产品等)的用户(患者、用户、客户等)。换句话说,估计HTE有助于我

Java如何遍历文件夹并获取所有文件名Java如何遍历文件夹并获取所有文件名Mar 29, 2024 pm 01:24 PM

Java是一种流行的编程语言,具有强大的文件处理功能。在Java中,遍历文件夹并获取所有文件名是一种常见的操作,可以帮助我们快速定位和处理特定目录下的文件。本文将介绍如何在Java中实现遍历文件夹并获取所有文件名的方法,并提供具体的代码示例。1.使用递归方法遍历文件夹我们可以使用递归方法来遍历文件夹,递归方法是一种自身调用自身的方式,可以有效地遍历文件夹中

在C语言中打印二叉树的左视图在C语言中打印二叉树的左视图Sep 03, 2023 pm 01:25 PM

任务是打印给定二叉树的左节点。首先,用户将插入数据,从而生成二叉树,然后打印所形成的树的左视图。每个节点最多可以有2个子节点,因此这里程序必须仅遍历与节点关联的左指针如果左指针不为空,则意味着它将有一些与之关联的数据或指针,否则它将是要打印并显示为输出的左子级。示例Input:10324Output:102这里,橙色节点代表二叉树的左视图。在给定的图中,数据为1的节点是根节点,因此它将被打印,而不是转到左子节点,它将打印0,然后它将转到3并打印其左子节点,即2。我们可以使用递归方法来存储节点的级

Java中的二叉树结构详解Java中的二叉树结构详解Jun 16, 2023 am 08:58 AM

二叉树是计算机科学中常见的数据结构,也是Java编程中常用的一种数据结构。本文将详细介绍Java中的二叉树结构。一、什么是二叉树?在计算机科学中,二叉树是一种树形结构,每个节点最多有两个子节点。其中,左侧子节点比父节点小,右侧子节点则比父节点大。在Java编程中,常用二叉树表示排序,搜索以及提高对数据的查询效率。二、Java中的二叉树实现在Java中,二叉树

PHP glob()函数使用示例:遍历指定文件夹中的所有文件PHP glob()函数使用示例:遍历指定文件夹中的所有文件Jun 27, 2023 am 09:16 AM

PHPglob()函数使用示例:遍历指定文件夹中的所有文件在PHP开发中,经常需要遍历指定文件夹中的所有文件,以实现文件批量操作或读取。PHP的glob()函数正是用来实现这种需求的。glob()函数可以通过指定一个通配符匹配模式,来获取指定文件夹中符合条件的所有文件的路径信息。在这篇文章中,我们将会演示如何使用glob()函数来遍历指定文件夹中的所有文件

raptor允许使用连接基本什么来创建算法raptor允许使用连接基本什么来创建算法Jan 15, 2021 pm 06:42 PM

raptor允许使用连接基本流程图符号来创建算法,然后可以在其环境下直接调试和运行算法,包括单步执行或连续执行的模式。Raptor程序实际上是一个流程图,运行时一次执行一个图形符号,以便帮助用户跟踪Raptor程序的指令流执行过程。

在C语言中,将二叉树的右视图打印出来在C语言中,将二叉树的右视图打印出来Sep 16, 2023 pm 11:13 PM

任务是打印给定二叉树的右节点。首先用户将插入数据以创建二叉树,然后打印所形成的树的右视图。上图展示了使用节点10、42、93、14、35、96、57和88创建的二叉树,其中选择并显示在树的右侧的节点。例如,10、93、57和88是二叉树的最右节点。示例Input:1042931435965788Output:10935788每个节点都有两个指针,即左指针和右指针。根据这个问题,程序只需遍历右节点。因此,不需要考虑节点的左子节点。右视图存储了所有那些是其所在层级的最后一个节点的节点。因此,我们可以

Java Iterator 和 Iterable 的深入比较:优缺点分析Java Iterator 和 Iterable 的深入比较:优缺点分析Feb 19, 2024 pm 04:20 PM

概念差异:Iterator:Iterator是一个接口,代表一个从集合中获取值的迭代器。它提供了MoveNext()、Current()和Reset()等方法,允许你遍历集合中的元素,并对当前元素进行操作。Iterable:Iterable也是一个接口,代表一个可迭代的对象。它提供了Iterator()方法,用于返回一个Iterator对象,以便于遍历集合中的元素。使用方式:Iterator:要使用Iterator,需要先获得一个Iterator对象,然后调用MoveNext()方法来移动到下一

熱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尊渡假赌尊渡假赌尊渡假赌

熱工具

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

DVWA

DVWA

Damn Vulnerable Web App (DVWA) 是一個PHP/MySQL的Web應用程序,非常容易受到攻擊。它的主要目標是成為安全專業人員在合法環境中測試自己的技能和工具的輔助工具,幫助Web開發人員更好地理解保護網路應用程式的過程,並幫助教師/學生在課堂環境中教授/學習Web應用程式安全性。 DVWA的目標是透過簡單直接的介面練習一些最常見的Web漏洞,難度各不相同。請注意,該軟體中

PhpStorm Mac 版本

PhpStorm Mac 版本

最新(2018.2.1 )專業的PHP整合開發工具

Atom編輯器mac版下載

Atom編輯器mac版下載

最受歡迎的的開源編輯器

MinGW - Minimalist GNU for Windows

MinGW - Minimalist GNU for Windows

這個專案正在遷移到osdn.net/projects/mingw的過程中,你可以繼續在那裡關注我們。 MinGW:GNU編譯器集合(GCC)的本機Windows移植版本,可自由分發的導入函式庫和用於建置本機Windows應用程式的頭檔;包括對MSVC執行時間的擴展,以支援C99功能。 MinGW的所有軟體都可以在64位元Windows平台上運作。