數(shù)據(jù)結(jié)構(gòu)（十四）——二叉樹

一、二叉樹簡介

1、二叉樹簡介

二叉樹是由n（n>=0）個結(jié)點組成的有序集合，集合或者為空，或者是由一個根節(jié)點加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。
二叉樹的五種形態(tài)：

創(chuàng)新互聯(lián)是一家專業(yè)提供文昌企業(yè)網(wǎng)站建設(shè),專注與網(wǎng)站設(shè)計制作、網(wǎng)站制作、H5頁面制作、小程序制作等業(yè)務(wù)。10年已為文昌眾多企業(yè)、政府機構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)的建站公司優(yōu)惠進(jìn)行中。

2、二叉樹的存儲結(jié)構(gòu)模型

樹的另一種表示法：孩子兄弟表示法
A、每個結(jié)點都有一個指向其第一個孩子的指針
B、每個結(jié)點都有一個指向其第一個右兄弟的指針

孩子兄弟表示法的特性：
A、能夠表示任意的樹形結(jié)構(gòu)
B、每個結(jié)點包含一個數(shù)據(jù)成員和兩個指針成員
C、孩子結(jié)點指針和兄弟結(jié)點指針構(gòu)成樹杈

3、滿二叉樹

如果二叉樹中所有分支結(jié)點的度數(shù)都為2，并且葉子結(jié)點都在統(tǒng)一層次上，則二叉樹為滿二叉樹。

4、完全二叉樹

如果一棵具有n個結(jié)點的高度為k的二叉樹，樹的每個結(jié)點都與高度為k的滿二叉樹中編號為1——n的結(jié)點一一對應(yīng)，則二叉樹為完全二叉樹。
完全二叉樹的特性：
A、同樣結(jié)點數(shù)的二叉樹，完全二叉樹的高度最小
B、完全二叉樹的葉子結(jié)點僅出現(xiàn)在最下邊兩層，并且最底層的葉子結(jié)點一定出現(xiàn)在左邊，倒數(shù)第二層的葉子結(jié)點一定出現(xiàn)在右邊。
C、完全二叉樹中度為1的結(jié)點只有左孩子。

5、二叉樹的特性

A、在二叉樹的第i層上最多有2^(i-1)個結(jié)點（i>=1）。
B、高度為k的二叉樹，最多有2^k-1個結(jié)點（k>=0）。
C、對任何一棵二叉樹，如果其葉結(jié)點有n個，度為2的非葉子結(jié)點有m個，則
n = m + 1。
D、具有n個結(jié)點的完全二叉樹的高度為logn + 1
E、對于有n個結(jié)點的完全二叉樹，按層次對結(jié)點進(jìn)行編號（從上到下，從左到右），對于任意編號為i的結(jié)點：

二、二叉樹的操作

1、二叉樹的存儲結(jié)構(gòu)實現(xiàn)

二叉樹結(jié)點包含四個固定的成員：結(jié)點的數(shù)據(jù)域、指向父結(jié)點的指針域、指向左子結(jié)點的指針域、指向右子結(jié)點的指針域。結(jié)點的數(shù)據(jù)域、指向父結(jié)點的指針域從TreeNode模板類繼承而來。
二叉樹結(jié)點的實現(xiàn)：

template 
  class BTreeNode:public TreeNode
  {
  public:
    BTreeNode* m_left;//左子結(jié)點
    BTreeNode* m_right;//右子結(jié)點
    BTreeNode()
    {
        m_left = NULL;
        m_right = NULL;
    }

    //工廠方法，創(chuàng)建堆空間的結(jié)點
    static BTreeNode* NewNode()
    {
      BTreeNode* ret = new BTreeNode();
      if(ret != NULL)
      {
          //堆空間的結(jié)點標(biāo)識為true
          ret->m_flag = true;
      }
      return ret;
    }
  };

2、二叉樹的結(jié)點查找

A、基于數(shù)據(jù)元素的查找
定義基于數(shù)據(jù)元素查找的函數(shù)

virtual BTreeNode* find(BTreeNode* node, const T& value)const
      {
          BTreeNode* ret = NULL;
          //如果根節(jié)點node
          if(node != NULL)
          {
              if(node->value == value)
              {
                  ret = node;
              }
              else
              {
                  //查找左子樹
                  if(ret == NULL)
                  {
                      ret = find(node->m_left, value);
                  }
                  //如果左子樹沒有找到，ret返回NULL，查找右子樹
                  if(ret == NULL)
                  {
                      ret = find(node->m_right, value);
                  }
              }
          }
          return ret;
      }

    BTreeNode* find(const T& value)const
    {
        return find(root(), value);
    }

