二叉树的基本操作

二叉树的基本操作多是由递归来实现的，包括其创建、遍历等。
根据其结构，分为根、左子树、右子树来进行相应的操作。

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

template<class T>
struct  BinaryTreeNode
{
T _data;
BinaryTreeNode<T>* _left;
BinaryTreeNode<T>* _right;

BinaryTreeNode(const T& x)
        : _data(x)
        , _left(NULL)
        , _right(NULL)
    {}
};

template<class T>
class BinaryTree
{
 typedef BinaryTreeNode<T> Node;
public:
BinaryTree()
 :_root(NULL)
 {}

BinaryTree(T* a, size_t n, const T& invalid)
 {
 size_t index = 0;
 _root = _CreatTree(a, n, invalid, index);
 }

 ~BinaryTree()
 {
 _Destroy(_root);
 }

 void Destroy()//后序遍历释放
 {
 _Destroy(_root);
 }

 void PrevOrder()//前序遍历 根 左子树 右子树
 {
 _Prevorder(_root);
 cout << endl;
 }

 void InOrder()//中序 左子树 根 右子树
 {
 _InOrder(_root);
 cout << endl;
 }

 void PostOrder()//后续 左子树 右子树 根
 {
 _PostOrder(_root);
 cout << endl;
 }

 void LevelOrder()//层序 队列
 {
 _LevelOrder(_root);
 }

Node* Find(const T& x)
 {
 return _Find(_root, x);
 }

 size_t LeafSize()//叶节点个数
 {
 return _LeafSize(_root);
 }

 size_t Depth()//深度
 {
 return _Depth(_root);
 }

 size_t GetKleveSize(size_t k)//第k层节点个数
 {
 assert(k > 0);
 return _GetKleveSize(_root, k);
 }

 size_t Size()//节点个数 = 左子树节点 + 右子树节点
 {
 return _Size(_root);
 }

protected:
Node* _CreatTree(T* a, size_t n, const T& invalid, size_t& index)
 {
Node* root = NULL;
 if (index < n&&a[index] != invalid)
 {
 root = new Node(a[index]);
 root->_left = _CreatTree(a, n, invalid, ++index);
 root->_right = _CreatTree(a, n, invalid, ++index);
 }
 return root;
 }

 void _Destroy(Node* root)
 {
 if (root == NULL)
 {
 return;
 }
 _Destroy(root->_left);
 _Destroy(root->_right);
 delete root;
 }

 void _Prevorder(Node* root)
 {
 if (root == NULL)
 {
 return;
 }
 cout << root->_data << " ";
 _Prevorder(root->_left);
 _Prevorder(root->_right);
 }

 void _InOrder(Node* root)
 {
 if (root == NULL)
 {
 return;
 }
 _InOrder(root->_left);
 cout << root->_data << " ";
 _InOrder(root->_right);
 }

 void _PostOrder(Node* root)
 {
 if (root == NULL)
 {
 return;
 }
 _PostOrder(root->_left);
 _PostOrder(root->_right);
 cout << root->_data << " ";
 }

 void _LevelOrder(Node* root)
 {
 if (root == NULL)
 return;
 queue<Node*> q;
 if (root)
 {
 q.push(root);
 }

 while (!q.empty())
 {
Node* front = q.front();
 cout << front->_datas << " ";
 q.pop();
 if (front->_left)
 q.push(front->_left);
 if (front->_right)
 q.push(front->_right);
 }
 cout << endl;
 }

Node* _Find(Node* root,const T& x)
 {
 if (root == NULL)
 {
 return NULL;
 }
 if (root->_data == x)
 {
 return root;
 }

Node* ret = _Find(root->_left, x);
 if (ret)
 return ret;
 return _Find(root->_right, x);
 }

 size_t _LeafSize(Node* root)
 {
 if (root == NULL)
 {
 return 0;
 }
 if ((root->_left == NULL) && (root->_right == NULL))
 {
 return 1;
 }
 return _LeafSize(root->_left) + _LeafSize(root->_right);
 }

 size_t _Depth(Node* root)
 {
 if (root == NULL)
 {
 return 0;
 }
 if (root->_left == NULL&&root->_right == NULL)
 {
 return 1;
 }
 size_t left = _Depth(root->_left);
 size_t right = _Depth(root->_right);
 return left > right ? left + 1 : right + 1;
 }

 size_t _GetKleveSize(Node* root, size_t k)
 {
 if (root == NULL)
 {
 return 0;
 }
 if (k == 1)
 {
 return 1;
 }
 return _GetKleveSize(root->_left, k - 1) + _GetKleveSize(root->_right, k - 1);

 }

 size_t _Size(Node* root)
 {
 if (root == NULL)
 {
 return 0;
 }

 return _Size(root->_left) + _Size(root->_right) + 1;
 }

private:
Node* _root;
};

void BinaryTreeTest()
{
 int a[10] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 };
BinaryTree<int> t1(a, 10, '#');
 t1.PostOrder();
 t1.InOrder();
 t1.PrevOrder();
 t1.LevelOrder();
}

int main()
{
BinaryTreeTest();
 return 0;
}