已知二叉树采用链表存储结构,根结点指针为T,请写出计算二叉树中度为2的结点数目的非递归算法
#include //头文件
#include
typedef struct BiTNode
{
char data;
struct BiTNode *lchild,*rchild;
}
BiTNode,*BiTree;//定义结点类型
BiTree CreateBiTree()//创建树
{
char p;BiTree T;
scanf("%c",&p);
if(p==' ')
T=NULL;
else
{
T=(BiTNode *)malloc(sizeof(BiTNode));//为结点开辟空间
T->data=p;
T->lchild=CreateBiTree();
T->rchild=CreateBiTree();
}
return (T);
}
int Nochild(BiTree T)//叶子结点
{
if(T==NULL)
return(0);
if(T->lchild==NULL&&T->rchild==NULL)
return(1);
return(Nochild(T->lchild)+Nochild(T->rchild));
}
int Onechild(BiTree T)//度为1的
{
int n=0;
if(T==NULL)
return(0);
if((T->lchild==NULL&&T->rchild!=NULL)||(T->lchild!=NULL&&T->rchild==NULL))
n=1;
return(Onechild(T->lchild)+Onechild(T->rchild)+n);
}
int Twochild(BiTree T)//度为2的
{
int n=0;
if(T==NULL)
return(0);
if(T->lchild!=NULL&&T->rchild!=NULL)
n=1;
return( Twochild(T->lchild)+Twochild(T->rchild)+n);
}
void main()//主函数
{
BiTree Ta;
printf("请创建树:
");
Ta=CreateBiTree();
printf("叶子数为:%d,度为1的数为:%d,度为2的为:%d",Nochild(Ta),Onechild(Ta),Twochild(Ta));
}
将二叉树遍历一边即可
static int count = 0;//记录二叉树叶子节点的个数
struct Node{
int data;
Node *rigthNode;//右孩子
Node *leftNode;//左孩子
};
int fine_Node(Node * t)//Node 表示二叉树节点
{
if(t == Null)
{
return 0;
}
else if((fine_Node(t->rigthNode)+fine_Node(t->leftNode)) != 0)
{
return 1;
}
else
{
count++;
return 1;
}
}
push(ST,root)
while(not empty(ST))
{
node=pop(ST)
if(node->left)
push(ST,node->left)
if(node->right)
push(ST,node->right)
}
上面的伪代码实际上就是图的深度遍历,二叉树算是一种特殊的图。
具体的写法可以搜索一下就可以找到。
int Count(AGraph *T,int v,int visit[maxSize])
{
ArcNode *p;
int que [maxSize],front=0,rear=0;
int j;
int s=0;
Visit(v);
visit(v)=1;
rear=(rear+1)%maxSize
que[rear]=v;
while(front!=rear)
{
int k=0;
front=(front+1)%maxSize;
j=que[front];
p=T->adjlist[j].firstarc
while(p!=NULL)
{
k++;
if(visit [p->adjvexj==0)
{
Visit(p->adjvex);
visit[p->adjvex]=1;
rear=(rear+1)%maxSize;
que[rear]=p->adjvex;
}
p=p->nextarc;
}
}
if(k==2)
{
s++;
}
return s;
}
若二叉树采用二叉链表存储结构,要交换其所有分支结点左、右子树的位置...
【答案】:C 本题用后序遍历肯定没问题,不过用层次遍历也可以实现,所以选D也不能算错,相比之下,后序遍历实现的程序更容易理解,作为单项选择题,首选的应该是C。
若二叉树采用二叉链表存储结构,要交换其所有分支结点左、右子树的位置...
答案:C。用二叉链表存储结构也就是左孩子右兄弟的存储结构。后序遍历比较合理。正常的逻辑应该就是:做好当前结点子树内部的交换,然后交换当前结点的左右子树。刚好符合后序遍历的算法逻辑。1、交换好左子树 2、交换好右子树 3、交换左子树与右子树 其他算法如先序和按层次其逻辑都差不多,即访问当前...
已知一棵二叉树是以二叉链表的形式存储的求出以T为根的子树的结点个数...
已知一棵二叉树是以二叉链表的形式存储的,其结点结构说明如下:structnode{intdata;structnode*left;structnode*right;};要求写出2个具有下面功能的算法:①、求出以T为根的子树的结... 已知一棵二叉树是以二叉链表的形式存储的,其结点结构说明如下:struct node{int data;struct node * left;struct node * right...
具有N个结点的二叉树,采用二叉链表存储,共有( )个空 链域.
这道数据题一共有N+1个空链域。二叉树是n个有限元素的集合,该集合或者为空、或者由一个称为根的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成,是有序树。当集合为空时,称该二叉树为空二叉树。在二叉树中,一个元素也称作一个结点。满二叉树:如果一棵二叉树只有度为0的结点...
已知二叉树采用二叉链表方式存放 要求返回二叉树T的后序序列的第一个...
\/\/ 构造二叉链表表示的二叉树T。变量Nil表示空(子)树。修改 int number;scanf("%d",&number); \/\/ 输入结点的值 if(number==Nil) \/\/ 结点的值为空 T=NULL;else \/\/ 结点的值不为空 { T=(BiTree)malloc(sizeof(BiTNode)); \/\/ 生成根结点 if(!T)exit(OVERFLOW);T->data=number; \/\/...
已知非空二叉树采用二叉树链表存储结构,根节点为T,写出非空二叉树的...
数据结构是 struct Tree { int data;Tree lchild,rchild;}*bt;void post_order(Tree t){ if(t.lchild) post_order(t.lchild);printf("%d\\n",t.data);if(t.rchild) post_order(t.rchild);}
已知一棵二叉树以二叉链表为存储结构,编写如下程序:对于树中每一个元 ...
先前序遍历整个二叉树,找到符合要求的结点,然后后序遍历该结点的整个子树,逐一释放结点。\/\/假设二叉树结构体如下struct binTree{ int data; binTree *lchild; binTree *rchild;}*BiTree;\/\/函数如下BiTree find(BiTree node, int x){ if(node) { if(node->data==x) dele...
已知二叉树按二叉链表方式存储 设计算法计算二叉树深度
有一棵已建好的二叉树 根指针为*root 函数max定义为 int max(int a,int b){ if (a>b)return a;else return b;} 则设计递归算法 函数 depth int depth(struct bintree r){ if (r==NULL)return 0;if (r->left == NULL && r->right == NULL)return 1;else return 1+(max(depth(...
假设二叉书采用二叉链表存储结构,设计一个算法,求二叉树中指定结点x...
初始值为0 下列算法是递归嵌套。1、n++,遍历当前节点的左子树 2、n--,访问当前节点,如果节点的data==x,那么(意味着找到节点了)打印节点层数 3、n++,遍历当前节点的右子树 递归结束后,如果没有找到X节点不要忘了,打印一下没有找到。参考资料:严蔚敏清华大学出版社《数据结构》第二版 ...
编写算法:已知二叉排序树按二叉链表形式存储,树中结点各不相同,欲得...
二叉排序树(Binary Sort Tree)又称二叉查找树,亦称二叉搜索树。 它或者是一棵空树;或者是具有下列性质的二叉树: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值; (3)左、右子树也分别为二叉排序树;...
苍樊康迈: 采用深度或者广度遍历就可以,分别采用栈或者队列结构.对于访问到的每个节点,如果度为2,就是所求的.比如用栈的话 push(ST,root) while(not empty(ST)) {node=pop(ST)if(node->left)push(ST,node->left)if(node->right)push(ST,node->right) }上面的伪代码实际上就是图的深度遍历,二叉树算是一种特殊的图. 具体的写法可以搜索一下就可以找到.
乌拉特前旗15040497420: 已知非空二叉树采用二叉树链表存储结构,根节点为T,写出非空二叉树的非递归中序遍 - ?
苍樊康迈: 数据结构是 struct Tree { int data; Tree lchild,rchild; }*bt; void post_order(Tree t) { if(t.lchild) post_order(t.lchild); printf("%d\n",t.data); if(t.rchild) post_order(t.rchild); }
乌拉特前旗15040497420: 已知一棵二叉树是以二叉链表的形式存储的,其结点结构说明如下: struct node { int data; struct node * 已知一棵二叉树是以二叉链表的形式存储的,其结点... - ?
苍樊康迈:[答案] #include#include/*①、求出以T为根的子树的结点个数.②、求出以T为根的子树的高度.*/typedef struct node{ int data; struct node * left; struct node * right;}BiTNode,*BiTree;/*①、求出以T为根的子树的结点...
乌拉特前旗15040497420: 用二叉链表存储树,为什么根结点的右指针是空,数据结构 - ?
苍樊康迈: 采用二叉树结构存储树或森林,即树/森林的左子右兄表示法. 二叉树中节点的左“孩子”是原树/森林对应节点的“长子节点”,右“孩子”是原树/森林对应节点的“兄弟节点”. 而树的根节点是没有兄弟的,故在二叉链表中它的右指针为空()
乌拉特前旗15040497420: 删除叶结点,C语言! - ?
苍樊康迈: 中序遍历:void inorder(Tree* root, Tree* top , bool left) { if (root.value == key) { if (left) top.left = NULL; else top.right = NULL; //delete the node } inorder(root.lchild, root, true); inorder(root.rchild, root, flase); }
乌拉特前旗15040497420: 二叉树用二叉链表结构进行存储,请编写算法求二叉树根结点左右子树相 - ?
苍樊康迈: int BiTreeCount(BiTree T) { int rNum,lNum; if(!T) return 0; else { lNum = BiTreeCount(T->lchild); rNum = BiTreeCount(T->rchild); return rNum + lNum + 1; } }
乌拉特前旗15040497420: 已知一棵二叉树以二叉链表为存储结构,编写如下程序:对于树中每一个元素值为x的结点,删去以它为根的子 - ?
苍樊康迈: 先前序遍历整个二叉树,找到符合要求的结点,然后后序遍历该结点的整个子树,逐一释放结点.//假设二叉树结构体如下 struct binTree { int data; binTree *lchild; binTree *rchild; }*BiTree;//函数如下 BiTree find(BiTree node, int x) { if(node) { if(...
乌拉特前旗15040497420: 二叉树采用二叉链表存储,统计以值为X的结点为根的子树中叶子结点的数目. - ?
苍樊康迈: 递归求解.思路基本类似于求叶子结点数目的算法,只不过统计变量+1的条件是结点值等于x.
乌拉特前旗15040497420: 设棵二叉树以二叉链表为存储结构,结点结构为lchild|dadt|rchild.设计一个算法,求在前根序列中第k结点 - ?
苍樊康迈: 用一个全局变量计数count,每进入一个节点,就count++,思路是这样,具体实现也不是很复杂
乌拉特前旗15040497420: 紧急求助:请写出递归算法,从小到大输出二叉排序树中所有数据值>=x的结点的数据. - ?
苍樊康迈: 由于是二叉排序树,因此只要使用中序遍历,输出比x大的数即可. void printMoreThanX(TreeNode *root, int x) {if (root == NULL)return; printMoreThanX(root->left, x, bPrint);if (root->data >= x){printf("%d ", root->data);}printMoreThanX(root->right, x, bPrint); }