B、基于結(jié)點的查找
定義基于結(jié)點查找的函數(shù)

virtual BTreeNode* find(BTreeNode* node, BTreeNode* obj)const
      {
          BTreeNode* ret = NULL;
          if(node != NULL)
          {
              //根節(jié)點node為目標(biāo)結(jié)點
              if(node == obj)
              {
                  ret = node;
              }
              else
              {
                  //查找左子樹
                  if(ret == NULL)
                  {
                      ret = find(node->m_left, obj);
                  }
                  //如果左子樹沒有找到，ret返回NULL，繼續(xù)查找右子樹
                  if(ret == NULL)
                  {
                      ret = find(node->m_right, obj);
                  }
              }
          }
          return ret;
      }
    BTreeNode* find(TreeNode* node)const
    {
        return find(root(), dynamic_cast*>(node));
    }

3、二叉樹的結(jié)點插入

根據(jù)插入的位置定義二叉樹結(jié)點的位置枚舉類型：

  enum BTNodePos
    {
        Any,
        Left,
        Right
    };

在node結(jié)點的pos位置插入newnode結(jié)點的功能函數(shù)如下：

virtual bool insert(BTreeNode* newnode, BTreeNode* node, BTNodePos pos)
      {
          bool ret = true;
          //插入的位置為Any
          if(pos == Any)
          {
              //如果沒有左子結(jié)點，插入結(jié)點作為左子結(jié)點
              if(node->m_left == NULL)
              {
                  node->m_left = newnode;
              }
              //如果有左子結(jié)點，沒有右子結(jié)點，插入結(jié)點作為右子結(jié)點
              else if(node->m_right == NULL)
              {
                  node->m_right = newnode;
              }
              //如果node結(jié)點的左右子結(jié)點不為空，插入失敗
              else
              {
                  ret = false;
              }
          }
          else if(pos == Left)
          {
              //如果指定插入左子結(jié)點，如果沒有左子結(jié)點，插入結(jié)點
              if(node->m_left == NULL)
              {
                  node->m_left = newnode;
              }
              else
              {
                  ret = false;
              }
          }
          else if(pos == Right)
          {
              //如果指定插入右子結(jié)點，如果沒有右子結(jié)點，插入結(jié)點
              if(node->m_right == NULL)
              {
                  node->m_right = newnode;
              }
              else
              {
                  ret = false;
              }
          }
          else
          {
              ret = false;
          }
          return ret;
      }

A、插入新結(jié)點

 //插入結(jié)點，無位置要求
    bool insert(TreeNode* node)
    {
       return insert(dynamic_cast*>(node), Any);
    }
    //插入結(jié)點，指定插入位置
    virtual bool insert(BTreeNode* node, BTNodePos pos)
    {
        bool ret = true;
        if(node != NULL)
        {
            if(this->m_root == NULL)
            {
                node->parent = NULL;
                this->m_root = node;
            }
            else
            {
               BTreeNode* np = find(node->parent);
               if(np != NULL)
               {
                   ret = insert(dynamic_cast*>(node), np, pos);
               }
               else
               {
                   THROW_EXCEPTION(InvalidParameterException, "Parameter invalid...");
               }
            }
        }
        else
        {
            THROW_EXCEPTION(InvalidParameterException, "Parameter invalid...");
        }
        return ret;
    }

B、插入數(shù)據(jù)元素

 //插入數(shù)據(jù)，指定插入位置和父結(jié)點
    virtual bool insert(const T& value, TreeNode* parent, BTNodePos pos)
    {
        bool ret = true;
        BTreeNode* node = BTreeNode::NewNode();
        if(node != NULL)
        {
            node->parent = parent;
            node->value = value;
            ret = insert(node, pos);
            if(!ret)
            {
                delete node;
            }
        }
        else
        {
            THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory...");
        }

        return ret;
    }
    //插入數(shù)據(jù)，指定父結(jié)點
    bool insert(const T& value, TreeNode* parent)
    {
        return insert(value, parent, Any);
    }

4、二叉樹的結(jié)點刪除

刪除功能函數(shù)的定義：

