二叉树的相关操作

二叉树:二叉树是一棵特殊的树，二叉树每个节点最多有两个孩子结点，分别称为左孩子和右孩子。

#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<assert.h>
#include<stack>
#include<queue>

using namespace std;
//节点结构
template<class T>
class BinaryTreeNode//节点
{
public:
BinaryTreeNode(const T& data)
:_data(data)
,_left(NULL)
,_right(NULL)
{}
T _data;//值
BinaryTreeNode* _left;//左子树
BinaryTreeNode* _right;//右子树
};
template<class T>
class BinaryTree
{
typedef BinaryTreeNode<T> Node;
public:
BinaryTree()//无参构造函数
:_root(NULL)
{}
BinaryTree(const T* a, size_t size, const T& invalid)//构造函数
{
assert(a);
size_t index = 0;
_root = _CreateTree(a, size, invalid, index);
}
BinaryTree(const BinaryTree<T>& t)//拷贝构造
{
_root = _Copy(t._root);
}
BinaryTree<T>& operator=(const BinaryTree<T>& t)//赋值函数
{
if (this != &t)
{
BinaryTreeNode<T>* tmp = _Copy(t._root);
_Destroy(_root);
_root = temp;
}
return *this;
}
~BinaryTree()//析构
{
_Destroy(_root);
_root = NULL;
}
public:
void PrevOrder()//先根遍历
{
cout << "先根遍历:";
_PrevOrder(_root);
cout << endl;
}
void InOrder()//中根遍历
{
cout << "中根遍历:";
_InOrder(_root);
cout << endl;
}
void PostOrder()//后根遍历
{
cout << "后根遍历:";
_PostOrder(_root);
cout << endl;
}
void LevelOrder()//层次遍历
{
cout << "层次遍历:";
_LevelOrder(_root);
cout << endl;
}
size_t Size()//求二叉树的节点的个数
{
return _Size(_root);
}
size_t Depth()//求二叉树的深度
{
return _Depth(_root);
}
size_t LeafSize()//叶子节点个数
{
return _LeafSize(_root);
}
protected:
Node* _CreateTree(const T* a, size_t size, const T& invalid, size_t&  index)
//index要传引用，需要更改index的值
{
Node* root = NULL;
//判断数组是否越界和输入的值是否合法
if (index < size&&a[index] != invalid)
{
root = new Node(a[index]);//创建根节点
root->_left = _CreateTree(a, size, invalid, ++index);//递归创建左子树
root->_right = _CreateTree(a, size, invalid, ++index);//递归创建右子树
}
return root;//返回根节点
}
//void _PrevOrder(Node* root)
//{
////如果节点为空则直接返回
//if (root == NULL)
//{
//return;
//}
//cout << root->_data << " ";//访问根节点
//_PrevOrder(root->_left);//递归访问左子树
//_PrevOrder(root->_right);//递归访问右子树
//}
void _PrevOrder(Node* root)
{
stack<Node*> s;
if (root==NULL)
{
return;
}
s.push(root);
while (!s.empty())
{
root = s.top();
cout << root->_data << " ";
s.pop();
if (root->_right)
{
s.push(root->_right);
}
if (root->_left)
{
s.push(root->_left);
}
}
}
//void _InOrder(Node* root)
//{
////如果节点为空则直接返回
//if (root == NULL)
//{
//return;
//}
//_InOrder(root->_left);//递归访问左子树
//cout << root->_data << " ";//递归访问根节点
//_InOrder(root->_right);//递归访问右子树
//}
void _InOrder(Node* root)
{
if (root == NULL)
{
return;
}
stack<Node*> s;
Node* cur = root;
while (cur || !s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
cur = s.top();//将栈顶元素保存，以便后面判断它是否有有孩子
cout << s.top()->_data << " ";
s.pop();
if (cur->_right == NULL)
{
cur = NULL;
}
else
{
cur = cur->_right;
}
}
}
//void _PostOrder(Node* root)
//{
//if(root == NULL)
//{
//return;
//}
//_PostOrder(root->_left);//递归访问左子树
//_PostOrder(root->_right);//递归访问右子树
//cout << root->_data << " ";//递归访问根节点
//}
void _PostOrder(Node* root)
{
if (root == NULL)
{
return;
}
Node* cur = root;
Node* prev = NULL;
stack<Node*> s;
while (cur || !s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
cur = s.top();
if (cur->_right == NULL || cur->_right == prev)
{
cout << cur->_data << " ";
s.pop();
prev = cur;
cur = NULL;
}
else
{
cur = cur->_right;
}
}
}
void  _Destory(Node* root)//析构---相当于后序删除
{
if (root == NULL)
{
return;
}
//删除叶结点
if (root->_left== NULL&&root->_right == NULL)
{
delete root;
root = NULL;
return;
}
_Destory(root->_left);//递归删除左子树
_Destory(root->_right);//递归删除右子树
delete root;
}
size_t _Size(Node* root)//节点的个数
{
size_t count = 0;
if (root == NULL)
{
return count;//树为空
}
count = _Size(root->_left) + _Size(root->_right);
return count + 1;
}
size_t _Depth(Node* root)//树的深度
{
size_t left = 0;
size_t right = 0;
size_t max = 0;
if (root == 0)
{
return 0;
}
else
{
left = _Depth(root->_left);
right = _Depth(root->_right);
max = left > right ? left : right;
return max + 1;
}
}
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);
}
Node* _Copy(Node* root)
{
if (roo == NULL)
{
return;
}
Node* newroot = new Node(root->_data);
newroot->_left = Copy(root->_left);
newroot->_right = Copy(root->_right);
return newroot;
}
void _LevelOrder(Node* root)//层次遍历
{
queue<Node*> q;
if (root == NULL)
{
return;
}
q.push(root);//根节点入队
while (!q.empty())//当队列不为空
{
if (q.front()->_left)
{
q.push(q.front()->_left);
}
if (q.front()->_right)
{
q.push(q.front()->_right);
}
cout << q.front()->_data << " ";
q.pop();
}
cout << endl;
}
private:
Node* _root;//根节点
};
void Test()
{
int a[10] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 };
BinaryTree<int> b(a, 10, '#');
b.PrevOrder();
b.InOrder();
b.PostOrder();
b.LevelOrder();
cout << "size:" << b.Size() << endl;
cout << "depth:" << b.Depth() << endl;
cout << "leafSize:" << b.LeafSize() << endl;
}
int main()
{
Test();
getchar();
return 0;
}