二叉樹的建立與相關操作

1、二叉樹：是每個節點最多有兩個子樹的樹結構。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。

如圖：

2、二叉樹的每個結點至多隻有二棵子樹(不存在度大于2的結點)，二叉樹的子樹有左右之分，次序不能颠倒。

3、二叉樹的第i層至多有2^（i-1）個結點；深度為k的二叉樹至多有2^k-1個結點；對任何一棵二叉樹T，如果其終端結點數為n0，度為2的結點數為n2，則n0=n2+1。

4、一棵深度為k，且有2^k-1個節點稱之為滿二叉樹（如上圖）；深度為k，有n個節點的二叉樹，當且僅當其每一個節點都與深度為k的滿二叉樹中，序号為1至n的節點對應時，稱之為完全二叉樹。

如下圖：

一、建立二叉樹

假設我們要建立一個二叉樹：

對應數組為：char array[] = "abc##d##ef##g";

這是因為以下程式中設定無效值為‘#’，在遞歸的過程中，遇到無效值則置為NULL。

代碼如下：

// 根+左子樹+右子樹 
  PNode _CreateBinTree(const T* array, size_t size, size_t& index, const T& invalid)
  {
    if (NULL == array)
      return 0;
    PNode root = NULL;
    if (index < size && array[index] != invalid)
    {
      root = new Node(array[index]);
      root->_left = _CreateBinTree( array, size, ++index, invalid);
      root->_right = _CreateBinTree( array, size, ++index, invalid);
    }
    return root;
  }

在判斷語句中，最好将index<size放在前面，因為當越界後根本不需要判斷是否為有效值。

二、前中後周遊二叉樹

前序周遊：首先通路根，再周遊左子樹，最後周遊右子樹

// 根--->根的左子樹---->根的右子樹
  void _PreOrder(PNode& pRoot)
  {
    if (pRoot == NULL)
      return;
    cout << pRoot->_data << " ";
    _PreOrder(pRoot->_left);
    _PreOrder(pRoot->_right);
  }

中序周遊：首先周遊左子樹，再通路根，最後周遊右子樹。

// 左子樹--->根節點--->右子樹 
  void _InOrder(PNode pRoot)
  {
    //pNode pCur = pRoot;
    if (pRoot == NULL)
      return;
    _InOrder(pRoot->_left);
    cout << pRoot->_data << " ";
    _InOrder(pRoot->_right);
  }

後序周遊：首先周遊左子樹，再周遊右子樹，最後通路根。

// 左子樹--->右子樹--->根節點 
  void _PostOrder(PNode pRoot)
  {
    if (pRoot == NULL)
      return;
    _PostOrder(pRoot->_left);
    _PostOrder(pRoot->_right);
    cout << pRoot->_data << " "; 
  }

三、層序周遊二叉樹

按照層次通路，通路根，通路子女，再通路子女的子女。

這裡遞歸很難實作，我們利用了隊列的特性，建立一個隊列，先将根節點入隊，将隊頭的資料列印并出隊，再看左右節點，如果左節點不為空，将左節點入隊，如果右節點不為空，将右節點入隊。

代碼如下：

void _LeverOrder(PNode pRoot)
  {
    if (NULL == pRoot)
      return;
    queue<PNode> q;
    q.push(pRoot);
    while (!q.empty())
    {
      PNode front = q.front();
      cout << front->_data << " ";
      q.pop();

      if (front->_left)
        q.push(front->_left);
      if (front->_right)
        q.push(front->_right);
    }
  }

四、求二叉樹的高度

先求出左子樹的高度，和右子樹比較。

size_t _Height(PNode pRoot)
  {
    if (NULL == pRoot)
      return 0;
    return 1+(_Height(pRoot->_left) > _Height(pRoot->_right)?_Height(pRoot->_left): _Height(pRoot->_right));
  }

五、求二叉樹中節點的個數

size_t _Size(PNode pRoot)
  {
    if (NULL == pRoot)
      return 0;
    return _Size(pRoot->_left) + _Size(pRoot->_right) + 1;
  }

六、求葉子節點的個數

size_t _GetLeafCount(PNode pRoot)
  {
    if (NULL == pRoot)
      return 0;
    if (pRoot->_left == NULL&&pRoot->_right == NULL)
      return 1;
    return _GetLeafCount(pRoot->_left) + _GetLeafCount(pRoot->_right);
  }

七、求二叉樹中第k層節點的個數

size_t _GetKLevelCount(PNode pRoot, int K)
  {
    if (NULL == pRoot || K < 1)
      return 0;
    if (K == 1)
      return 1;
    int leftLevel = _GetKLevelCount(pRoot->_left, K - 1);
    int rightLevel = _GetKLevelCount(pRoot->_right, K - 1);
    return leftLevel + rightLevel;
  }

