數據結構-二叉樹以及遍歷代碼

二叉樹是每個結點最多有兩個子樹的樹結構。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹常被用於實現二叉查找樹和二叉堆。

一棵深度為k，且有2^k-1個結點的二叉樹，稱為滿二叉樹。這種樹的特點是每一層上的結點數都是最大結點數。而在一棵二叉樹中，除最後一層外，若其餘層都是滿的，並且或者最後一層是滿的，或者是在右邊缺少連續若干結點，則此二叉樹為完全二叉樹。具有n個結點的完全二叉樹的深度為floor(log2n)+1。深度為k的完全二叉樹，至少有2k-1個葉子結點，至多有2k-1個結點。

二叉樹是樹的特殊一種，具有如下特點：1、每個結點最多有兩顆子樹，結點的度最大為2。2、左子樹和右子樹是有順序的，次序不能顛倒。3、即使某結點只有一個子樹，也要區分左右子樹。

一、特殊的二叉樹及特點

1、斜樹

所有的結點都只有左子樹（左斜樹），或者只有右子樹（右斜樹）。這就是斜樹，應用較少

左斜樹

右斜樹

2、滿二叉樹

所有的分支結點都存在左子樹和右子樹，並且所有的葉子結點都在同一層上，這樣就是滿二叉樹。

滿二叉樹

根據滿二叉樹的定義，其特點為：

1. 葉子只能出現在最下一層。
2. 非葉子結點度一定是2.
3. 在同樣深度的二叉樹中，滿二叉樹的結點個數最多，葉子樹最多。

3、完全二叉樹

完全二叉樹：對於一個樹高為h的二叉樹，如果其第0層至第h-1層的節點都滿。如果最下面一層節點不滿，則所有的節點在左邊的連續排列，空位都在右邊。這樣的二叉樹就是一棵完全二叉樹。

完全二叉樹最重要的性質：如果n個節點的完全二叉樹的節點按照層次並按從左到右的順序從0開始編號，特點有：

• 序號為0的節點是根

• 對於i>0，其父節點的編號為(i-1)/2。

• 若2·i+1

• 若2·i+2

4、二叉樹遍歷

遍歷二叉樹：就是按照系統化的方式訪問二叉樹裡的每一個節點。

• 這是二叉樹的一個重要性質：每棵二叉樹都有唯一的根節點，可以將其看做這棵二叉樹的唯一標識，是基於樹結構的處理入口。

深度優先遍歷：按照一條路徑儘可能的向前探索， 直至檢查完一個葉節點。

遍歷實例

1.先根序遍歷(前序遍歷)：先訪問根節點，而後以同樣的方式順序遍歷左子樹和右子樹。就是先訪問根結點，再先序遍歷左子樹，最後再先序遍歷右子樹即根—左—右。結果：A -> B -> D -> H -> E -> I -> C -> F -> J -> K ->G

前序遞歸遍歷的代碼實現：

<code>//前序遞歸遍歷
void PreOrderTraverse(BiTree *root)
{
  //注意跳出條件
    if(root != NULL)
    {
       //注意訪問語句順序
        printf("%c ", root->data);
        PreOrderTraverse(root->lchild);
        PreOrderTraverse(root->rchild);
    }
}/<code>

非遞歸實現：

根據前序遍歷訪問的順序，優先訪問根結點，然後再分別訪問左孩子和右孩子。即對於任一結點，其可看做是根結點，因此可以直接訪問，訪問完之後，若其左孩子不為空，按相同規則訪問它的左子樹；當訪問其左子樹時，再訪問它的右子樹。因此其處理過程如下：

對於任一結點P：

1)訪問結點P，並將結點P入棧;

2)判斷結點P的左孩子是否為空，若為空，則取棧頂結點並進行出棧操作，並將棧頂結點的右孩子置為當前的結點P，循環至1);若不為空，則將P的左孩子置為當前的結點P;

3)直到P為NULL並且棧為空，則遍歷結束。

<code>//前序非遞歸遍歷
void preOrder2(BinTree *root)     //非遞歸前序遍歷 
{
    stack<bintree> s;
    BinTree *p=root;
    while(p!=NULL||!s.empty())
    {
        while(p!=NULL)
        {
            cout<data<            s.push(p);
            p=p->lchild;
        }
        if(!s.empty())
        {
            p=s.top();
            s.pop();
            p=p->rchild;
        }
    }
}/<bintree>/<code>

2.後根序遍歷(後序遍歷)：先以同樣的方式遍歷左右子樹，最後遍歷根節點。 結果：H -> D -> I -> E -> B -> J -> K -> F -> G -> C -> A

1）後序遞歸遍歷

<code>1）中序遞歸遍歷void postOrder1(BinTree *root)    //遞歸後序遍歷
{
    if(root!=NULL)
    {
        postOrder1(root->lchild);
        postOrder1(root->rchild);
        cout<<root->data<    }    
}/<root->/<code>

