#include
#include
using namespace std;
#include
#include
template
struct BinaryTreeNode
{
BinaryTreeNode* _left;
BinaryTreeNode* _right;
T _data;
BinaryTreeNode(const T& x)
:_left(NULL)
,_right(NULL)
,_data(x)
{}
};
template
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)
{
_root = _CopyTree(t._root);
}
//赋值运算符重载的传统写法
/*BinaryTree& operator=(const BinaryTree& t)
{
if (this != &t)
{
_DestroyTree(_root);
_root = _CopyTree(t._root);
}
return *this;
}*/
//赋值运算符重载的现代写法
BinaryTree& operator=(BinaryTree t)
{
swap(_root, t._root);
return *this;
}
//递归前序遍历
void PreOrderTraverse()
{
_PreOrderTraverse(_root);
cout<*> q;
q.push(_root);
while (!q.empty())
{
BinaryTreeNode* front = q.front();
q.pop();
cout<_left)
{
q.push(front->_left);
}
if (front->_right)
{
q.push(front->_right);
}
}
}
//非递归前序遍历
void PreOrderTraverse_NonR()
{
if (NULL == _root)
{
return;
}
stack*> s;
s.push(_root);
while (!s.empty())//当栈为空时遍历完成
{
//先访问根节点
BinaryTreeNode* top = s.top();
s.pop();
cout<_data<<" ";
//右节点存在时先入栈，后出栈
if (top->_right)
{
s.push(top->_right);
}
//左结点存在时后入栈，先出栈
if (top->_left)
{
s.push(top->_left);
}
}
cout<*> s;
BinaryTreeNode* cur = _root;
while (cur || !s.empty())
{
//左结点全部入栈
while (cur)
{
s.push(cur);
cur = cur->_left;
}
if (!s.empty())
{
BinaryTreeNode* top = s.top();
cout<_data<<" ";
s.pop();
cur = top->_right;//将栈顶结点的右节点看作子树的根节点
}
}
cout<*> s;
BinaryTreeNode* cur = _root;
BinaryTreeNode* pre = NULL;
while (cur || !s.empty())//当前结点为空和栈为空同时满足时遍历完成
{
//左结点全部入栈
while (cur)
{
s.push(cur);
cur = cur->_left;
}
BinaryTreeNode* top = s.top();
if (NULL == top->_right || pre == top->_right)//若当前结点的右结点为空或者右节点已经访问过，可以访问该结点
{
cout<_data<<" ";
pre = top;
s.pop();
}
else//该结点的右节点不为空且未被访问
{
cur = top->_right;//将该结点的右节点看作子树的根节点
}
}
cout<* _CreateTree(const T* a, size_t size, size_t& index, const T& invalid)
{
BinaryTreeNode* root = NULL;
if (index < size && a[index] != invalid)
{
root = new BinaryTreeNode(a[index]);
root->_left = _CreateTree(a, size, ++index, invalid);
root->_right = _CreateTree(a, size, ++index, invalid);
}
return root;
}
void _DestroyTree(BinaryTreeNode* 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* _CopyTree(BinaryTreeNode* root)
{
if (NULL == root)
{
return NULL;
}
BinaryTreeNode* newRoot = new BinaryTreeNode(root->_data);
newRoot->_left = _CopyTree(root->_left);
newRoot->_right = _CopyTree(root->_right);
return newRoot;
}
void _PreOrderTraverse(BinaryTreeNode* root)
{
if (NULL == root)
{
return;
}
cout<_data<<" ";
_PreOrderTraverse(root->_left);
_PreOrderTraverse(root->_right);
}
void _InOrderTraverse(BinaryTreeNode* root)
{
if (NULL == root)
{
return;
}
_InOrderTraverse(root->_left);
cout<_data<<" ";
_InOrderTraverse(root->_right);
}
void _PostOrderTraverse(BinaryTreeNode* root)
{
if (NULL == root)
{
return;
}
_PostOrderTraverse(root->_left);
_PostOrderTraverse(root->_right);
cout<_data<<" ";
}
//_Size方法1：
/*size_t _Size(BinaryTreeNode* root)
{
if (NULL == root)
{
return;
}
return _Size(root->left) + _Size(root->_right) + 1;
}*/
//_Size方法2：（存在线程安全问题）
/*size_t _Size(BinaryTreeNode* 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* root, size_t& size)
{
if (NULL == root)
{
return;
}
else
{
++size;
}
_Size(root->_left, size);
_Size(root->_right, size);
}
size_t _Depth(BinaryTreeNode* 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* 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* 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* _root;
};
void BinaryTreeTest()
{
int a[] = {1, 2, 3, '#', '#', 4, '#', '#', 5, 6};
BinaryTree 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:"< t2(t);
cout<<"t2:";
t2.PreOrderTraverse();
BinaryTree t3;
t3 = t2;
cout<<"t3:";
t3.PreOrderTraverse();
}
int main()
{
BinaryTreeTest();
return 0;
}
生成的二叉树如下图：
为天坛街道等地区用户提供了全套网页设计制作服务，及天坛街道网站建设行业解决方案。主营业务为成都网站建设、做网站、天坛街道网站设计，以传统方式定制建设网站，并提供域名空间备案等一条龙服务，秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求，就会得到认可，从而选择与我们长期合作。这样，我们也可以走得更远！
测试结果：
本文题目：C++实现二叉树
浏览路径：
http://bjjierui.cn/article/ihojpo.html
