Question

数据结构中，怎样以二叉链表为存储结构，分别写出求二叉树结点总数及叶子总数的算法？

要求上机调试的！！！急。。。

Answer 1

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

#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;
}
}

Answer 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);
}
}

Answer 3

//求叶子节点数
#include<iostream>
using namespace std;
int n=0;//全局变量求叶子总数
template <class T>
struct BiNode
{
T data;
BiNode<T>*lchild,*rchild;
};
template <class T>
class BiTree
{
public:
BiTree(){root=Creat(root);}
int PreOrder(){return PreOrder(root);}
private:
BiNode<T>*root;
int count;
BiNode<T>*Creat(BiNode<T>*bt);
int PreOrder(BiNode<T>*bt);
};
template <class T>
int BiTree<T>::PreOrder(BiNode<T>*bt)
{
if(bt==NULL)return 0;
else{
PreOrder(bt->lchild);
n++;
PreOrder(bt->rchild);
}
return n;
}
template<class T>
BiNode<T>*BiTree<T>::Creat(BiNode<T>*bt)
{ char ch;
cin>>ch;
if(ch=='#')bt=NULL;
else{
bt=new BiNode<T>;bt->data=ch;
bt->lchild=Creat(bt->lchild);
bt->rchild=Creat(bt->rchild);
}
return bt;
}
int main()
{ int t;
BiTree<char> Bt;
t=Bt.PreOrder();
if(t==0)cout<<"NULL"<<endl;
else cout<<t<<endl;
return 0;
}
//求二叉树结点总数
#include<iostream>
using namespace std;
int n=0;
template <class T>
struct BiNode
{
T data;
BiNode<T>*lchild,*rchild;
};
template <class T>
class BiTree
{
public:
BiTree(){root=Creat(root);}
int PreOrder(){return PreOrder(root);}
private:
BiNode<T>*root;
int count;
BiNode<T>*Creat(BiNode<T>*bt);
int PreOrder(BiNode<T>*bt);
};
template <class T>
int BiTree<T>::PreOrder(BiNode<T>*bt)
{
if(bt==NULL)return 0;
else{
PreOrder(bt->lchild);
n++;
PreOrder(bt->rchild);
}
return n;
}
template<class T>
BiNode<T>*BiTree<T>::Creat(BiNode<T>*bt)
{ char ch;
cin>>ch;
if(ch=='#')bt=NULL;
else{
bt=new BiNode<T>;bt->data=ch;
bt->lchild=Creat(bt->lchild);
bt->rchild=Creat(bt->rchild);
}
return bt;
}
int main()
{ int t;
BiTree<char> Bt;
t=Bt.PreOrder();
if(t==0)cout<<"NULL";
else cout<<t;
return 0;
}

Answer 4

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);
}
}

Answer 5

int jiedian(BTNode *b)//节点总数
{
if(b)
return (jiedian(b->lchild)+jiedian(b->rchild)+1);
else
return 0;

}
int yezi(BTNode *b)//叶子总数
{
if(b->lchild==NULL && b->rchild==NULL)
return 1;
else
return (yezi(b->lchild)+yezi(b->rchild));
}