2）後序非遞歸遍歷

後序遍歷：需要判斷上次訪問的節點是位於左子樹，還是右子樹。若是位於左子樹，則需跳過根節點，先進入右子樹，再回頭訪問根節點；若是位於右子樹，則直接訪問根節點。

<code>void postOrder1(BinTree *root){
        if (root == NULL)
          return;
        stack<bintree> s;
        //pCur:當前訪問節點，pLastVisit:上次訪問節點
        BinTree* pCur, *pLastVisit;
        //pCur = root;
        pCur = root;
        pLastVisit = NULL;
        //先把pCur移動到左子樹最下邊
        while (pCur)
        {
          s.push(pCur);
          pCur = pCur->lchild;
        }
        while (!s.empty())
        {
          //走到這裡，pCur都是空，並已經遍歷到左子樹底端(看成擴充二叉樹，則空，亦是某棵樹的左孩子)
          pCur = s.top();
          s.pop();
          //一個根節點被訪問的前提是：無右子樹或右子樹已被訪問過
          if (pCur->rchild == NULL || pCur->rchild == pLastVisit)
          {
            cout  << pCur->data;
            //修改最近被訪問的節點
            pLastVisit = pCur;
          }
          /*這裡的else語句可換成帶條件的else if:
          else if (pCur->lchild == pLastVisit)//若左子樹剛被訪問過，則需先進入右子樹(根節點需再次入棧)
          因為：上面的條件沒通過就一定是下面的條件滿足。仔細想想！
          */
          else
          { 

            //根節點再次入棧
            s.push(pCur);
            //進入右子樹，且可肯定右子樹一定不為空
            pCur = pCur->rchild;
            while (pCur)
            {
              s.push(pCur);
              pCur = pCur->lchild;
            }
          }
        }
}\t/<bintree>/<code>

3.中根序遍歷(中序遍歷)：先以同樣的方式遍歷左子樹，然後訪問根節點，最後以同樣的方式遍歷右子樹。 結果： D -> H ->B -> E -> I -> A -> J -> F -> K -> C -> G

1）中序遞歸遍歷

<code>void InOrderTraverse(BiTree *root)
{
    if(root != NULL)
    {
        InOrderTraverse(root->lchild);
        printf("%c ", root->data);
        InOrderTraverse(root->rchild);
    }
}/<code>

2）中序非遞歸遍歷

根據中序遍歷的順序，對於任一結點，優先訪問其左孩子，而左孩子結點又可以看做一個根結點，然後繼續訪問其左孩子結點，直到遇到左孩子結點為空的結點才停止訪問，然後按相同的規則訪問其右子樹。其處理過程如下：

對於任一結點：

a. 若其左孩子不為空，則將p入棧，並將p的左孩子設置為當前的p，然後對當前結點再進行相同的操作；

b. 若其左孩子為空，則取棧頂元素並進行出棧操作，訪問該棧頂結點，然後將當前的p置為棧頂結點的右孩子；

c. 直到p為空並且棧為空，則遍歷結束。

<code>//中序非遞歸遍歷
void InOrderTraverse(BiTree* root)
{
\t//空樹
\tif (root == NULL)
\t\treturn;
\t//樹非空
\tBiTree* p = root;
\tstack<bitree> s;
\twhile (!s.empty() || p)
    {
      //一直遍歷到左子樹最下邊，邊遍歷邊保存根節點到棧中
      while (p)
      {
          s.push(p);
          p = p->lchild;
      }
      //當p為空時，說明已經到達左子樹最下邊，這時需要出棧了
      if (!s.empty())
      {
          p = s.top();
          s.pop();
          cout<data<          //進入右子樹，開始新的一輪左子樹遍歷(這是遞歸的自我實現) 

          p = p->rchild;
      }
    }
}/<bitree>/<code>

五、二叉樹的建立

其實而二叉樹的建立就是二叉樹的遍歷，只不過將輸入內容改為建立結點而已，比如，利用前序遍歷建立二叉樹

<code>//創建樹
//按先後次序輸入二叉樹中結點的值(一個字符),#表示空樹
//構造二叉鏈表表示的二叉樹
BiTree CreateTree(BiTree t)
{
    char ch;
    scanf("%c", &ch);
 
    if(ch == '#')
    {
        t = NULL;
    }
    else
    {
        t = (BitNode *)malloc(sizeof(BitNode));
        if(t == NULL)
        {
            return;
        }
 
        t->data = ch;                        //生成根結點
        t->lchild = CreateTree(t->lchild);    //構造左子樹
        t->rchild = CreateTree(t->rchild);    //構造右子樹
    }
    return t;
}/<code>

閱讀更多 嘎嘎皮皮來了 的文章

關鍵字: 斜樹 數據結構 不完美媽媽