#include <assert.h>
#include <iostream>
using namespace std;
#include <stack>
#include <queue>
template<class T>
struct BinaryTreeNode
{
BinaryTreeNode<T>* _left;
BinaryTreeNode<T>* _right;
T _data;
BinaryTreeNode(const T& x)
:_left(NULL)
,_right(NULL)
,_data(x)
{}
};
template<class T>
class BinaryTree
{
public:
BinaryTree()
:_root(NULL)
{}
BinaryTree(const T* a, size_t size, const T& invalid)
{
size_t index = 0;
_root = _CreateTree(a, size, index, invalid);
}
~BinaryTree()
{
_DestroyTree(_root);
_root = NULL;
}
BinaryTree(const BinaryTree<T>& t)
{
_root = _CopyTree(t._root);
}
//赋值运算符重载的传统写法
/*BinaryTree<T>& operator=(const BinaryTree& t)
{
if (this != &t)
{
_DestroyTree(_root);
_root = _CopyTree(t._root);
}
return *this;
}*/
//赋值运算符重载的现代写法
BinaryTree<T>& operator=(BinaryTree<T> t)
{
swap(_root, t._root);
return *this;
}
//递归前序遍历
void PreOrderTraverse()
{
_PreOrderTraverse(_root);
cout<<endl;
}
//递归中序遍历
void InOrderTraverse()
{
_InOrderTraverse(_root);
cout<<endl;
}
//递归后序遍历
void PostOrderTraverse()
{
_PostOrderTraverse(_root);
cout<<endl;
}
//非递归层序遍历
void LevelOrderTraverse()
{
if (NULL == _root)
{
return;
}
queue<BinaryTreeNode<T>*> q;
q.push(_root);
while (!q.empty())
{
BinaryTreeNode<T>* front = q.front();
q.pop();
cout<<front._data<<" ";
if (front->_left)
{
q.push(front->_left);
}
if (front->_right)
{
q.push(front->_right);
}
}
}
//非递归前序遍历
void PreOrderTraverse_NonR()
{
if (NULL == _root)
{
return;
}
stack<BinaryTreeNode<T>*> s;
s.push(_root);
while (!s.empty())//当栈为空时遍历完成
{
//先访问根节点
BinaryTreeNode<T>* top = s.top();
s.pop();
cout<<top->_data<<" ";
//右节点存在时先入栈,后出栈
if (top->_right)
{
s.push(top->_right);
}
//左结点存在时后入栈,先出栈
if (top->_left)
{
s.push(top->_left);
}
}
cout<<endl;
}
//非递归中序遍历
void InOrderTraverse_NonR()
{
if (NULL == _root)
{
return;
}
stack<BinaryTreeNode<T>*> s;
BinaryTreeNode<T>* cur = _root;
while (cur || !s.empty())
{
//左结点全部入栈
while (cur)
{
s.push(cur);
cur = cur->_left;
}
if (!s.empty())
{
BinaryTreeNode<T>* top = s.top();
cout<<top->_data<<" ";
s.pop();
cur = top->_right;//将栈顶结点的右节点看作子树的根节点
}
}
cout<<endl;
}
//非递归后序遍历
void PostOrderTraverse_NonR()
{
if (NULL == _root)
{
return;
}
stack<BinaryTreeNode<T>*> s;
BinaryTreeNode<T>* cur = _root;
BinaryTreeNode<T>* pre = NULL;
while (cur || !s.empty())//当前结点为空和栈为空同时满足时遍历完成
{
//左结点全部入栈
while (cur)
{
s.push(cur);
cur = cur->_left;
}
BinaryTreeNode<T>* top = s.top();
if (NULL == top->_right || pre == top->_right)//若当前结点的右结点为空或者右节点已经访问过,可以访问该结点
{
cout<<top->_data<<" ";
pre = top;
s.pop();
}
else//该结点的右节点不为空且未被访问
{
cur = top->_right;//将该结点的右节点看作子树的根节点
}
}
cout<<endl;
}
//求结点数
size_t Size()
{
size_t size = 0;
_Size(_root, size);
return size;
}
//求深度
size_t Depth()
{
return _Depth(_root);
}
//求叶子结点数
size_t LeafSize()
{
size_t leafSize = 0;
_LeafSize(_root, leafSize);
return leafSize;
}
//求第K层结点数
size_t GetKLevel(const size_t& k)
{
return _GetKLevel(_root, k);
}
protected:
BinaryTreeNode<T>* _CreateTree(const T* a, size_t size, size_t& index, const T& invalid)
{
BinaryTreeNode<T>* root = NULL;
if (index < size && a[index] != invalid)
{
root = new BinaryTreeNode<T>(a[index]);
root->_left = _CreateTree(a, size, ++index, invalid);
root->_right = _CreateTree(a, size, ++index, invalid);
}
return root;
}
void _DestroyTree(BinaryTreeNode<T>* root)
{
if (NULL == root)
{
return;
}
if (NULL == root->_left && NULL == root->_right)
{
delete root;
root = NULL;
return;
}
_DestroyTree(root->_left);
_DestroyTree(root->_right);
delete root;
}
BinaryTreeNode<T>* _CopyTree(BinaryTreeNode<T>* root)
{
if (NULL == root)
{
return NULL;
}
BinaryTreeNode<T>* newRoot = new BinaryTreeNode<T>(root->_data);
newRoot->_left = _CopyTree(root->_left);
newRoot->_right = _CopyTree(root->_right);
return newRoot;
}
void _PreOrderTraverse(BinaryTreeNode<T>* root)
{
if (NULL == root)
{
return;
}
cout<<root->_data<<" ";
_PreOrderTraverse(root->_left);
_PreOrderTraverse(root->_right);
}
void _InOrderTraverse(BinaryTreeNode<T>* root)
{
if (NULL == root)
{
return;
}
_InOrderTraverse(root->_left);
cout<<root->_data<<" ";
_InOrderTraverse(root->_right);
}
void _PostOrderTraverse(BinaryTreeNode<T>* root)
{
if (NULL == root)
{
return;
}
_PostOrderTraverse(root->_left);
_PostOrderTraverse(root->_right);
cout<<root->_data<<" ";
}
//_Size方法1:
/*size_t _Size(BinaryTreeNode<T>* root)
{
if (NULL == root)
{
return;
}
return _Size(root->left) + _Size(root->_right) + 1;
}*/
//_Size方法2:(存在线程安全问题)
/*size_t _Size(BinaryTreeNode<T>* root)
{
static size_t size = 0;
if (NULL == root)
{
return 0;
}
else
{
++size;
}
_Size(root->_left);
_Size(root->_right);
return size;
}*/
//_Size方法3:
void _Size(BinaryTreeNode<T>* root, size_t& size)
{
if (NULL == root)
{
return;
}
else
{
++size;
}
_Size(root->_left, size);
_Size(root->_right, size);
}
size_t _Depth(BinaryTreeNode<T>* root)
{
if (NULL == root)
{
return 0;
}
size_t leftDepth = _Depth(root->_left);
size_t rightDepth = _Depth(root->_right);
return leftDepth > rightDepth ? leftDepth+1 : rightDepth+1;
}
void _LeafSize(BinaryTreeNode<T>* root, size_t& leafSize)
{
if (NULL == root)
{
return;
}
if (NULL == root->_left && NULL == root->_right)
{
++leafSize;
return;
}
_LeafSize(root->_left, leafSize);
_LeafSize(root->_right, leafSize);
}
size_t _GetKLevel(BinaryTreeNode<T>* root, const size_t& k)
{
assert(k > 0);
if (NULL == root)
{
return 0;
}
if (k == 1)
{
return 1;
}
return _GetKLevel(root->_left, k-1) + _GetKLevel(root->_right, k-1);
}
protected:
BinaryTreeNode<T>* _root;
};
void BinaryTreeTest()
{
int a[] = {1, 2, 3, '#', '#', 4, '#', '#', 5, 6};
BinaryTree<int> t(a, sizeof(a)/sizeof(a[0]), '#');
cout<<"递归前序遍历:";
t.PreOrderTraverse();
cout<<"递归中序遍历:";
t.InOrderTraverse();
cout<<"递归后序遍历:";
t.PostOrderTraverse();
cout<<"非递归前序遍历:";
t.PreOrderTraverse_NonR();
cout<<"非递归中序遍历:";
t.InOrderTraverse_NonR();
cout<<"非递归后序遍历:";
t.PostOrderTraverse_NonR();
cout<<"Size:"<<t.Size()<<endl;
cout<<"Depth:"<<t.Depth()<<endl;
cout<<"LeafSize:"<<t.LeafSize()<<endl;
cout<<"Get3Level:"<<t.GetKLevel(3)<<endl;
BinaryTree<int> t2(t);
cout<<"t2:";
t2.PreOrderTraverse();
BinaryTree<int> t3;
t3 = t2;
cout<<"t3:";
t3.PreOrderTraverse();
}
int main()
{
BinaryTreeTest();
return 0;
}
生成的二叉树如下图:
测试结果:
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。