C++:一棵二叉树,叶子结点数为22，度为1的结点数为13，则该二叉树的结点总数为（ ）。

C++: 编写程序，创建一个二叉树。实现统计二叉树叶子结点的个数和二叉树的深度~

#include #include #include typedef int ElemType; //数据类型//定义二叉树结构，与单链表相似，多了一个右孩子结点typedef struct BiTNode{ElemType data; //数据域struct BiTNode*lChild, *rChlid; //左右子树域}BiTNode, *BiTree;//先序创建二叉树int CreateBiTree(BiTree *T){ElemType ch;ElemType temp;scanf("%d", &ch);temp = getchar();if (ch == -1)*T = NULL;else{*T = (BiTree)malloc(sizeof(BiTNode));if (!(*T))exit(-1);(*T)->data = ch;printf("输入%d的左子节点：", ch);CreateBiTree(&(*T)->lChild);printf("输入%d的右子节点：", ch);CreateBiTree(&(*T)->rChlid);}return 1;}//先序遍历二叉树void TraverseBiTree(BiTree T){if (T == NULL)return ;printf("%d ", T->data);TraverseBiTree(T->lChild);TraverseBiTree(T->rChlid);}//中序遍历二叉树void InOrderBiTree(BiTree T){if (T == NULL)return ;InOrderBiTree(T->lChild);printf("%d ", T->data);InOrderBiTree(T->rChlid);}//后序遍历二叉树void PostOrderBiTree(BiTree T){if (T == NULL)return ;PostOrderBiTree(T->lChild);PostOrderBiTree(T->rChlid);printf("%d ", T->data);}//二叉树的深度int TreeDeep(BiTree T){int deep = 0;if(T){int leftdeep = TreeDeep(T->lChild);int rightdeep = TreeDeep(T->rChlid);deep = leftdeep>=rightdeep?leftdeep+1:rightdeep+1;}return deep;}//求二叉树叶子结点个数int Leafcount(BiTree T,int &num){ if(T){if(T->lChild ==NULL &&T->rChlid==NULL)num++;Leafcount(T->lChild,num);Leafcount(T->rChlid,num);}return num;}//主函数int main(void){BiTree T;BiTree *p = (BiTree*)malloc(sizeof(BiTree));int deepth,num=0 ;printf("请输入第一个结点的值,-1表示没有叶结点:
");CreateBiTree(&T);printf("先序遍历二叉树:
");TraverseBiTree(T);printf("
");printf("中序遍历二叉树:
");InOrderBiTree(T);printf("
");printf("后序遍历二叉树:
");PostOrderBiTree(T);printf("
");deepth=TreeDeep(T);printf("树的深度为:%d",deepth);printf("
");Leafcount(T,num);printf("树的叶子结点个数为:%d",num);printf("
");return 0;}

同学，你们老师和我们老师留的作业是一模一样的阿，我有现成的做好了的程序，调试成功。这个程序的难点就在于这种很别扭的输入形式，所以我为它设计了一个结构体形式存放输入内容，再将它转化成了线性结构。

#include <iostream.h>
#include <stdlib.h>

struct inform /*建立输入信息结构体inform*/
{ char data;

int l;

int r;

int signl; /*作为标记的signl,signr*/

int signr;
};

struct leafnode /*建立叶子节点结构体*/
{
char leaf;

leafnode* lchild;

leafnode* rchild;

};

void print(inform* ps, int n);

void judge ( inform* ps );

leafnode* creatree(); /*声明二叉树的建立函数*/

void preorder (leafnode* T); /*声明先序遍历函数*/

void inorder (leafnode* T); /*声明中序遍历函数*/

void postorder (leafnode* T); /*声明后序遍历函数*/

char a[100];

int k=1;
int s=0;

inform *p;

void main()
{
/*-------------------------------按格式输入信息-----------------------------------*/

int n;

cout<<"请输入二叉树内容：第一行为节点总数n ，后面的n行是节点的具体形式："<<endl;

cout<<"n= ";

cin>>n;

p=(inform* )malloc( n*sizeof(inform) ); /*开辟的一个叶子结构体型的指针数组*/
inform *p1; p1=p;

for(int i=0; i<n; i++)

{
cin>>(p+i)->data>>(p+i)->l>>(p+i)->r;
if((p+i)->l != -1) (p+i)->signl=1; /*用signl signr 的0，1标示输入的信息中是否有左或右孩子*/
else (p+i)->signl= 0;
if((p+i)->r !=-1) (p+i)->signr=1;
else (p+i)->signr= 0;
}

/*--------------------------------------------------------------------------------------------*/
a[0]= p->data;

judge ( p1 ); /*用递归算法将输入数据信息转为线性字符串*/

cout<<endl<<"输出转换的线性字符串： "<<endl;

cout<<a<<endl<<endl;
/*------------------------------------------遍历-----------------------------------*/
leafnode* T;

T= creatree();

/*先续遍历二叉树*/
cout<<"先序遍历二叉树： "<<endl;
preorder( T );

cout<<endl<<"中序遍历二叉树： "<<endl;
inorder ( T );

cout<<endl<<"后序遍历二叉树： "<<endl;
postorder( T );
cout<<endl<<endl;


}

/*------------------------------------------函数定义-------------------------------*/

void judge( inform* ps ) /*用函数的递归来将输入的信息转化为线性的数组*/
{
inform* b;

if (ps->signl==0)
{
a[k]='@';
k++;
}
else
{
b = p+(ps->l);
a[k] = b->data;
k++;
judge(b);
}



if ((ps->signr) == 0)
{
a[k]='@';
k++;
}
else
{
b = p+(ps->r );
a[k] = b->data;
k++;
judge(b);
}


}