virtual void remove(BTreeNode* node, BTree* ret)
      {
          ret = new BTree();
          if(ret == NULL)
          {
              THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory...");
          }
          else
          {
              if(node == root())
              {
                  this->m_root = NULL;
              }
              else
              {
                  BTreeNode* parent = dynamic_cast*>(node->parent);
                  if(parent->m_left == node)
                  {
                      parent->m_left = NULL;
                  }
                  else if(parent->m_right == node)
                  {
                      parent->m_right = NULL;
                  }
                  node->parent = NULL;
              }
              ret->m_root = node;
          }
      }

A、基于數(shù)據(jù)元素值刪除

 //根據(jù)數(shù)據(jù)元素刪除結(jié)點
    SharedPointer< Tree > remove(const T& value)
    {
        BTree* ret = NULL;
        BTreeNode* node = find(value);
        if(node == NULL)
        {
            THROW_EXCEPTION(InvalidParameterException, "No value...");
        }
        else
        {
            remove(node, ret);
        }
        return ret;
    }

B、基于結(jié)點刪除

 //根據(jù)結(jié)點刪除結(jié)點
    SharedPointer< Tree > remove(TreeNode* node)
    {
        BTree* ret = NULL;
        node = find(node);
        if(node != NULL)
        {
            remove(dynamic_cast*>(node), ret);
        }
        else
        {
            THROW_EXCEPTION(InvalidParameterException, "No node...");
        }
        return ret;
    }

5、二叉樹的清空

將二叉樹中所有在堆空間分配的結(jié)點銷毀。
清除node結(jié)點為根節(jié)點的二叉樹的功能函數(shù)：

virtual void free(BTreeNode* node)
      {
          if(node != NULL)
          {
              free(node->m_left);
              free(node->m_right);
          }
          //如果結(jié)點在堆空間分配
          if(node->flag())
          {
              delete node;
          }
      }
    //清空樹
    void clear()
    {
        free(root());
        this->m_root = NULL;
    }

6、二叉樹的屬性操作

A、樹中結(jié)點的數(shù)量
定義計算某個結(jié)點為根結(jié)點的樹的結(jié)點的數(shù)量

 int count(BTreeNode* node) const
      {
          int ret = 0;
          if(node != NULL)
          {
              ret = count(node->m_left) + count(node->m_right) + 1;
          }
          return ret;
      }
    //樹的結(jié)點數(shù)目訪問函數(shù)
    int count()const
    {
        return count(root());
    }

B、樹的高度
獲取node結(jié)點為根結(jié)點的二叉樹的高度的功能函數(shù)：

 int height(BTreeNode* node) const
      {
          int ret = 0;
          if(node != NULL)
          {
              int l = height(node->m_left);
              int r = height(node->m_right);
              ret = ((l > r)?l:r) + 1;
          }
          return ret;
      }
    //樹的高度訪問函數(shù)
    int height()const
    {
        return height(root());
    }

C、樹的度
獲取node為根結(jié)點的二叉樹的度的功能函數(shù)：

 int degree(BTreeNode* node) const
      {
          int ret = 0;
          if(node != NULL)
          {
              //根結(jié)點的度數(shù)
              ret = (!!node->m_left + !!node->m_right);
              //左子樹的度
              if(ret < 2)
              {
                  int l = degree(node->m_left);
                  if(ret < l)
                  {
                      ret = l;
                  }
              }
              //右子樹的度數(shù)
              if(ret < 2)
              {
                  int r = degree(node->m_left);
                  if(ret < r)
                  {
                      ret = r;
                  }
              }
          }
          return ret;
      }
    //樹的度訪問函數(shù)
    int degree()const
    {
        return degree(root());
    }

7、二叉樹的層次遍歷

二叉樹的遍歷是指從根結(jié)點出發(fā)，按照某種次序依次訪問二叉樹中的所有結(jié)點，使得每個結(jié)點被訪問依次，且僅被訪問一次。
根據(jù)游標(biāo)思想，提供一組遍歷的先關(guān)函數(shù)，按層次訪問二叉樹中的數(shù)據(jù)元素。