八、求一個節點的雙親節點，及左、右孩子節點。

PNode _Parent(PNode pRoot, PNode pNode)
  {
    if (pNode == pRoot->_left || pNode == pRoot->_right)
      return pRoot;
    if (pRoot->_left)
    {
      _Parent(pRoot->_left, pNode);
    }
    if (pRoot->_right)
    {
      _Parent(pRoot->_right, pNode);
    }
    return pRoot;
  }

PNode LeftChild(PNode pNode)
  {
    if (NULL == pNode)
      return NULL;
    return pNode->_left;
  }

  PNode RightChild(PNode pNode)
  {
    if (NULL == pNode)
      return NULL;
    return pNode->_right;
  }

還有一些輔助函數，比如尋找某一進制素所在節點。

整體代碼如下：

#include<iostream>
using namespace std;
#include<queue>
#include<string.h>

template<class T>
struct TreeNode
{
  T _data;
  TreeNode *_left;
  TreeNode *_right;
  TreeNode(const T& data)
    :_data(data)
    , _left(NULL)
    , _right(NULL)
  {}
};

template<class T>
class BinTree
{
  typedef TreeNode<T> Node;
  typedef TreeNode<T> *PNode;
public:
  BinTree()
    : _pRoot(NULL)
  {}

  BinTree(const T* array, size_t size, const T& invalid)
  {
    size_t index = 0;
    _pRoot = _CreateBinTree(array, size, index, invalid);
  }

  BinTree(const BinTree& bt)
  {
    _pRoot = _CopyBinTree(bt._pRoot);
  }

  BinTree& operator=(const BinTree& bt)
  {
    if (this == bt)
      return;
    _DestroyBinTree(_pRoot);
    _pRoot = new Node(bt->_data);
    _pRoot->_left = bt->_left;
    _pRoot->_right = bt->_right;
  }

  ~BinTree()
  {
    _DestroyBinTree(_pRoot);
  }
  void PreOrder()
  {
    _PreOrder(_pRoot);
    cout << endl;
  }

  void InOrder()
  {
    _InOrder(_pRoot);
    cout << endl;
  }

  void PostOrder()
  {
    _PostOrder(_pRoot);
    cout << endl;
  }

  void LevelOrder()
  {
    _LeverOrder(_pRoot);
    cout << endl;
  }

  size_t Size()
  {
    return _Size(_pRoot);
  }

  size_t GetLeafCount()
  {
    return _GetLeafCount(_pRoot);
  }

  // 擷取第K層結點的個數 
  size_t GetKLevelCount(size_t K)
  {
    return _GetKLevelCount(_pRoot, K);
  }

  size_t Height()
  {
    return _Height(_pRoot);
  }

  PNode Find(const T& data)
  {
    return _Find(_pRoot, data);
  }

  PNode Parent(PNode pNode)
  {
    return _Parent(_pRoot, pNode);
  }

  PNode LeftChild(PNode pNode)
  {
    if (NULL == pNode)
      return NULL;
    return pNode->_left;
  }

  PNode RightChild(PNode pNode)
  {
    if (NULL == pNode)
      return NULL;
    return pNode->_right;
  }
private:
  // 根+左子樹+右子樹 
  PNode _CreateBinTree(const T* array, size_t size, size_t& index, const T& invalid)
  {
    if (NULL == array)
      return 0;
    PNode root = NULL;
    if (index < size && array[index] != invalid)
    {
      root = new Node(array[index]);
      root->_left = _CreateBinTree( array, size, ++index, invalid);
      root->_right = _CreateBinTree( array, size, ++index, invalid);
    }
    return root;
  }

  PNode _CopyBinTree(PNode pRoot)
  {
    if (this == pRoot)
      return;
    if (pRoot)
    {
      _pRoot = new Node(pRoot->_data);
      _pRoot->_left = _CopyBinTree(pRoot->_left);
      _pRoot->_right = _CopyBinTree(pRoot->_right);
    }
    return *this;
  }

  void _DestroyBinTree(PNode pRoot)
  {
    if (NULL == pRoot)
      return;
    if (pRoot)
    {
      _Destroy(pRoot->_left);
      _Destroy(pRoot->_right);
      delete pRoot;
      pRoot = NULL;
    }
  }

  // 根--->根的左子樹---->根的右子樹
  void _PreOrder(PNode& pRoot)
  {
    if (pRoot == NULL)
      return;
    cout << pRoot->_data << " ";
    _PreOrder(pRoot->_left);
    _PreOrder(pRoot->_right);
  }

