统计二叉树各度数的结点的个数高度宽度结点.docx

文档介绍：该【统计二叉树各度数的结点的个数高度宽度结点 】是由【niupai11】上传分享，文档一共【7】页，该文档可以免费在线阅读，需要了解更多关于【统计二叉树各度数的结点的个数高度宽度结点 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。统计二叉树各度数的结点的个数高度宽度结点最
大元素的值交换结点的左孩子和右孩子删除所有
叶子节点
/*设一棵二叉树以二叉链表表示,试编写有关二叉树的递归算法:
1、统计二叉树中度为1的结点
2、统计二叉树中度为2的结点
3、统计二叉树中度为0的结点
4、统计二叉树的高度
5、统计二叉树的宽度,即在二叉树各层上具有节点数最多的那一层上结点总数
6、计算二叉树中个结点最大元素的值
7、交换每个结点的左孩子结点和右孩子结点
8从二叉树中删除所有叶子节点*/
#include<iostream>
#include<queue>
#include<stack>
#include<string>
usingnamespacestd;
template<classT>
classbtrnode
{
public:
Telement;
//结点的数据域
btrnode<T>*lchild;
//结点的左孩子结点
btrnode<T>*rchild;
//结点的右孩子节点
btrnode(){lchild
=
NULL;rchild=NULL;
}
//默认构造函数
btrnode(Tele)
//给定数值域的值得构造函数
{element=ele;lchild=NULL;rchild=NULL;
}
};
//二叉树的抽象数据类型template<classT>
classbtr
{
private:
btrnode<T>*root;
intcount;
public:
btr(){count=0;} //默认构造函数
btrnode<T>*pib(stringpreod,stringinod);//前序中序构造二叉树的算法intnum0(btrnode<T>*root); //求度为0的结点的个数
intnum1(btrnode<T>*root); //求度为1的结点的个数
intnum2(btrnode<T>*root); //求度为2的结点的个数
intbtrhigh(btrnode<T>*root); //求树的的高度
intbtrwidth(btrnode<T>*root); //求树的宽度
btrnode<T>*max(btrnode<T>*root);//二叉树中个结点最大元素的值voidchange(btrnode<T>*root); //交换每个结点的左右孩子
voiddel(btrnode<T>*&root); //删除所有叶子节点
voidpreorder(btrnode<T>*root);
voidvisit(btrnode<T>*cur);
};
//先序、中序构造二叉树递归算法
template<classT>
btrnode<T>*btr<T>::pib(stringpreod,stringinod)//是二叉树结点个数
{
stringp,q,m,n;
inti=0;
btrnode<char>*tmp=newbtrnode<char>;//????????为什么直接构造无法赋值成功?????????
tmp->element=preod[0];
for(;inod[i]!=preod[0];i++);
if(preod==""||inod=="")returnNULL;
p=(1,i);
q=(0,i);
m=(i+1);
n=(i+1);tmp->lchild=pib(p,q);tmp->rchild=pib(m,n);returntmp;
}
//求度为0的结点的个数template<classT>
intbtr<T>::num0(btrnode<T>*root)
{
intn,m,sum=0;
btrnode<T>*pointer=root;
if(pointer)
{
if(pointer->lchild==NULL&&pointer->rchild==NULL)sum++;
n=num0(pointer->lchild);
sum+=n;
m=num0(pointer->rchild);
sum+=m;
}
returnsum;
}
//求度为1的结点的个数template<classT>
intbtr<T>::num1(btrnode<T>*root)
{
intn,m,sum=0;
btrnode<T>*pointer=root;
if(pointer)
NULL)||
{
if((pointer->lchild==NULL&&pointer->rchild(pointer->rchild==NULL&&pointer->lchild!=NULL))sum++;
n=num1(pointer->lchild);
sum+=n;
m=num1(pointer->rchild);
sum+=m;
}
returnsum;
}
//求度为2的结点的个数template<classT>
intbtr<T>::num2(btrnode<T>*root)
{
intn,m,sum=0;
btrnode<T>*pointer=root;
if(pointer)
{
if(pointer->lchild!=NULL&&pointer->rchild!=NULL)sum++;
n=num2(pointer->lchild);
sum+=n;
m=num2(pointer->rchild);
sum+=m;
}
returnsum;
}
//求树的的高度
template<classT>
intbtr<T>::btrhigh(btrnode<T>*root)
{
btrnode<T>*pointer=root;
intm,n,max;
if(pointer==NULL)
return0;
m=btrhigh(pointer->lchild);
n=btrhigh(pointer->rchild);
max=1+(m>n?m:n);
returnmax;
}
//求树的宽度
template<classT>
intbtr<T>::btrwidth(btrnode<T>*root)
{
intcur,max=0;
btrnode<T>*pointer=root;
queue<btrnode<T>*>nqueue1,nqueue2;
if(pointer==NULL)
return0;
(pointer);
while(!())
{
cur=0;
while(!())
{
cur++;
pointer=();
();
if(pointer->lchild!=NULL)(pointer->lchild);
if(pointer->rchild!=NULL)
(pointer->rchild);
}
max=(max>cur?max:cur);
while(!())
{
(());
();
}
}
returnmax;
}
/*//求树的宽度
template<classT>
intbtr<T>::btrwidth(btrnode<T>*root)
{
intn,m,sum=0;
btrnode<T>*pointer=root;
if(pointer)
{
sum=1;
n=btrwidth(pointer->lchild);
m=btrwidth(pointer->rchild);
}
returnsum;
}*/
//二叉树中个结点最大元素的值
template<classT>
btrnode<T>*btr<T>::max(btrnode<T>*root){
btrnode<T>*pointer=root;btrnode<T>*tmp,*tmpl,*tmpr;
if(pointer==NULL)
returnNULL;
tmpl=max(pointer->lchild);
tmpr=max(pointer->rchild);
if(tmpl==NULL&&tmpr==NULL)
tmp=pointer;
else
{
if(tmpl!=NULL&&tmpr==NULL)
tmp=tmpl;
elseif(tmpl==NULL&&tmpr!=NULL)
tmp=tmpr;
else
tmp=(tmpl->element>tmpr->element?tmpl:tmpr);tmp=(tmp->element>pointer->element?tmp:pointer);}
returntmp;
}
//删除所有叶子节点template<classT>
voidbtr<T>::del(btrnode<T>*&root){
if(root==NULL)
return;
if(root->lchild==NULL&&root->rchild==NULL){deleteroot;
root=NULL;
return;
}
del(root->lchild);del(root->rchild);
}//交换每个结点的左右孩子template<classT>
voidbtr<T>::change(btrnode<T>*root){
btrnode<T>*tmp;
btrnode<T>*pointer=root;
if(pointer)
{
tmp=pointer->lchild;
pointer->lchild=pointer->rchild;pointer->rchild=tmp;
}
elsereturn;
change(pointer->l
child);
change(pointer->rchild);
}
//前序遍历
template<classT>
voidbtr<T>::preorder(btrnode<T>*root)
{
if(root!=NULL)
{
visit(root); //处理根结点
preorder(root->lchild);
preorder(root->rchild);
}
}
template<classT>
voidbtr<T>::visit(btrnode<T>*cur)
{
cout<<cur->element<<"";
}
intmain()
{
stringa,b;
btr<char>c;
btrnode<char>*root,*tmp;
intn;
cout&It;&It;"分别输入先序序列、和中序序列:";
cin>>a;
cin>>b;
root=(a,b);
n=(root);
cout&It;<"度为0的结点个数:"&It;&It;n&It;&It;endl;
n=(root);
cout&It;<"度为1的结点个数:"&It;&It;n&It;&It;endl;
n=(root);
cout&It;<"度为2的结点个数:"&It;&It;n&It;&It;endl;
n=(root);
cout&It;&It;"树的高度为:"&It;&It;n&It;&It;endl;
n=(root);
cout&It;&It;"树的宽度为:"&It;&It;n&It;&It;endl;
tmp=(root);
cout&It;&It;"最大元素值为"&It;&It;tmp->element&It;&It;endl;(root);
(root);
cout&It;&It;endI;
(root);
(root);
return0;
}