二叉树的基本功能实现方法（C++）

假设：有一个n个元素的完全二叉树，为了使其成为满二叉树，补全没有孩子的节点是的除了叶节点所有节点都有两个孩子，即最低层皆为-1.

例1：

　　　　　　　　　2 　　　　　　　　3

　　　　　　4　　　　 5 　　　　-1 　　　6

　　　　　-1 -1 　-1 -1 　-1 -1

补全的节点赋值为-1，表示当前无节点，需转向别的子树。

step 1：首先，对于一棵二叉树，需定义一个节点的类模板：

包括：节点键值、左子树指针、右子树指针

template <typename T>
class binaryTreeNode {
public:
    T element;
    binaryTreeNode<T>* leftChild;
    binaryTreeNode<T>* rightChild;
    
    binaryTreeNode(){leftChild = NULL;rightChild = NULL;}
};

step 2：如何创建一棵二叉树呢？根据链表的特性，成员变量为：节点指针类型的mRoot根节点。除此之外，还包括常见的成员函数：如获取树的当前规模、获取树的深度、打印或输出树及销毁二叉树等操作。

 1 template <typename T>
 2 class binaryTree {
 3 private:
 4     binaryTreeNode<T>* mRoot;//树根
 5     
 6     
 7     int getSize(binaryTreeNode<T>*);
 8     int getHeight(binaryTreeNode<T>*);
 9     
10     void preOrder(binaryTreeNode<T>*);
11     void inOrder(binaryTreeNode<T>*);
12     void postOrder(binaryTreeNode<T>*);
13     void distroy(binaryTreeNode<T>*&);
14     binaryTreeNode<T>* AddNode(const T& key,int direction,binaryTreeNode<T>*& root);
15     
16 public:
17     binaryTree();
18     virtual ~binaryTree();
19     binaryTreeNode<T>* Create();//递归的创建二叉树的节点
20     void AddNode(const T& key,int direction);
21     
22     int getSize();//递归得到树的节点数目
23     int getHeight();//递归得到树的高度
24     
25     //递归遍历
26     void preOrder();//前序遍历
27     void inOrder();//中序遍历
28     void postOrder();//后序遍历
29     
30     //删除二叉树
31     void distroy();
32     
33 };

View Code

>>首先，怎么在二叉树中插入节点呢？
可以想到的是，插入新节点的时候需要标明插得是左孩子还是右孩子which，在哪一个父节点下插入where，及插入的键值是多少what，简单的来说，就是WWW问题。

 1 template <typename T>
 2 binaryTreeNode<T>* binaryTree<T>::AddNode(const T& key,int direction,binaryTreeNode<T>*& root)
 3 {
 4     if(direction == 0)//左孩子
 5     {
 6         if(root->leftChild == NULL){//找到对应的叶节点插入
 7             root->leftChild = new binaryTreeNode<T>(key);
 8         }
 9         else{
10             root->leftChild = AddNode(key, direction, root->leftChild);
11         }
12     }
13     
14     else//右孩子
15     {
16         if (root->rightChild == NULL) {//找到相应的叶节点插入
17             root->rightChild = new binaryTreeNode<T>(key);
18         }
19         else{
20             root->rightChild = AddNode(key, direction, root->rightChild);
21         }
22     }
23     
24     return root;
25 }
26 
27 template <typename T>
28 void binaryTree<T>::AddNode(const T& key,int direction)
29 {
30     AddNode(key, direction, mRoot);
31 }

了解了这个思路后，可以不用一个个插入节点，用输入流的方式直接创建一棵树，如下程序：

 1 template <typename T>
 2 binaryTreeNode<T>* binaryTree<T>::Create(){
 3     
 4     binaryTreeNode<T>* current = NULL;
 5     
 6     T val;
 7     
 8     cin >> val;//输入键值
 9     
10     if(val == -1)//标识当前子树为空，转向下一节点
11     {
12         return NULL;
13     }
14     
15     else{//递归的创建左右子树
16         current = new binaryTreeNode<T>;
17         current->element = val;
18         current->leftChild = Create();
19         current->rightChild = Create();
20         return current;
21     }
22 }

可以发现，-1是一个过渡标识，标明当前从递归左子树转向递归右子树。而上述创建程序是一个前序遍历，所谓前序遍历是指：