引入一個隊列，輔助遍歷二叉樹。
LinkedQueue*> m_queue;
層次遍歷的過程如下：

 //將根結(jié)點壓入隊列
    bool begin()
    {
      bool ret = (root() != NULL);
      if(ret)
      {
          //清空隊列
          m_queue.clear();
          //根節(jié)點加入隊列
          m_queue.add(root());
      }
      return ret;
    }
    //判斷隊列是否為空
    bool end()
    {
        return (m_queue.length() == 0);
    }

    //隊頭元素彈出，將隊頭元素的孩子壓入隊列中
    bool next()
    {
      bool ret = (m_queue.length() > 0);
      if(ret)
      {
          BTreeNode* node = m_queue.front();
          m_queue.remove();//隊頭元素出隊
          //將隊頭元素的子結(jié)點入隊
          if(node->m_left != NULL)
          {
              m_queue.add(node->m_left);
          }
          if(node->m_right != NULL)
          {
              m_queue.add(node->m_right);
          }
      }
      return ret;
    }
    //訪問隊頭元素指向的數(shù)據(jù)元素
    T current()
    {
      if(!end())
      {
          return m_queue.front()->value;
      }
      else
      {
          THROW_EXCEPTION(InvalidOperationException, "No value at current Node...");
      }
    }

8、二叉樹的克隆

定義克隆node結(jié)點為根結(jié)點的二叉樹的功能函數(shù)：

BTreeNode* clone(BTreeNode* node)
      {
          BTreeNode * ret = NULL;
          if(node != NULL)
          {
              ret = BTreeNode::NewNode();
              if(ret != NULL)
              {
                  ret->value = node->value;
                  //左子樹
                  ret->m_left = clone(node->m_left);
                  //右子樹
                  ret->m_right = clone(node->m_right);
                  //如果左子樹不為空，設(shè)置左子樹的父結(jié)點
                  if(ret->m_left != NULL)
                  {
                      ret->m_left->parent = ret;
                  }
                  //如果右子樹不為空，設(shè)置右子樹父結(jié)點
                  if(ret->m_right != NULL)
                  {
                      ret->m_right->parent = ret;
                  }
              }
              else
              {
                  THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory...");
              }
          }
          return ret;
      }
    SharedPointer> clone()const
    {
        BTree* ret = new BTree();
        if(ret != NULL)
        {
            ret->m_root = clone(root());
        }
        else
        {
            THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory...");
        }
        return ret;
    }

9、二叉樹的比較

判斷兩棵二叉樹中的數(shù)據(jù)元素是否對應(yīng)相等
定義二叉樹相等比較的功能函數(shù)：

bool equal(BTreeNode* l, BTreeNode* r)const
      {
          bool ret = true;
          //二叉樹自比較
          if(l == r)
          {
              ret = true;
          }
          //兩棵二叉樹都不為空
          else if(l != NULL &&  r != NULL)
          {
             ret = (l->value == r->value) && (equal(l->m_left, r->m_left)) && (l->m_right, r->m_right);
          }
          //有一棵二叉樹為空，一棵二叉樹不為空
          else
          {
              ret = false;
          }
          return ret;
      }

    bool operator ==(const BTree& tree)const
    {
        return equal(root(), tree.root());
    }

    bool operator !=(const BTree& tree)const
    {
        return !(*this == tree);//使用==比較
    }

10、二叉樹的相加

將當(dāng)前二叉樹與參數(shù)btree二叉樹中對應(yīng)的數(shù)據(jù)元素相加，返回一棵在堆空間創(chuàng)建的新的二叉樹。
二叉樹相加實例如下：

定義將兩棵二叉樹相加的功能函數(shù)：

 BTreeNode* add(BTreeNode* l, BTreeNode* r)const
      {
          BTreeNode* ret = NULL;
          //二叉樹l為空
          if(l == NULL && r != NULL)
          {
            ret = clone(r);
          }
          //二叉樹r為空
          else if(l != NULL && r == NULL)
          {
            ret = clone(l);
          }
          //二叉樹l和二叉樹r不為空
          else if(l != NULL && r != NULL)
          {
              ret = BTreeNode::NewNode();
              if(ret != NULL)
              {
                  //根節(jié)點數(shù)據(jù)元素相加
                  ret->value = l->value + r->value;
                  //左子樹相加
                  ret->m_left = add(l->m_left, r->m_left);
                  //右子樹相加
                  ret->m_right = add(l->m_right, r->m_right);
                  //左子樹不為空，設(shè)置左子樹的父結(jié)點為當(dāng)前結(jié)點
                  if(ret->m_left != NULL)
                  {
                      ret->m_left->parent = ret;
                  }
                  //右子樹不為空，設(shè)置右子樹的父結(jié)點為當(dāng)前結(jié)點
                  if(ret->m_right != NULL)
                  {
                      ret->m_right->parent = ret;
                  }
              }
              else
              {
                  THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory...");
              }
          }
          return ret;
      }
        SharedPointer> add(const BTree& other)const
    {
        BTree* ret = new BTree();
        if(ret != NULL)
        {
            ret->m_root = add(root(), other.root());
        }
        else
        {
            THROW_EXCEPTION(NoEnoughMemoryException, "No enough memoty...");
        }
        return ret;
    }

