二叉树链式存储,写出节点总数与叶子数的程序代码,C语言版的,VC6运行平台。。。
叶子结点共有16个。
在一棵满二叉树中,节点的个数为2^n-1,叶子节点的个数为:2^(n-1)。
一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,除最后一层外,每一层上的所有节点都有两个子节点,即在满二叉树的第k层上有2^(k-1)个节点,且深度为m的满二叉树中有2^m-1个节点。
满二叉树满足如下性质。
1、一个层数为k 的满二叉树总结点数为:2^k-1。因此满二叉树的结点数一定是奇数个。
2、第i层上的结点数为:2^i-1
3、一个层数为k的满二叉树的叶子结点个数(也就是最后一层):2^k-1。
扩展资料满二叉树和完全二叉树的区别
1、定义不同
完全二叉树指除最后一层外,每一层上的节点数都达到最大值;在最后一层上只缺少右边的若干节点。
满二叉树指每一个层的结点数都达到最大值,即除最后一层外,每一层上的所有节点都有两个子节点。
2、关系不同
满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树。
参考资料来源:百度百科-完全二叉树
参考资料来源:百度百科-满二叉树
根据“二叉树的第i层至多有2^(i − 1)个结点;深度为k的二叉树至多有2^k − 1个结点(根结点的深度为1)”这个性质:
因为2^9-1 < 700 < 2^10-1 ,所以这个完全二叉树的深度是10,前9层是一个满二叉树,
这样的话,前九层的结点就有2^9-1=511个;而第九层的结点数是2^(9-1)=256
所以第十层的叶子结点数是700-511=189个;
现在来算第九层的叶子结点个数。
由于第十层的叶子结点是从第九层延伸的,所以应该去掉第九层中还有子树的结点。因为第十层有189个,所以应该去掉第九层中的(189+1)/2=95个;
所以,第九层的叶子结点个数是256-95=161,加上第十层有189个,最后结果是350个。
#include "stdio.h"
#include "string.h"
#define NULL 0
typedef struct BiTNode{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTree Create(BiTree T){
char ch;
ch=getchar();
if(ch=='#')
T=NULL;
else{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
printf("Error!");
T->data=ch;
T->lchild=Create(T->lchild);
T->rchild=Create(T->rchild);
}
return T;
}
void Preorder(BiTree T){
if(T){
printf("%c",T->data);
Preorder(T->lchild);
Preorder(T->rchild);
}
}
int Sumleaf(BiTree T){
int sum=0,m,n;
if(T){
if((!T->lchild)&&(!T->rchild))
sum++;
m=Sumleaf(T->lchild);
sum+=m;
n=Sumleaf(T->rchild);
sum+=n;
}
return sum;
}
void zhongxu(BiTree T){
if(T){
zhongxu(T->lchild);
printf("%c",T->data);
zhongxu(T->rchild);
}
}
void houxu(BiTree T){
if(T){
houxu(T->lchild);
houxu(T->rchild);
printf("%c",T->data);
}
}
int Depth(BiTree T){
int dep=0,depl,depr;
if(!T) dep=0;
else{
depl=Depth(T->lchild);
depr=Depth(T->rchild);
dep=1+(depl>depr?depl:depr);
}
return dep;
}
main(){
BiTree T;
int sum,dep;
T=Create(T);
Preorder(T);
printf("\n");
zhongxu(T);
printf("\n");
houxu(T);
printf("\n");
sum=Sumleaf(T);
printf("%d",sum);
dep=Depth(T);
printf("\n%d",dep);
}
不好的,不给你回答 嘿嘿
以前用C++写过,很简单!
二叉树_链式存储
利用“扩展先序遍历序列” 创建二叉树二叉链表: 1、若输入的字符是 '#',则建立空树; 2、否则建立根结点,接着递归建立左子树,然后递归建立右子树。
二叉链表的存储结构
二叉树的存储结构 二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址
树- 二叉树 - 二叉树的存储结构(二)
在一棵二叉树中 所有类型为BinTNode的结点 再加上一个指向开始结点(即根结点)的BinTree型头指针(即根指针)root 就构 成了二叉树的链式存储结构 并将其称为二叉链表 【例】下面左图所示二叉树的二叉链表如下面中图所示 注意 ① 一个二叉链表由根指针root惟一确定 若二叉树为空 则root=NULL;若...
二叉树的顺序存储和链式存储各有什么优缺点
顺序存储充分利用满二叉树的特性,即每层的节点数分别为1、2、4、8等等2i+1,一个深度为i的二叉树最多只能包含2i-1个节点,因此只要定义一个长度为2i-1的数组即可存储这颗二叉树。对于普通的不是满二叉树的,那些空出来的节点对应的数组元素留空即可,因此顺序存储会造成一定的空间浪费。如果...
4. 设二叉树的存储结构为二叉链表,试写出算法(C函数):将所有结点的左右...
二、 链式存储结构 由二叉树的定义得知二叉树的结点由一个数据元素和分别指向左右子树的两个分支构成 ,则表 示二叉树的链表中的结点至少包含三个域 :数据域和左右指针域 ,如图 (b)所示。有时 ,为了便于找 到结点的双亲 ,则还可在结点结构中增加一个指向其双亲受的指针域,如图 6.7(c)所示。...
数据结构(树和二叉树)
* 二叉树的子树有左右之分,其次序不能任意颠倒。1.顺序存储结构:使用一组地址连续的存储单元来存储数据元素,将二叉树的结点依照自上而下,自左至右存储结点元素。2.链式存储结构:结点包含3个域:数据域,左右指针。遍历二叉树是指按某条搜索路径巡访树中每个结点,使的每个结点均被访问一次,而...
二叉树有哪几种形式?
二叉树的五种形态:1、 空二叉树(什么都没有,nothing)2、 只有一个根节点的二叉树(左右子树为空)3、 右子树为空的二叉树(右腿断了)4、 左子树为空的二叉树(左腿断了)5、 左右子树都非空的的二叉树(既有左子树又有右子树,)...
四叉树存储方法有哪些
采用链式存储。四叉树存储方法有采用链式存储。四叉树(Q-Tree)是一种树形数据结构。四叉树的定义是:每个节点下至多可以有四个子节点,通常把一部分二维空间细分为四个象限或区域并把该区域里的相关信息存入到四叉树节点中。这个区域可以是正方形、矩形或是任意形状。
什么是二叉树的度?
二叉树的度是指树中所以结点的度数的最大值。二叉树的度小于等于2,因为二叉树的定义要求二叉树中任意结点的度数(结点的分支数)小于等于2 。
一个二叉树按顺序方式存储在一个一维数组中,如图:
二叉树按照层序遍历,依次编号,按照编号的顺序,存储在连续存储单元的方式就是二叉树的顺序存储。如果二叉树不是满二叉树,则只存储有内容的节点,缺失的结点在存储的过程中,所对应的位置不存储任何东西,即是空的。对于题中所给的存储结构,构造一个满二叉树,结点为空,再按照层序遍历,依次编号...
偶才喷昔: int CountNode (BTNode *t) //节点总数 { int num; if (t == NULL) num = 0; else num = 1 + CountNode (t->lch) + CountNode (t->rch); return (num); } void CountLeaf (BTNode *t) //叶子节点总数 { if (t != NULL) { if (t->lch == NULL && t->rch == NULL) count ++; // 全局变量 CountLeaf (t->lch); CountLeaf (t->rch); } }
安国市17147939682: 数据结构中,怎样以二叉链表为存储结构,分别写出求二叉树结点总数及叶子总数的算法? - ?
偶才喷昔: 同学,你们老师和我们老师留的作业是一模一样的阿,我有现成的做好了的程序,调试成功.这个程序的难点就在于这种很别扭的输入形式,所以我为它设计了一个结构体形式存放输入内容,再将它转化成了线性结构.#include <iostream.h>#...
安国市17147939682: 设一棵二叉树以二叉链表为存储结构,试写出求该二叉树中所有叶子结点数的算法. - ?
偶才喷昔: //我做了一个程序,可以实现二叉树的左右子树的交换功能,#include<iostream.h>/* 二叉树类型的定义(二叉链表形式储存) */ typedef char datatype; // 树的结点数据类型为字符型,可以根据需要修改 typedef struct node *pointer; // 定义二叉...
安国市17147939682: 已知一棵二叉树采用二叉链表存放,写依程序,要求统计出二叉树中叶子的个数,并输出二叉树中非终端节点 - ?
偶才喷昔: void countleaf(bitnode *t,int *c) { if(t!=null) { if (t->lchild==null && t->rchild==null) {*c=*c+1; } countleaf(t->lchild,c); countleaf(t->rchild,c); } return; } typedef struct bitnode { char data; struct bitnode *lchild, *rchild; }bitnode, *bitree;
安国市17147939682: 采用二叉链表作为存储结构,完成二叉树的建立,前序、中序和后序遍历的操作,求所有叶子及结点总数的操作 - ?
偶才喷昔: #include<iostream> #include<cstdio> #include<stdlib.h> using namespace std; typedef int Elemtype; typedef struct BiTnode {Elemtype data;//数据域struct BiTnode* Lchild,*Rchild; //左右子树域; }BiTnode,*BiTree;int create(BiTree *T) {...
安国市17147939682: 假设二叉树采用二叉链表存储,其结点结构是(lchild,data,rchild).试写出求二叉树叶子结点总数的算法. - ?
偶才喷昔: /* 求叶子数 */ int IsBSt(BtreeNode *BT) {int count1,count2;if(BT==NULL)return 0;else{if(BT->lchild==NULL && BT->rchild==NULL)return 1;else{count1=leafcount(BT->lchild);count2=leafcount(BT->rchild);return count1+count2;}} }
安国市17147939682: 以二叉链为存储结构,写一算法求二叉树的叶子结点个数 - ?
偶才喷昔: 只要在遍历右子树之前加上判断统计就可以了,下面给出一个Vc的程序例子,包括建树、遍历等等,下面先序建立一棵树abcd, 输入(输入一个字符回车一次): a b # # c # d # # 输出;中序遍历结果和叶子节点数实现程序如下:#include<...
安国市17147939682: 二叉树的叶子节点数如何计算? - ?
偶才喷昔: 二叉树的叶子节点数:没有子树的结点是叶子结点.结点的度是指,该结点的子树的个数,在二叉树中,不存在度大于2的结点. 计算公式:n0=n2+1 n0 是叶子节点的个数 n2 是度为2的结点的个数 n0=n2+1=5+1=6 故二叉树有5个度为2的结点,则该二叉树中的叶子结点数为6.
安国市17147939682: 以二叉链表为结构体,写出二叉树结点总数及叶子总数的算法?我需要完整的程序代码 - ?
偶才喷昔: 分太少啊#include <stdlib.h>#include <stdio.h>#define MAXL 100 typedef char Elemtype ; typedef struct { Elemtype e; } Elem; typedef struct BTree { Elem data; struct BTree * lchild,*rchild; } BITnode,*BTree; void Createtree(BTree *T) //创建二叉树 { ...
安国市17147939682: 编写递归算法,求二叉树的结点个数和叶子数 - ?
偶才喷昔: 00DLR(liuyu *root) /*中序遍历 递归函数*/ {if(root!=NULL){if((root->lchild==NULL)&&(root->rchild==NULL)){sum++; printf("%d\n",root->data);}DLR(root->lchild);DLR(root->rchild); }return(0); } 法二: int LeafCount_BiTree(Bitree T)//求二叉树中...