  // 左子樹--->根節點--->右子樹 
  void _InOrder(PNode pRoot)
  {
    //pNode pCur = pRoot;
    if (pRoot == NULL)
      return;
    _InOrder(pRoot->_left);
    cout << pRoot->_data << " ";
    _InOrder(pRoot->_right);
  }

  // 左子樹--->右子樹--->根節點 
  void _PostOrder(PNode pRoot)
  {
    if (pRoot == NULL)
      return;
    _PostOrder(pRoot->_left);
    _PostOrder(pRoot->_right);
    cout << pRoot->_data << " "; 
  }

  //層次周遊
  void _LeverOrder(PNode pRoot)
  {
    if (NULL == pRoot)
      return;
    queue<PNode> q;
    q.push(pRoot);
    while (!q.empty())
    {
      PNode front = q.front();
      cout << front->_data << " ";
      q.pop();

      if (front->_left)
        q.push(front->_left);
      if (front->_right)
        q.push(front->_right);
    }
  }

  size_t _Size(PNode pRoot)
  {
    if (NULL == pRoot)
      return 0;
    return _Size(pRoot->_left) + _Size(pRoot->_right) + 1;
  }

  size_t _GetLeafCount(PNode pRoot)
  {
    if (NULL == pRoot)
      return 0;
    if (pRoot->_left == NULL&&pRoot->_right == NULL)
      return 1;
    return _GetLeafCount(pRoot->_left) + _GetLeafCount(pRoot->_right);
  }

  size_t _Height(PNode pRoot)
  {
    if (NULL == pRoot)
      return 0;
    return 1+(_Height(pRoot->_left) > _Height(pRoot->_right)?_Height(pRoot->_left): _Height(pRoot->_right));
  }

  PNode _Find(PNode pRoot, const T& data)
  {
    if (data == pRoot->_data)
      return pRoot;
    if (pRoot->_left)
    {
      _Find(pRoot->_left, data);
    }
    if (pRoot->_right)
    {
      _Find(pRoot->_right, data);
    }
  }

  PNode _Parent(PNode pRoot, PNode pNode)
  {
    if (pNode == pRoot->_left || pNode == pRoot->_right)
      return pRoot;
    if (pRoot->_left)
    {
      _Parent(pRoot->_left, pNode);
    }
    if (pRoot->_right)
    {
      _Parent(pRoot->_right, pNode);
    }
    return pRoot;
  }

  size_t _GetKLevelCount(PNode pRoot, int K)
  {
    if (NULL == pRoot || K < 1)
      return 0;
    if (K == 1)
      return 1;
    int leftLevel = _GetKLevelCount(pRoot->_left, K - 1);
    int rightLevel = _GetKLevelCount(pRoot->_right, K - 1);
    return leftLevel + rightLevel;
  }

private:
  PNode _pRoot;
};

測試，傳文章開頭所示的數組，如下：

int main()
{
    char array[] = "abc##d##ef##g";
    BinTree<char> bt(array,strlen(array),'#');

    cout << bt.GetKLevelCount(2) << endl;

    cout << bt.GetLeafCount() << endl;

    cout << bt.Height() << endl;

    bt.PreOrder();
    bt.InOrder();
    bt.PostOrder();
    bt.LevelOrder();

    cout << bt.LeftChild(bt.Find('a'))->_data << endl;
    cout << bt.RightChild(bt.Find('a'))->_data << endl;

    cout << bt.Parent(bt.Find('b'))->_data << endl;

    cout << bt.Size() << endl;

    system("pause");
    return 0;
}

結果如下：

二叉樹的建立與相關操作

繼續閱讀

CSU 1811 Tree Intersection

LeetCode 102.二叉樹的層次周遊

圖解

計算二叉樹的高度（C++實作）

繩索資料結構（字元串快速拼接）

平衡二叉樹詳解筆記

真二叉樹重構(Proper Rebuild)

653. 兩數之和 IV - 輸入 BST653. 兩數之和 IV - 輸入 BST

(刷題筆記)Leetcode 653.兩數之和 IV - 輸入 BST題目解題思路代碼(C++)

【算法導論】堆排序一、數組轉換成堆二、如何進行堆排序三、堆排序過程四、堆排序時間複雜度

二叉樹三種周遊(先序，中序，後序)----超詳細引入先序周遊後序周遊中序周遊總結

二叉樹的先序、中序、後序周遊總結

二叉樹及其應用--二叉樹建立

用JS模拟實作二叉樹(含周遊)

資料結構---二叉樹（手動建立及周遊）

樹的基本概念(定義、基本術語、性質)