三、二叉樹的典型遍歷方式

二叉樹有先序、中序、后序三種遍歷方式，三種遍歷方法的不同主要是取決于根節(jié)點的遍歷順序。

1、前序遍歷

如果二叉樹為空，則無操作，直接返回。
如果二叉樹非空，則執(zhí)行以下操作：
A、訪問根結(jié)點；
B、先序遍歷左子樹；
C、先序遍歷右子樹。
先序遍歷實現(xiàn)代碼：

void preOrderTraversal(BTreeNode* node, LinkedQueue*>& queue)
{
      if(node != NULL)
      {
          queue.add(node);
          preOrderTraversal(node->m_left, queue);
          preOrderTraversal(node->m_right, queue);
      }
 }

先序遍歷二叉樹示例：

2、中序遍歷

如果二叉樹為空，則無操作，直接返回。
如果二叉樹非空，則執(zhí)行以下操作：
A、中序遍歷左子樹；
B、訪問根結(jié)點；
C、中序遍歷右子樹。
中序遍歷實現(xiàn)代碼：

void inOrderTraversal(BTreeNode* node, LinkedQueue*>& queue)
{
  if(node != NULL)
  {
      inOrderTraversal(node->m_left, queue);
      queue.add(node);
      inOrderTraversal(node->m_right, queue);
  }
}

中序遍歷二叉樹示例：

3、后序遍歷

如果二叉樹為空，則無操作，直接返回。
如果二叉樹非空，則執(zhí)行以下操作：
A、后序遍歷左子樹；
B、后序遍歷右子樹；
C、訪問根結(jié)點。
后序遍歷實現(xiàn)代碼：

void postOrderTraversal(BTreeNode* node, LinkedQueue*>& queue)
{
  if(node != NULL)
  {
      postOrderTraversal(node->m_left, queue);
      postOrderTraversal(node->m_right, queue);
      queue.add(node);
  }
}

后序遍歷二叉樹示例：

4、遍歷算法的封裝

定義遍歷方式的枚舉類型：

  enum BTTraversal
    {
        PreOder,
        InOder,
        PostOder
    };

根據(jù)參數(shù)order選擇遍歷的方式，返回數(shù)組保存了二叉樹遍歷結(jié)點

 SharedPointer> traversal(BTTraversal order)
    {
        DynamicArray* ret = NULL;
        LinkedQueue*> queue;//保存遍歷二叉樹的結(jié)點
        switch (order)
        {
            case PreOder:
                preOrderTraversal(root(), queue);
                break;
            case InOder:
                inOrderTraversal(root(), queue);
                break;
            case PostOder:
                postOrderTraversal(root(), queue);
                break;
            default:
                THROW_EXCEPTION(InvalidParameterException, "Parameter invalid...");
                break;
        }
        ret = new DynamicArray(queue.length());
        if(ret != NULL)
        {
            for(int i = 0; i < ret->length(); i++, queue.remove())
            {
                ret->set(i, queue.front()->value);
            }
        }
        else
        {
            THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory...");
        }

        return ret;
    }

四、線索化二叉樹

1、線索化二叉樹簡介

線索化二叉樹是將二叉樹轉(zhuǎn)換為雙向鏈表的過程（將非線性的二叉樹轉(zhuǎn)換為線性的鏈表）。
二叉樹的線索化能夠反映某種二叉樹的遍歷次序（結(jié)點的先后訪問次序）。
線索化二叉樹的過程：

二叉樹線索化的實現(xiàn)：

通過某種遍歷方式遍歷二叉樹，根據(jù)遍歷次序?qū)⒍鏄浣Y(jié)點依次存儲到輔助隊列中，最后將輔助隊列中保存的結(jié)點依次出隊并連接（連接時，原二叉樹結(jié)點的m_left指針作為雙向鏈表結(jié)點的m_prev指針，指向結(jié)點的前驅(qū)；原二叉樹結(jié)點的m_right結(jié)點作為雙向鏈表結(jié)點的m_next指針，指向結(jié)點的后繼），成為雙向鏈表。

void traversal(BTTraversal order, LinkedQueue*>& queue)
    {
        switch (order)
        {
        case PreOrder:
            preOrderTraversal(root(), queue);
            break;
        case InOrder:
            inOrderTraversal(root(), queue);
            break;
        case PostOrder:
            postOrderTraversal(root(), queue);
            break;
        case LevelOrder:
            levelOrderTraversal(root(), queue);
            break;
        default:
            THROW_EXCEPTION(InvalidParameterException, "Parameter invalid...");
            break;
        }
    }

