二叉树的创建与相关操作

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模拟实现二叉树(含遍历)

数据结构---二叉树（手动创建及遍历）

树的基本概念(定义、基本术语、性质)