C/C++实现树操作的实例代码

2023-08-01 16:19:06 308

预处理命令

#include
#include
#defineTRUE1
#defineFALSE0
typedefintelemtype;
typedefstructtNode*tree;
typedefstructtNode{
elemtypeelem;
treeleft;
treeright;
}tNode;

计算树的节点个数

//明确函数的功能：返回传入树的节点个数
//定好尾头：尾：当传入的节点尾NULL时头：1+count(t->left)+count(t->right)
intcount(treet)
{
if(t==NULL)return0;
return1+count(t->left)+count(t->right);
}

求树中节点数据为num的节点个数

//明确函数功能：返回节点数据为num的节点个数
//定好尾头：尾：NULL头：1+func(左)+func（右）//或者func(左)+func（右）
intcount_num(treet,elemtypenum)
{
if(t==NULL)return0;
else
{
if(t->elem==num)
return1+count_num(t->left,num)+count_num(t->right,num);
else
returncount_num(t->left,num)+count_num(t->right,num);
}
}

求树中节点数据的总和

//明确函数功能：返回总和
//定好尾头：尾：NULL头：root->elem+func(左)+func（右）
intadd(treet)
{
if(t==NULL)
return0;
else
returnt->elem+add(t->left)+add(t->right);
}

判断树中有无数据为num的节点

//两种方式：一种是可以达成目的就结束，一种是需要遍历完全才结束
//明确函数功能：判断其中有没有值为num的节点返回1或0
//定好尾头：尾：值为num，头：
intinTree_1(treet,elemtypenum)
{
if(t->elem==num)
returnTRUE;
else
{
if(t->left!=NULL)
intree(t->left,num);//使用递归将其递到子节点
if(t->right!=NULL)
intree(t->right,num);
}
returnFALSE;
}
//确定函数功能：根据num的有无，返回0/非0
//定好尾头：尾：NULL头：有:return1+func(左)+func(右)无：func(左)+func(右)
intinTree_2(treet,elemtypenum)
{
if(t==NULL)return0;
intres;
if(t->elem==num)
res=1+intree(t->left,num)+intree(t->right,num);
if(t->elem==num)
res=intree(t->left,num)+intree(t->right,num);
returnres;
}

计算值为num的个数

intcount_elem(treet,elemtypeval,int*num)
{
intval_l,val_r;
if(t->left==NULL)
returnt->elem;
if(t->right==NULL)
returnt->elem;
else
{
val_l=count_elem(t->left,val,num);
if(val==val_l)
(*num)++;
val_r=count_elem(t->right,val,num);
if(val==val_r)
(*num)++;
returnt->elem;
}
return*num;
}

打印trunk

//明确函数功能：打印trunk
//定好尾头尾：NULL头：第一步是判断本节点是否是树干然后打印，再func（左）去打印左边的树干func（右）去打印右边的树干
voidprint_trunk(treet)
{
if(t==NULL)return;
if(t->right!=NULL||t->left!=NULL)
printf("%d",t->elem);
print_trunk(t->right);
print_trunk(t->left);
}

判断两棵树是否一样

intsame(treet1,treet2)
{
if(count(t1)==count(t2))
{
if(t1->elem!=t2->elem)
returnFALSE;
if(t1->left!=NULL&&t2->left!=NULL)
same(t1->left,t2->left);
if(t1->right!=NULL&&t2->right!=NULL)
same(t1->right,t2->right);
returnTRUE;
}
elsereturnFALSE;
}

求树的高度

#definemax(x,y)(x>y)?x:y

intheight(treet)
{
if(t==NULL)return-1;
return1+max(height(t->right),height(t->left));
}

打印树中某值的层数

//明确函数功能：寻找放入的数的层数并打印
//确定尾：//找到特定值的节点找到NULL头：若是则打印，若不是则去左右子树寻找layer++，当孩子寻找完都没有时layer--
boolflag=false;//flag标记可以用于提前结束递归
voidgetTreeLayer(Node*root,intnum,int&layer)
{
if(root==NULL)return;
if(flag==true)return;
if(root->data==num){
cout<<"num值"<lChild,num);
getTreeLayer(root->rChild,num);
layer--;
}

求节点的路径

vectorpath;
boolflag=false;//flag标记可以用于提前结束递归
voidgetTreeLayer(Node*root,intnum,int&layer)
{
if(root==NULL)return;
if(flag==true)return;
if(root->data==num){
for(intx:path)
cout<lChild,num);
getTreeLayer(root->rChild,num);
path.pop_back();
}

总结

以上所述是小编给大家介绍的C/C++实现树操作的实例代码，希望对大家有所帮助！

声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

C/C++实现树操作的实例代码

热门推荐

随机推荐