若用二叉链表作为二叉树的存储表示，试针对以下问题编写算法：统计二叉树终结点的个数
int count(Node *root) {
if (!root) return 0;
int ret = count(root->leftChild) + count(root->rightChild);
return ret == 0 ? 1 : ret;
}
第一行: 空指针返回0
第二行：统计左右子树的叶子节点个数
第三行：如果左右子树的叶子节点个数为0,则本身是一个叶子节点，返回1；否则返回左右子树的叶子节点个数。
及层次顺序遍历二叉树的算法。
#define M 10
typedef int DataType;/*元素的数据类型*/
typedef struct node
{ DataType data;
struct node *lchild,*rchild;
}BitTNode,*BiTree;
int front=0,rear=0;
BitTNode *que[10];
BitTNode *creat()
{BitTNode *t;
DataType x;
scanf("%d",&x);
if(x==0) t=NULL;
else{ t=(BitTNode *)malloc(sizeof(BitTNode));
t->data=x;
t->lchild=creat();
t->rchild=creat();
}
return(t);
}/*creat*/
/* 前序遍历二叉树t */
void preorder(BiTree t)
{ if(t!=NULL)
{ printf("%4d",t->data);
preorder(t->lchild);
preorder(t->rchild);
}
}
/* 中序遍历二叉树t */
void inorder(BiTree t)
{ if(t!=NULL)
{ inorder(t->lchild);
printf("%4d",t->data);
inorder(t->rchild);
}
}
/* 后序遍历二叉树t */
void postorder(BiTree t)
{ if(t!=NULL)
{ postorder(t->lchild);
postorder(t->rchild);
printf("%4d",t->data);
}
}
void enqueue(BitTNode *t)
{if (front!=(rear+1)%M)
{ rear=(rear+1)%M;
que[rear]=t;
}
}/*enqueue*/
BitTNode * delqueue()
{ if(front==rear)return NULL;
{ front=(front+1)%M;
return (que[front]);
}
}/*delqueue*/
/* 按层次遍历二叉树t */
void levorder(BiTree t)
{ BitTNode *p;
if(t!=NULL)
{ enqueue(t);
while (front!=rear)
{ p=delqueue();
printf("%4d",p->data);
if(p->lchild!=NULL) enqueue(p->lchild);
if(p->rchild!=NULL) enqueue(p->rchild);
}
}
}/* levorder */
main()
{BitTNode *root;
root=creat();
printf("
按先序遍历次序生成的二叉树");
printf("
前序遍历二叉树");
preorder(root);
printf("
中序遍历二叉树");
inorder(root);
printf("
后序遍历二叉树");
postorder(root);
printf("
层次顺序遍历二叉树");
levorder(root);
}
2、以二叉链表作存储结构，试编写计算二叉树深度、所有结点总数、叶子结点数、双孩子结点个数、单孩子结点个数的算法
#include <stdio.h>
#define MaxSize 100
typedef char ElemType;
typedef struct node
{
ElemType data;
struct node *left,*right;
} BTree;
BTree * createbt( )
{ BTree *q;
struct node1 *s[30];
int j,i,x;
printf("建立二叉树，输入结点对应的编号和值,编号和值之间用逗号隔开
");
printf("i,x = ");
scanf("%d,%c",&i,&x);
while(i != 0 && x != '$')
{ q = (BTree*)malloc(sizeof(BTree)); /*建立一个新结点q*/
q->data = x; q->left = NULL; q->right = NULL;
s[i] = q; /*q新结点地址存入s指针数组中*/
if(i != 1) /*i = 1，对应的结点是根结点*/
{ j = i / 2; /*求双亲结点的编号j*/
if(i % 2 == 0)
s[j]->left = q; /*q结点编号为偶数则挂在双亲结点j的左边*/
else
s[j]->right = q; /*q结点编号为奇数则挂在双亲结点j的右边*/
}
printf("i,x = ");
scanf("%d,%c",&i,&x);
}
return s[1]; /*返回根结点地址*/
}
void preorder(BTree *BT)
/* 前序遍历二叉树t */
{ if(BT!=NULL)
{ printf("%4c", BT ->data);
preorder(BT ->left);
preorder(BT ->right);
}
}
int BTreeDepth(BTree *BT)
{
int leftdep,rightdep;
if (BT==NULL)
return(0);
else
{
leftdep=BTreeDepth(BT->left);
rightdep=BTreeDepth(BT->right);
if (leftdep>rightdep)
return(leftdep+1);
else
return(rightdep+1);
}
}
int nodecount(BTree *BT)
{
if (BT==NULL)
return(0);
else
return(nodecount(BT->left)+nodecount(BT->right)+1);
}
int leafcount(BTree *BT)
{
if (BT==NULL)
return(0);
else if (BT->left==NULL && BT->right==NULL)
return(1);
else
return(leafcount(BT->left)+leafcount(BT->right));
}
int notleafcount(BTree *BT)
{
if (BT==NULL)
return(0);
else if (BT->left==NULL && BT->right==NULL)
return(0);
else
return(notleafcount(BT->left)+notleafcount(BT->right)+1);
}
int onesoncount(BTree *BT)
{
if (BT==NULL)
return(0);
else if ((BT->left==NULL && BT->right!=NULL) ||
(BT->left!=NULL && BT->right==NULL))
return(onesoncount(BT->left)+onesoncount(BT->right)+1);
else
return(onesoncount(BT->left)+onesoncount(BT->right));
}
int twosoncount(BTree *BT)
{
if (BT==NULL)
return(0);
else if (BT->left==NULL || BT->right==NULL)
return(twosoncount(BT->left)+twosoncount(BT->right));
else if (BT->left!=NULL && BT->right!=NULL)
return(twosoncount(BT->left)+twosoncount(BT->right)+1);
}
main()
{
BTree *B;
B=creatree();
printf("
按先序遍历次序生成的二叉树");
preorder(B);
printf("
二叉树深度:%d
",BTreeDepth(B));
printf("总结点个数:%d
",nodecount(B));
printf("叶子结点个数:%d
",leafcount(B));
printf("非叶子结点个数:%d
",notleafcount(B));
printf("具有双孩子结点个数:%d
",twosoncount(B));
printf("具有单孩子结点个数:%d
",onesoncount(B));
}
如果还没解决你的问题，可以加我百度HI账号。
{ //递归方法，
if ( T )
{
if ((!T->lchild)&& (!T->rchild))
count++;
CountLeaf( T->lchild, count); // 统计左子树中叶子结点个数
CountLeaf( T->rchild, count); // 统计右子树中叶子结点个数
}
}
----------
非递归，就是采用前序/中序/后序遍历所有节点，并统计。下面就给你提供分别用三个函数的统计方法(PS：因为计数器定义为全局，所以三个函数不能同时使用，使用其中一个就能统计你要的节点数)。
#include "stdlib.h"
#define MAXNODE 20
#define ISIZE 8
#define NSIZE0 7
#define NSIZE1 8
#define NSIZE2 15
//SHOWCHAR = 1(显示字符) SHOWCHAR = 0(显示数字)
#define SHOWCHAR 1
//二叉树结构体
struct BTNode
{
int data;
BTNode *rchild;
BTNode *lchild;
};
//非递归遍堆栈
struct ABTStack
{
BTNode *ptree;
ABTStack *link;
};
static pCounter = 0; //计数器，记录节点个数
/*
前序遍历函数pre_Order_Access()<非递归算法>
参数描述：
BTNode *head: 根节点指针
*/
void pre_Order_Access(BTNode *head)
{
BTNode *pt;
ABTStack *ps,*top;
pt = head;
top = NULL;
printf("\n二叉树的前序遍历结果<非递归>：\t");
while(pt!=NULL ||top!=NULL) /*未遍历完,或堆栈非空*/
{
while(pt!=NULL)
{
if(SHOWCHAR)
printf("%c ",pt->data); /*访问根节点*/
else
printf("%d ",pt->data); /*访问根节点*/
ps = (ABTStack *)malloc(sizeof(ABTStack)); /*根节点进栈*/
ps->ptree = pt;
ps->link = top;
top = ps;
pt = pt->lchild; /*遍历节点右子树,经过的节点依次进栈*/
pCounter++;
}
if(top!=NULL)
{
pt = top->ptree; /*栈顶节点出栈*/
ps = top;
top = top->link;
free(ps); /*释放栈顶节点空间*/
pt = pt->rchild; /*遍历节点右子树*/
}
}
}
/*
中序遍历函数mid_Order_Access()<非递归算法>
参数描述：
BTNode *head: 根节点指针
*/
void mid_Order_Access(BTNode *head)
{
BTNode *pt;
ABTStack *ps,*top;
int counter =1;
pt = head;
top = NULL;
printf("\n二叉树的中序遍历结果<非递归>：\t");
while(pt!=NULL ||top!=NULL) /*未遍历完,或堆栈非空*/
{
while(pt!=NULL)
{
ps = (ABTStack *)malloc(sizeof(ABTStack)); /*根节点进栈*/
ps->ptree = pt;
ps->link = top;
top = ps;
pt = pt->lchild; /*遍历节点右子树,经过的节点依次进栈*/
pCounter++;
}
if(top!=NULL)
{
pt = top->ptree; /*栈顶节点出栈*/
ps = top;
top = top->link;
free(ps); /*释放栈顶节点空间*/
if(SHOWCHAR)
printf("%c ",pt->data); /*访问根节点*/
else
printf("%d ",pt->data); /*访问根节点*/
pt = pt->rchild; /*遍历节点右子树*/
}
}
}
/*
后序遍历函数last_Order_Access()<非递归算法>
参数描述：
BTNode *head: 根节点指针
*/
void last_Order_Access(BTNode *head)
{
BTNode *pt;
ABTStack *ps,*top;
int counter =1;
pt = head;
top = NULL;
printf("\n二叉树的后序遍历结果<非递归>：\t");
while(pt!=NULL ||top!=NULL) /*未遍历完,或堆栈非空*/
{
while(pt!=NULL)
{
ps = (ABTStack *)malloc(sizeof(ABTStack)); /*根节点进栈*/
ps->ptree = pt;
ps->link = top;
top = ps;
pt = pt->lchild; /*遍历节点右子树,经过的节点依次进栈*/
pCounter++;
}
if(top!=NULL)
{
pt = top->ptree; /*栈顶节点出栈*/
ps = top;
top = top->link;
free(ps); /*释放栈顶节点空间*/
printf("%c ",pt->data); /*访问根节点*/
pt = pt->rchild; /*遍历节点右子树*/
}
}
}
int tongji(bitree *t)
{if(t!=NULL)
{i++; /*i的初值是0*/
tongji(t->lchild);
tongji(t->rchild);
}
return(i);
}
遍历的时候计数就好了，树的遍历在任何一本算法书都是例子吧
若二叉树用二叉链表做存储结构,则在N个结点的二叉树链表中只有N-1个...
其实可以这样理解：N个节点的二叉树，若用二叉链表表示 则每个节点都有两个链域 也就是2N个 ，然后除了根节点外 每个节点都能但只能被指一次，所以有N-1个链域 不为空 因而 有N+1个链域为空,,
利用二叉链表作为存储结构建立一棵二叉树,每个结点中存放一种水果名(由...
这个很简单吗，给你段代码，是我最近刚编的二叉树程序，已经在vc++6.0和devc++上调试过了。其中包括一个前序的创建；前序，中序，后序的输出；还有一个前序，中序输入一棵树，确定后序，我是用队列作的，你可以先注释掉，先解决主要问题；另外就是一些诸如求高度，节点数的小方法。我这个是整形...
采用二叉链表作为存储结构,将一棵非空树转换为二叉树后,根结点没有右...
是的。采用二叉链表作为存储结构,将一棵非空树转换为二叉树后,根结点是没有右子树的。
用二叉链表作为存储结构,建立二叉树,对二叉树进行前序、中序、后序遍...
function FirstOrderAccess0()功能：实现二叉树的前序遍历 二叉树前序遍历的思想：从根节点开始，沿左子树一直走到没有左孩子的节点为止，依次访问所经过的节点，同时所经[节点]的地址进栈；当找到没有左孩子的节点时，从栈顶退出该节点的双亲的 右孩子，此时，此节点的左子树已访问完毕；在用上述方法...
假设以二叉链表存储的二叉树中,每个结点所含数据元素均为单字母,试编写...
同理，第四层的打印空间是9个字符宽，第五层是4个字符宽，第六层是1个字符宽。因此，这个程序最多只能显示6层的二叉树。中序访问二叉树（从右子树开始，而不是左子树）的结点，根据结点的深度打印相应的空格，每打印一个字母就换行，当整个二叉树的中序访问结束后就打印出树状二叉树了。
二叉树以二叉链表存储,试定义二叉链表的结构,并编写复制一棵二叉树的...
用递归实现：void PrintBiTree(BiTree T){ cout<<endl;LayerTraverse(T,printelem);cout<<endl;} void CopyBiTree(BiTree T,BiTree &M){ if (!T) M=T;else{ M=new BiTNode;M->data=T->data;CopyBiTree (T->lchild,M->lchild);CopyBiTree(T->rchild,M->rchild);} } ...
设一棵二叉树以二叉链表为储存结构,设计一个递归算法将所有结点的左右子...
\/\/我做了一个程序，可以实现二叉树的左右子树的交换功能，#include<iostream.h>\/* 二叉树类型的定义(二叉链表形式储存) *\/ typedef char datatype; \/\/ 树的结点数据类型为字符型，可以根据需要修改 typedef struct node *pointer; \/\/ 定义二叉树结点类型 struct node { datatype data; \/\/...
若二叉树采用二叉链表存储结构,要交换其所有分支结点左、右子树的位置...
【答案】：C 本题用后序遍历肯定没问题，不过用层次遍历也可以实现，所以选D也不能算错，相比之下，后序遍历实现的程序更容易理解，作为单项选择题，首选的应该是C。
假定一棵二叉树用二叉链表存储试编写求出二叉树中1度结点个数的算法_百...
\/ 设0度结点 1度结点 2度结点个数分别为x0 x1 x2 \/ x0+x1+x2 = node_count;\/\/三种结点数之和为总结点数 0*x0 + 1*x1 + 2*x2 = node_count - 1;\/\/树枝数等于结点数减1（去掉根结点）一式乘2减二式得 2*x0 + x1 = node_count + 1;因此只要知道叶子数和总结点数就可得1...
怎么建立一棵以二叉链表方式存储的二叉树,并且对其进行遍历(先序、中...
printf("先序递归遍历二叉树c:\\n");PreOrderTraverse(c,visit);printf("将树C插入树T中,请输入树T中树C的双亲结点C为左(0)或右(1)子树:");scanf("%d,%d",&e1,&i);p=Point(T,e1);\/\/p指向二叉树T中将T中作为二叉树C的双亲结点的e1InsertChild(p,i,c);\/\/将树C插入到二叉树T中作为结点的左...
廉琪桂枝： 递归:void exchange(BTree *rt){ BTree *temp = NULL; if(rt->lchild == NULL && rt->rchild == NULL) return; else{ temp = rt->lchild; rt->lchild = rt->rchild; rt->rchild = temp; } if(rt->lchild) exchange(rt->lchild); if(rt->rchild) exchange(rt->rchild); } 非递归:...
旺苍县18369158970： 请高任帮忙解答一下:若用二叉链表作为二叉树的存储表示,试编写算法统计二叉树中叶结点的个数 - ？
廉琪桂枝： , int& count) { //递归方法,if ( T ) { if ((!T->lchild)&& (!T->rchild)) count++; CountLeaf( T->lchild, count); // 统计左子树中叶子结点个数 CountLeaf( T->rchild, count); // 统计右子树中叶子结点个数 } }---------- 非递归,就是采用前序/中序/后序遍历所...
旺苍县18369158970： 假设以二叉链表作为二叉树的存储结构,试编写一个求树的高度的算法 - ？
廉琪桂枝： int length(BiTree T) { int h1,h2; if(T==NULL) return 0; if(T->lchild==NULL && T->rchild==NULL) return 1; h1=length(T->lchild); h2=length(T->rchild); return h1>=h2?h1:h2; } BiTree Find(BiTree T,ElemType x) //该函数2113返回5261给4102定值的1653结...
旺苍县18369158970： (1)以二叉链表作为二叉树的存储结构,写出二叉树的存储结构定义(C或C++表示). (2)编程实现以二叉链 - ？
廉琪桂枝： 思想上,可以构造“节点”这种结构体,该结构体包含自身的值,还有左孩子指针,右孩子指针.朝这个方向自己构思,希望能帮到你!欢迎追问
旺苍县18369158970： 假设二叉树采用二叉链表作为存储结构,试编写一个算法:求任意一个指定结点所在的层次. - ？
廉琪桂枝： 非递归中序遍历 构造变量count记录当前层访问到的节点数,nextcount记录当前层的总个数; 每当访问过一层层数depth++; 此种方法同时可以求最大宽度,访问第几层的第几个节点,求带权路径长度WPL,是一种通用方法! int TreeDepth(...
旺苍县18369158970： 对于一棵具有n个结点的二叉树,当用二叉链表作为存储结构时,其二叉链表中的指针域的总数为______个,其中______个用于链接孩子结点,_______个为... - ？
廉琪桂枝：[答案] n个节点则有2n个链域,除了根节点没有被lchild和rchild指向,其余的节点必然会被指到.所以空链域有2n-(n-1)=n+1;非空链域有2n-(n+1)=n-1
旺苍县18369158970： 设某棵二叉树中度数为0的结点数为N0,度数为1的结点数为N1,若采用二叉链表作为该二叉树的存储结构,则该二叉 则该二叉树中共有()个空指针域. - ？
廉琪桂枝：[选项] A. N0+N1 B. N0+1 C. 2N0+N1 D. N0-1 请帮忙 解答 一下,并说详细说一下选择的理由,谢谢了.
旺苍县18369158970： 设一棵二叉树以二叉链表为存储结构,试写出求该二叉树中所有叶子结点数的算法. - ？
廉琪桂枝： //我做了一个程序,可以实现二叉树的左右子树的交换功能,#include<iostream.h>/* 二叉树类型的定义(二叉链表形式储存) */ typedef char datatype; // 树的结点数据类型为字符型,可以根据需要修改 typedef struct node *pointer; // 定义二叉...
