二叉樹線索化以及線索化前序、中序、後序周遊

二叉樹線索化以及線索化前序、中序、後序周遊

前面已經對二叉樹的建立與建立有了一定了解，那二叉樹的線索化又是什麼呢？

二叉樹雖然是非線性結構，但二叉樹的周遊卻為二叉樹的節點導出了一個線性序列。

用二叉樹作為存儲結構時，取到一個節點，隻能擷取節點的左孩子和右孩子，不能直接得到節點的任一周遊序列的前驅或者後繼。

為了儲存這種在周遊中需要的資訊，我們利用二叉樹中指向左右子樹的空指針來存放節點的前驅和後繼資訊

利用二叉樹中的空指針域來存放在某種周遊次序下的前驅和後繼，這種指針叫“線索”。這種加上了線索的二叉樹稱為線索二叉樹。

根據線索的性質的不同，線索二叉樹分為：前序線索二叉樹 ， 中序線索二叉樹 ， 後序線索二叉樹

節點結構如下：

enum PointerTag{ LINK, THREAD };

template<class T>
struct BinTreeNodeTread
{
  BinTreeNodeTread(const T& data)
  : _pLeft(NULL)
  , _pRight(NULL)
  , _leftThread(LINK)
  , _rightThread(LINK)
  , _data(data)
  {}

  BinTreeNodeTread* _pLeft;
  BinTreeNodeTread* _pRight;
  PointerTag _leftThread; // 左線索 
  PointerTag _rightThread; // 右線索 
  T _data;
};      

_leftThread标記是否有左子樹，值為LINK表示有左孩子，值為THREAD表示沒有左孩子，則有前驅；

_rightThread标記是否有右子樹，值為LINK表示有右孩子，值為THREAD表示沒有右孩子，則有後繼；

一、要線索化二叉樹，首先我們要建立二叉樹。

//建立二叉樹
  void _CreateBinTree(PNode& pRoot, const T* array, size_t size, size_t& index, const T& invalid)
  {
    if (array == NULL || size == 0)
      return;
    PNode root = NULL;
    if (index < size && array[index] != invalid)
    {
      root = new Node(array[index]);
      _CreateBinTree(root->_pLeft, array, size, ++index, invalid);
      _CreateBinTree(root->_pRight, array, size, ++index, invalid);
      pRoot = root;
    }
  }      

二、前序線索化二叉樹

先來看一下圖：

// 前序線索化二叉樹：根節點--->左子樹--->右子樹 
  void _PreThreading(PNode pRoot, PNode& prev)
  {
    if (NULL == pRoot)
      return;
    if (pRoot->_pLeft == NULL)  //沒有左子樹  
    {
      pRoot->_pLeft = prev;     //前驅 
      pRoot->_leftThread = THREAD;
    }
    if (prev != NULL&&prev->_pRight == NULL)// 上一個節點有沒有右子樹 
    {
      prev->_pRight = pRoot;
      prev->_rightThread = THREAD;
    }
    prev = pRoot;   //前驅,每次記住上次的節點  

    //判斷Root是否有左右孩子  
    if (pRoot->_leftThread == LINK)
      _PreThreading(pRoot->_pLeft, prev);
    if (pRoot->_rightThread == LINK)
      _PreThreading(pRoot->_pRight, prev);
  }      

前序線索二叉樹周遊

//前序周遊二叉樹遞歸
  void _PreOrder(PNode pRoot)
  {
    if (NULL == pRoot)
      return;
    cout << pRoot->_data << " ";
    if (pRoot->_leftThread == LINK)
      _PreOrder(pRoot->_pLeft);
    if (pRoot->_rightThread == LINK)
      _PreOrder(pRoot->_pRight);
  
  }
  //前序周遊二叉樹非遞歸
  void _PreOrderNor(PNode pRoot)
  {
    if (NULL == pRoot)
      return;
    PNode pCur = pRoot;
    while (pCur)
    {
      //找最左側路徑中的所有節點并通路
      while (pCur->_leftThread == LINK)
      {
        cout << pCur->_data << " ";
        pCur = pCur->_pLeft;
      }
      cout << pCur->_data << " ";

      pCur = pCur->_pRight;
    }
  }      

三、中序線索二叉樹

// 中序：左子樹--->根節點--->右子樹 
  void _InThreading(PNode pRoot, PNode& prev)
  {
    if (NULL == pRoot)
      return;
    _InThreading(pRoot->_pLeft, prev); //線索化左子樹

    if (pRoot->_pLeft == NULL)   //沒有左子樹
    {
      pRoot->_pLeft = prev;
      pRoot->_leftThread = THREAD;
    }
    if (prev&&prev->_pRight == NULL)  //沒有右孩子
    {
      prev->_pRight = pRoot;
      prev->_rightThread = THREAD;
    }
    prev = pRoot;

    if (pRoot->_rightThread == LINK)
      _InThreading(pRoot->_pRight, prev);//線索化右子樹  
  }      

中序線索二叉樹周遊：

//中序周遊二叉樹遞歸
  void _InOrder(PNode pRoot)
  {
    if (NULL == pRoot)
      return;
    if (pRoot->_leftThread == LINK)
      _InOrder(pRoot->_pLeft);
    cout << pRoot->_data << " ";
    if (pRoot->_rightThread == LINK)
      _InOrder(pRoot->_pRight);
  }

  //中序周遊二叉樹非遞歸
  void _InOrderNor(PNode pRoot)
  {
    if (NULL == pRoot)
      return;
    PNode pCur = pRoot;
    while (pCur)
    {
      while (pCur->_leftThread == LINK)  //找最左側路徑中的節點并通路
      { 
        pCur = pCur->_pLeft;
      }

      cout << pCur->_data << " ";

      while (pCur->_rightThread == THREAD)
      {
        pCur = pCur->_pRight;
        if (pCur == NULL)
        {
          cout << endl;
          return;
        }
        cout << pCur->_data << " ";
      }
      if (pCur != NULL)
      {
        pCur = pCur->_pRight;
      }
    }
  }      

四、後序線索二叉樹

線索化：

// 後序：左子樹--->右子樹--->根節點 
  void _PostThreading(PNode pRoot, PNode& prev)
  {
    if (NULL == pRoot)
      return;
    _PostThreading(pRoot->_pLeft, prev);  //線索化左子樹
    _PostThreading(pRoot->_pRight, prev);//線索化右子樹  

    if (pRoot->_pLeft == NULL)   //沒有左子樹
    {
      pRoot->_pLeft = prev;
      pRoot->_leftThread = THREAD;
    }
    if (prev != NULL&&prev->_pRight == NULL)  //沒有右孩子
    {
      prev->_pRight = pRoot;
      prev->_rightThread = THREAD;
    }
    prev = pRoot;
  }      

後序線索化周遊：