　　1.先访问父节点

　　2.递归左子树

　　3.递归右子树

时间复杂度是O(N)，因为遍历了每一个节点。

>>创建了二叉树后，怎么销毁？其实只要一一删除每个节点即可，考虑到链表结构，我们不能使用下标去删除节点，只能一个个的访问，而二叉树典型的遍历方法有：前序遍历、中序遍历及后序遍历。在这里，我们使用后序遍历进行递归删除, 即自下而上的删除。

 1 /*二叉树的销毁操作：后序遍历删除
 2 
 3 1）不能使用该声明：void distroy(binaryTreeNode<T>* pNode);该声明会创建一个局部的临时对象来保存传递的指针
 4 虽然实参指针和局部指针都执行同一块堆空间，delete局部指针也会删除二叉树结构所占用的堆内存
 5 但是实参指针将出现无所指的状态，出现不可预料的错误
 6 因此传递的是指针的引用，这样才能将实参指针置空。
 7 
 8 2）使用递归方法释放节点
 9  
10 */
11 
12 template <typename T>
13 void binaryTree<T>::distroy(binaryTreeNode<T>*& pNode)
14 {
15     if(pNode)
16     {
17         distroy(pNode->leftChild);
18         distroy(pNode->rightChild);
19         delete pNode;
20         pNode = NULL;
21     }
22 }
23 template <typename T>
24 void binaryTree<T>::distroy()
25 {
26     distroy(mRoot);
27 }

如要删除如上例1中的二叉树，删除过程依次为：4 5 2 6 3 1

>>对于获取树的深度，有一种方法是，获取左右子树的深度，比较子树深度大小，大的那个增1即为树的深度了。当然，也是递归实现。

 1 template <typename T>
 2 int binaryTree<T>::getHeight()
 3 {
 4     return getHeight(mRoot);
 5 }
 6 /*
 7 获取当前节点的深度
 8  递归的方法首先要设置截止条件，在进行递归操作。
 9  0.约束条件：节点为空
10  1.递归左子树,每次递归加1
11  2.递归右子树，每次递归加1
12  3.比较左右子树深度，更深的子树+1即为当前节点深度。
13 */
14 
15 template <typename T>
16 int binaryTree<T>::getHeight(binaryTreeNode<T>* node)
17 {
18     if(node == NULL)
19         return 0;
20     else{
21         int depL = getHeight(node->leftChild);
22         int depR = getHeight(node->rightChild);
23         return (depL > depR) ? depL+1 : depR+1;
24     }
25         
26 }

>>同理，获取树的规模只要遍历整棵树即可，这里用递归实现。这里仅给出前序遍历，后序遍历和中序遍历类似则不再给出。

 1 template <typename T>
 2 void binaryTree<T>::preOrder()
 3 {
 4     cout <<"前序遍历： ";
 5     preOrder(mRoot);
 6     cout << endl;
 7 }
 8 
 9 /*
10  前序遍历：
11  1.由于是递归实现，所以要设置截止条件：当前节点为空
12  2.先访问父节点，再访问左节点，最后访问右孩子
13  
14  */
15 template <typename T>
16 void binaryTree<T>::preOrder(binaryTreeNode<T>* node)
17 {
18     if(node == NULL)
19         return;
20     else{
21         cout << node->element <<' ';
22         preOrder(node->leftChild);
23         preOrder(node->rightChild);
24     }
25 }

对于例1的遍历结果，如下：

输入：1 2 4 -1 -1 5 -1 -1 3 -1 6 -1 -1
前序遍历： 1 2 4 5 3 6  
中序遍历： 4 2 5 1 3 6  
后序遍历： 4 5 2 6 3 1 
树的高度为： 3
树的节点数目： 6

>>总之呢，创建二叉树的全过程都用到了递归，那么递归到底是什么呢？

从定义上来讲：递归作为一种算法，是让函数/子程序/过程在程序运行过程中调用自身的方法，能够把一个较为复杂的问题经过层层转换，得到一个与原问题相似但是规模大大减小的问题来求解。递归方法大大减少了代码的复杂度。

实现方法：首先递归必须设置一个终止条件，当满足终止条件时，则递归返回。除此之外，则递归调用自身。