C++实现二叉树基本操作详解
树是一种重要的非线性数据结构，二叉树是树型结构的一种重要类型。本学年论文介绍了二叉树的定义，二叉树的存储结构，二叉树的相关术语，以此引入二叉树这一概念，为展开二叉树的基本操作做好理论铺垫。二叉树的基本操作主要包含以下几个模块：二叉树的遍历方法，计算二叉树的结点个数，计算二叉树的叶子结点个数，二叉树深度的求解等内容。
前序遍历（递归&非递归）
- 访问根节点
- 前序访问左子树
- 前序访问右子树
//前序非递归
voidPrevOrder()
{
stacks;
Node*cur=_root;
while(cur||!s.empty())
{
while(cur)
{
cout<_data<<"";
s.push(cur);
cur=cur->_left;
}
//此时当前节点的左子树已遍历完毕
Node*tmp=s.top();
s.pop();
cur=tmp->_right;
}
cout<_data<<"";
_PrevOrder(root->_left);
_PrevOrder(root->_right);
}
中序遍历（递归&非递归）
- 中序访问左子树
- 访问根节点
- 中序访问右子树
//中序非递归
voidInOrder()
{
stacks;
Node*cur=_root;
while(cur||!s.empty())
{
while(cur)
{
s.push(cur);
cur=cur->_left;
}
//此时当前节点的左子树已遍历完毕
Node*tmp=s.top();
cout<_data<<"";
s.pop();
cur=tmp->_right;
}
cout<_left);
cout<_data<<"";
_InOrder(root->_right);
}
后序遍历（递归&非递归）
//后序非递归
//后序遍历可能会出现死循环，所以要记录下前一个访问的节点
voidPostOrder()
{
stacks;
Node*cur=_root;
Node*prev=NULL;
while(cur||!s.empty())
{
while(cur)
{
s.push(cur);
cur=cur->_left;
}
Node*tmp=s.top();
if(tmp->_right&&tmp->_right!=prev)
{
cur=tmp->_right;
}
else
{
cout<_data<<"";
prev=tmp;
s.pop();
}
}
cout<_left);
_PostOrder(root->_right);
cout<_data<<"";
}
层序遍历
从根节点开始，依次访问每层结点。
利用队列先进先出的特性，把每层结点从左至右依次放入队列。
voidLevelOrder()//利用队列！！！
{
queueq;
Node*front=NULL;
//1.push根节点
if(_root)
{
q.push(_root);
}
//2.遍历当前节点，push当前节点的左右孩子，pop当前节点
//3.遍历当前节点的左孩子，再遍历右孩子，循环直至队列为空
while(!q.empty())
{
front=q.front();
cout<_data<<"";
if(front->_left)
q.push(front->_left);
if(front->_right)
q.push(front->_right);
q.pop();
}
cout<
求二叉树的高度
size_tDepth()
{
return_Depth(_root);
}
size_t_Depth(Node*root)
{
if(root==NULL)
return0;
elseif(root->_left==NULL&&root->_right==NULL)
return1;
else
{
size_tleftDepth=_Depth(root->_left)+1;
size_trightDepth=_Depth(root->_right)+1;
returnleftDepth>rightDepth?leftDepth:rightDepth;
}
}
求叶子节点的个数
size_tLeafSize()
{
return_LeafSize(_root);
}
size_t_LeafSize(Node*root)
{
if(root==NULL)
return0;
elseif(root->_left==NULL&&root->_right==NULL)
return1;
else
return_LeafSize(root->_left)+_LeafSize(root->_right);
}
求二叉树第k层的节点个数
size_tGetKLevel(intk)
{
return_GetKLevel(_root,k);
}
size_t_GetKLevel(Node*root,intk)
{
if(root==NULL)
return0;
elseif(k==1)
return1;
else
return_GetKLevel(root->_left,k-1)+_GetKLevel(root->_right,k-1);
}
完整代码如下：
template
structBinaryTreeNode
{
T_data;
BinaryTreeNode*_left;
BinaryTreeNode*_right;
BinaryTreeNode(constT&d)
:_data(d)
,_left(NULL)
,_right(NULL)
{}
};
template
classBinaryTree
{
public:
typedefBinaryTreeNodeNode;
BinaryTree()
:_root(NULL)
{}
BinaryTree(T*arr,size_tn,constT&invalid)
{
size_tindex=0;
_root=_CreateBinaryTree(arr,n,invalid,index);
}
BinaryTree(constBinaryTree&t)
:_root(NULL)
{
_root=_CopyTree(t._root);
}
BinaryTree&operator=(constBinaryTree&t)
{
if(this!=t)
{
Node*tmp=newNode(t._root);
if(tmp!=NULL)
{
delete_root;
_root=tmp;
}
}
return*this;
}
~BinaryTree()
{
_DestroyTree(_root);
cout<s;
Node*cur=_root;
while(cur||!s.empty())
{
while(cur)
{
cout<_data<<"";
s.push(cur);
cur=cur->_left;
}
//此时当前节点的左子树已遍历完毕
Node*tmp=s.top();
s.pop();
cur=tmp->_right;
}
cout<s;
Node*cur=_root;
while(cur||!s.empty())
{
while(cur)
{
s.push(cur);
cur=cur->_left;
}
//此时当前节点的左子树已遍历完毕
Node*tmp=s.top();
cout<_data<<"";
s.pop();
cur=tmp->_right;
}
cout<s;
Node*cur=_root;
Node*prev=NULL;
while(cur||!s.empty())
{
while(cur)
{
s.push(cur);
cur=cur->_left;
}
Node*tmp=s.top();
if(tmp->_right&&tmp->_right!=prev)
{
cur=tmp->_right;
}
else
{
cout<_data<<"";
prev=tmp;
s.pop();
}
}
cout<q;
Node*front=NULL;
//1.push根节点
if(_root)
{
q.push(_root);
}
//2.遍历当前节点，push当前节点的左右孩子，pop当前节点
//3.遍历当前节点的左孩子，再遍历右孩子，循环直至队列为空
while(!q.empty())
{
front=q.front();
cout<_data<<"";
if(front->_left)
q.push(front->_left);
if(front->_right)
q.push(front->_right);
q.pop();
}
cout<_left=_CreateBinaryTree(arr,n,invalid,index);
index++;
root->_right=_CreateBinaryTree(arr,n,invalid,index);
}
returnroot;
}
Node*_CopyTree(Node*root)
{
Node*newRoot=NULL;
if(root)
{
newRoot=newNode(root->_data);
newRoot->_left=_CopyTree(root->_left);
newRoot->_right=_CopyTree(root->_right);
}
returnnewRoot;
}
void_DestroyTree(Node*root)
{
if(root)
{
_Destroy(root->_left);
_Destroy(root->_right);
deleteroot;
}
}
void_PrevOrder(Node*root)
{
if(root==NULL)//必须有递归出口！！！
return;
cout<_data<<"";
_PrevOrder(root->_left);
_PrevOrder(root->_right);
}
void_InOrder(Node*root)
{
if(root==NULL)
return;
_InOrder(root->_left);
cout<_data<<"";
_InOrder(root->_right);
}
void_PostOrder(Node*root)
{
if(root==NULL)
return;
_PostOrder(root->_left);
_PostOrder(root->_right);
cout<_data<<"";
}
size_t_Size(Node*root)
{
if(root==NULL)
return0;
else
return_Size(root->_left)+_Size(root->_right)+1;
}
size_t_LeafSize(Node*root)
{
if(root==NULL)
return0;
elseif(root->_left==NULL&&root->_right==NULL)
return1;
else
return_LeafSize(root->_left)+_LeafSize(root->_right);
}
size_t_GetKLevel(Node*root,intk)
{
if(root==NULL)
return0;
elseif(k==1)
return1;
else
return_GetKLevel(root->_left,k-1)+_GetKLevel(root->_right,k-1);
}
size_t_Depth(Node*root)
{
if(root==NULL)
return0;
elseif(root->_left==NULL&&root->_right==NULL)
return1;
else
{
size_tleftDepth=_Depth(root->_left)+1;
size_trightDepth=_Depth(root->_right)+1;
returnleftDepth>rightDepth?leftDepth:rightDepth;
}
}
Node*_Find(Node*root,constT&d)
{
if(root==NULL)
returnNULL;
elseif(root->_data==d)
returnroot;
elseif(Node*ret=_Find(root->_left,d))
returnret;
else
_Find(root->_right,d);
}
protected:
Node*_root;
};
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。