数据结构-二叉树的常见操作(基于递归实现)
程序员文章站
2022-03-13 10:34:11
...
二叉树的拷贝
求二叉树的节点个数
求二叉树叶子节点个数
求第K层节点的个数
求二叉树的高度
在二叉树中查找节点:给定值,返回地址
已知孩子节点,求父节点
求出当前节点的左子树,右子树
-
二叉树 的拷贝分为深拷贝和浅拷贝
深拷贝:重新申请物理内存,将原有二叉树的复制过去,
优点:修改其中一个二叉树,不会影响其他和此二叉树相同的二叉树。
缺点:占用内存大,耗时浅拷贝:不会重新申请物理内存,在一块物理内存上完成复制
优点:节省空间,时间。
缺点:牵一发而动全身。只要修改其中一个一个节点,其他的元素都会受到影响
应用:父进程创建子进程时,地址空间共享,而数据写实拷贝。这里的写实拷贝就应用了深浅拷贝的原理。
本文中实现深拷贝
//二叉树的深拷贝
BinTreeNode* BinTreeClone(BinTreeNode* root)
{
//空树
if( root==NULL)
{
return NULL;
}
//拷贝根节点
BinTreeNode* newnode=BinTreeNodeCreate(root->data);
newnode->data=root->data;
//递归拷贝左子树
newnode->pleft=BinTreeClone(root->pleft);
//递归拷贝右子树
newnode->pright=BinTreeClone(root->pright);
return newnode;
}
求节点个数时,包括根节点
//求二叉树的节点个数(递归版本)
size_t BinTreeSizeR( BinTreeNode* root)
{
if( root==NULL)
{
return 0;
}
return 1+BinTreeSizeR(root->pleft)+BinTreeSize(root->pright);
}
void _BinTreeSize(BinTreeNode* root,size_t * size)
{
if(root==NULL)
{
return;
}
++(*size);
_BinTreeSize(root->pleft,size);
_BinTreeSize(root->pright,size);
}
//求二叉树节点个数(非递归:通过参数带值方法)
size_t BinTreeSize( BinTreeNode* root)
{
size_t size=0;
if( root==NULL)
{
return 0;
}
_BinTreeSize(root,&size);
return size;
}
叶子节点:度为0的节点,即终端没有孩子节点的节点个数
//求二叉树叶子节点的个数
size_t BinTreeLeafSize(BinTreeNode* root)
{
if(root==NULL)
{
return 0;
}
if( root->pleft==NULL&&root->pright==NULL)
{
return 1;
}
return BinTreeLeafSize(root->pleft)+BinTreeLeafSize(root->pright);
}
求第K层节点个数,我们无法直接获得第K层节点个数,但我们可以将问题化整为零,先求第K-1层节点,求K-1层节点时先求第(k-1)-1层节点,后面以此类推,知道第1层节点,即根节点,然后将将第K层左右子树节点相加,即可
//求二叉树中第K层节点的个数
size_t BinTreeK_leveSize(BinTreeNode* root,int k)
{
if(root==NULL||k<1)
{
return 0;
}
if( k==1)
{
return 1;
}
return BinTreeK_leveSize(root->pleft,k-1)+BinTreeK_leveSize(root->pright,k-1);
}
//求二叉树的高度
//使用递归
// 如果该树只有一个结点,它的深度为1.如果根节点只有左子树没有右子树,
// 那么树的深度为左子树的深度加1;同样,如果只有右子树没有左子树,
// 那么树的深度为右子树的深度加1。如果既有左子树也有右子树,
// 那该树的深度就是左子树和右子树的最大值加1.
C语言版本
size_t BinTreeHight(BinTreeNode* root)
{
//空树
if( root==NULL)
{
return 0;
}
//只有一个节点,即左右子树为空
if(root->pleft==NULL&&root->pright==NULL)
{
return 1;
}
//递归遍历左子树节点个数
size_t l_height=BinTreeHight(root->pleft);
//递归遍历右子树节点个数
size_t r_height=BinTreeHight(root->pright);
//比较根节点左子树节点个数和根节点加上右子树节点个数,谁大取谁
return (1+l_height)>(1+r_hight)?(1+l_height):(1+r_height);
}
C++版本:
class Solution {
public:
int TreeDepth(TreeNode* pRoot)
{
if(pRoot==NULL)
{
return 0;
}
return max(TreeDepth(pRoot->left),TreeDepth(pRoot->right))+1;
}
};
//在二叉树中查找节点:给定值,返回指针
BinTreeNode* BinTreeFind(BinTreeNode* root,DataType to_find)
{
//空树
if( root==NULL)
{
return NULL;
}
//根节点 就是要找的值
if( root->data==to_find)
{
return root;
}
else
{
//递归遍历左子树,查找给定值
BinTreeNode* LResult=BinTreeFind(root,to_find);
//递归遍历左子树,查找给定值
BinTreeNode* RResult=BinTreeFind(root,to_find);
return LResult!=NULL?LResult:RResult;
}
}
//给定孩子节点,求父节点
BinTreeNode* BinTreeParent(BinTreeNode* root,BinTreeNode* child)
{
//空树或者孩子节点为NULL
if(root==NULL||child==NULL)
{
return NULL;
}
//如果根节点就是目标给定孩子节点的父节点
else if(root->pleft==child||root->pright==child)
{
return root;
}
else
{
//递归遍历左子树,查找给定孩子节点的父节点
BinTreeNode* LResult= BinTreeParent( root->pleft,child);
//递归遍历左子树,查找给定孩子节点的父节点
BinTreeNode* RResult= BinTreeParent( root-pright,child);
return (LResult!=NULL)?LResult:RResult;
}
}
//求当前节点的左子树
BinTreeNode* BinTreeFindLchild(BinTreeNode* root)
{
if( root==NULL)
{
return NULL;
}
return root->pleft;
}
//求当前节点的右子树
BinTreeNode* BinTreeFindRchild(BinTreeNode* root)
{
if( root==NULL)
{
return NULL;
}
return root->pright;
}
上一篇: WEB 2.0 代码最全备忘录
下一篇: 输出(a,b)之间的质数