2、層次遍歷算法

增加層次遍歷方式LevelOrder到遍歷方式枚舉類型中。

enum BTTraversal
{
    PreOrder,//先序遍歷
    InOrder,//中序遍歷
    PostOrder,//后序遍歷
    LevelOrder//層次遍歷
};

層次遍歷算法：
A、將根結(jié)點入隊
B、訪問隊頭元素指向的二叉樹結(jié)點
C、將隊頭元素出隊，隊頭元素的孩子入隊
D、判斷隊列是否為空，如果非空，繼續(xù)B；如果為空，結(jié)束。

層次遍歷二叉樹的實例如下：

//層次遍歷
    void levelOrderTraversal(BTreeNode* node, LinkedQueue*>& queue)
    {
        if(node != NULL)
        {
            //輔助隊列
            LinkedQueue*> temp;
            //根結(jié)點壓入隊列
            temp.add(node);
           while(temp.length() > 0)
            {
                BTreeNode* n = temp.front();
                //如果左孩子不為空，將左孩子結(jié)點入隊
                if(n->m_left != NULL)
                {
                    temp.add(n->m_left);
                }
                //如果右孩子不為空，將右孩子結(jié)點入隊
                if(n->m_right != NULL)
                {
                    temp.add(n->m_right);
                }
                //將隊列的隊頭元素出隊
                temp.remove();
                //將隊列的隊頭元素入隊輸出隊列
                queue.add(n);
            }
        }
    }

3、隊列中結(jié)點的連接

將隊列中的所有結(jié)點連接成為一個線性的雙向鏈表

void connect(LinkedQueue*>& queue)
    {
        BTreeNode* ret = NULL;
        if(queue.length() > 0)
        {
            //返回隊列的隊頭元素指向的結(jié)點作為雙向鏈表的首結(jié)點
            ret = queue.front();
            //雙向鏈表的首結(jié)點的前驅(qū)設(shè)置為空
            ret->m_left = NULL;
            //創(chuàng)建一個游標(biāo)結(jié)點，指向隊列隊頭
            BTreeNode* slider = queue.front();
            //將隊頭元素出隊
            queue.remove();
           while(queue.length() > 0)
            {
                //當(dāng)前游標(biāo)結(jié)點的后繼指向隊頭元素
                slider->m_right = queue.front();
                //當(dāng)前隊頭元素的前驅(qū)指向當(dāng)前游標(biāo)結(jié)點
                queue.front()->m_left = slider;
                //將當(dāng)前游標(biāo)結(jié)點移動到隊頭元素
                slider = queue.front();
                //將當(dāng)前隊頭元素出隊，繼續(xù)處理新的隊頭元素
                queue.remove();
            }
            //雙向鏈表的尾結(jié)點的后繼為空
            slider->m_right = NULL;
        }
    }

4、線索化二叉樹的實現(xiàn)

線索化二叉樹函數(shù)接口的設(shè)計：
BTreeNode* thread(BTTraversal order)
A、根據(jù)參數(shù)order選擇線索化的方式（先序、中序、后序、層次）
B、返回值是線索化二叉樹后指向鏈表首結(jié)點的指針
C、線索化二叉樹后，原有的二叉樹被破壞，二叉樹的所有結(jié)點根據(jù)遍歷次序組建為一個線性的雙向鏈表，對應(yīng)的二叉樹應(yīng)為空。
線索化二叉樹的流程：

 BTreeNode* thread(BTTraversal order)
    {
        BTreeNode* ret = NULL;
        LinkedQueue*>* queue;
        //遍歷二叉樹，并按遍歷次序?qū)⒔Y(jié)點保存到隊列
        traversal(order, queue);
        //連接隊列中的結(jié)點成為雙向鏈表
        ret = connect(queue);
        //將二叉樹的根節(jié)點置空
        this->m_root = NULL;
        //將游標(biāo)遍歷的輔助隊列清空
        m_queue.clear();
        //返回雙向鏈表的首結(jié)點
        return ret;
    }

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機、免備案服務(wù)器”等云主機租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

網(wǎng)站題目：數(shù)據(jù)結(jié)構(gòu)（十四）——二叉樹-創(chuàng)新互聯(lián)
鏈接地址：http://weahome.cn/article/dojogj.html