leafnode* creatree() /*建立二叉树函数*/
{
char ch;

leafnode *t;

ch= a[s];
s++;

if(ch=='@')
{
t=NULL;
}
else
{
t=(leafnode* )malloc(sizeof(leafnode));
t->leaf=ch;
t->lchild=creatree();
t->rchild=creatree();
}
return t;

}

/*先序遍历的递归函数*/
void preorder (leafnode* T)
{
if(T)
{
cout<<T->leaf;
preorder(T->lchild);
preorder(T->rchild);
}
}
/*中序遍历的递归函数*/
void inorder (leafnode* T)
{
if(T)
{
inorder(T->lchild);
cout<<T->leaf;
inorder(T->rchild);
}
}
/*后序遍历的递归函数*/
void postorder (leafnode* T)
{
if(T)
{
postorder(T->lchild);
postorder(T->rchild);
cout<<T->leaf;
}
}

度为0的结点数（即叶子结点数）=度为2的结点数+1。题目中给出叶子结点数为22个，利用性质可计算出度为2的结点数为21个。在二叉树只有三种结点：度为0的、度为1的、度为2的，总数为25个，所以度为1的结点数即为22+13+21=56个

因为叶子节点与度为2的结点的关系是：n0＝n2＋1；
因为 n0＝22，所以 n2＝2；
总的结点数：n＝n0＋n1＋n2＝22＋13＋2＝37

---

临泽县15971306382： C++:一棵二叉树,叶子结点数为22,度为1的结点数为13,则该二叉树的结点总数为( ). - ？
宗丽川贝： 因为叶子节点与度为2的结点的关系是:n0=n2+1; 因为 n0=22,所以 n2=2; 总的结点数:n=n0+n1+n2=22+13+2=37

临泽县15971306382： 二叉树求叶子结点个数算法(c++) - ？
宗丽川贝： #include<iostream> #include<string> using namespace std; int geshu=0; template<class T> struct Node { T data; Node<T> *zuohaizi,*youhaizi; }; template <class T> class shu { public: zhongshu(); ~shu(); void qianli(Node<T> *root); void zhongli(Node...

临泽县15971306382： C++二叉树算叶子结点个数递归算法解析 - ？
宗丽川贝： 因为d没有左右子叶,因此return结束这个调用,然后执行LeafCount(root->right),也就是子叶e咯,顺序执行嘛

临泽县15971306382： 二叉树的叶子节点数如何计算? - ？
宗丽川贝： 二叉树的叶子节点数:没有子树的结点是叶子结点.结点的度是指,该结点的子树的个数,在二叉树中,不存在度大于2的结点. 计算公式:n0=n2+1 n0 是叶子节点的个数 n2 是度为2的结点的个数 n0=n2+1=5+1=6 故二叉树有5个度为2的结点,则该二叉树中的叶子结点数为6.

临泽县15971306382： C++: 在一棵含有n个结点的二叉树中.其分支数(边数)为( );若此二叉树只有度为2的分 - ？
宗丽川贝： 在一棵含有n个结点的二叉树中.其分支数(边数)为( n-1 );若此二叉树只有度为2的分支结点和度为0的叶子结点,则该树中叶子结点的数目为((n+1)/2 );若此二叉树的深度(根所在数为1,深度为树的最大层数)为d,且此树为满二叉树,则此树的结点数n为( log2 (d)+1 ).

临泽县15971306382： C++: 编写程序,创建一个二叉树.实现统计二叉树叶子结点的个数和二叉树的深度 - ？
宗丽川贝： #include typedef int ElemType; //数据类型//定义二叉树结构,与单链表相似,多了一个右孩子结点 typedef struct BiTNode{ ElemType data; //数据域 struct BiTNode*lChild, *rChlid; //左右子树域 }BiTNode, *BiTree;//先序创建二叉树 int ...

临泽县15971306382： 2叉数的叶子节点的算法 - ？
宗丽川贝： 设二叉树的叶子节点数为n0,度数为2的节点数为n2.设n1为二叉树中度为1的节点数.因为二叉树中所有节点的度都等于2,所以二叉树节点总数n=n0+n1+n2再看二叉树的分支数,除了根节点外,其余节点都有一个分支进入,设B为分支总数,...

临泽县15971306382： 怎么用C语言写求一棵二叉树的叶子结点个数 - ？
宗丽川贝： int LeaveCount(BiTree T) { int i=0;if(T->leftchild) {i++; i+=LeaveCount(BiTree T->leftchild);}if(T->rightchild) {i++; i+=LeaveCount(BiTree T->rightchild);} return i; }

临泽县15971306382： 告诉了一棵完全二叉树的总结点个数,求叶子结点个数怎么计算?谢谢帮助 - ？
宗丽川贝： 前九层的结点就有2^9-1=511个 而第九层的结点数是2^(9-1)=256 所以,第十层的叶子结点数是699-511=188个现在来算第九层的叶子结点个数:由于第十层的叶子结点是从第九层延伸的,所以应该去掉第九层中还有子树的结点.因为第十层...

临泽县15971306382： 设一颗二叉树中,度为2的结点数为9,则该二叉树的叶子节点的数目是? - ？
宗丽川贝： n0=n2+1 证明:设二叉树T中度为1得结点数为n1,结点总数为n.由于T中所有结点度数均不大于2,因此,T中结点总数n=n0+n1+n2 (1) 再考虑树T的分支数.除了根结点外,其余每个结点都有一条向上的分支与双亲结点相连,因此总共有n-1(即总节点-根节点)条向上的分支.从另一个角度看,每个结点有其“度数”条向下的分支与孩子结点相连,因此总共有n1+2n2条向下的分支.因此有:n-1=n1+2n2 (2) 由(1)和(2)->n0=n2+1 因此答案为10