2叉树的创建和非叶子结点解析

1写一个程序实现2叉树的创建和统计树中非叶子结点的个数

/*********方法1：***********/

#include

#include

#include

#include

#define ClearBiTree DestroyBiTree

typedef char Elemtype;

typedef struct BiTNode

{

Elemtype data;

BiTNode *lchild,*rchild;

}BiTNode,*BiTree;

void visit(Elemtype e)

{

printf(\"%c \

}

void InitBiTree(BiTree &T)

{

T=NULL;

}

void CreateBiTree(BiTree &T)

{

Elemtype ch;

scanf(\"%c\

if(ch=='#')

T=NULL;

else

{

T=(BiTree)malloc(sizeof(BiTNode));

if(!T) exit(OVERFLOW);

T->data=ch;

CreateBiTree(T->lchild);

CreateBiTree(T->rchild);

}

}

void DestroyBiTree(BiTree &T)

{

if(T)

{

DestroyBiTree(T->lchild);

DestroyBiTree(T->rchild);

free(T);

T=NULL;

}

}

void PreOrderTraverse(BiTree T,void(*Visit)(Elemtype))

{

if(T)

{

Visit(T->data);

PreOrderTraverse(T->lchild,Visit);

PreOrderTraverse(T->rchild,Visit);

}

}

void InOrderTraverse(BiTree T,void(*Visit)(Elemtype))

{

if(T)

{

InOrderTraverse(T->lchild,Visit);

Visit(T->data);

InOrderTraverse(T->rchild,Visit);

}

}

void PostOrderTraverse(BiTree T,void(*Visit)(Elemtype))

{

if(T)

{

PostOrderTraverse(T->lchild,Visit);

PostOrderTraverse(T->rchild,Visit);

Visit(T->data);

}

}

void sum(BiTree T,void(*Visit)(Elemtype),int *s)//统计树中非叶子结点的个数，并输出

{

if(T->lchild||T->rchild)

{

Visit(T->data);

*s=*s+1;

sum(T->lchild,Visit,s);

sum(T->rchild,Visit,s);

}

}

void main()

{

BiTree T;

InitBiTree(T);

printf(\"按先序次序输入二叉树中结点的值,输入#表示节点为空，输入范例：ab##c##\\n\");

CreateBiTree(T);

printf(\"先序递归遍历二叉树：\\n\");

PreOrderTraverse(T,visit);

printf(\"\\n中序递归遍历二叉树：\\n\");

InOrderTraverse(T,visit);

printf(\"\\n后序递归遍历二叉树：\\n\");

PostOrderTraverse(T,visit);

int s=0;

printf(\"\\n非叶子结点的值为： \\n\");

sum(T,visit,&s);

printf(\"\\n非叶子结点的个数为： \\n\");

printf(\"%d\\n\

}

/********方法2***********/

# include

#include

#define maxsize 100

#define null 0

typedef char elemtype;

typedef struct node

{

elemtype data;

struct node *lchild;

struct node *rchild;

}btnode;

void createbtnode(btnode *&b,char *str) {

btnode *st[maxsize],*p=null;

int top=-1,k,j=0;

//创建

char ch;

b=null;

ch=str[j];

while (ch!='\\0')

{

switch(ch)

{

case'(':top++;st[top]=p;k=1;break;

case')':top--;break;

case',':k=2;break;

default:p=(btnode *)malloc(sizeof(btnode));

p->data=ch;

p->lchild=p->rchild=null;

if (b==null)

b=p;

else

{

switch(k)

{

case 1:st[top]->lchild=p;break;

case 2:st[top]->rchild=p;break;

}

}

}

j++;

ch=str[j];

}

}

void dispbtnode (btnode *b) //输出

{

if(b!=null)

{

printf(\"%c\

if(b->lchild!=null||b->rchild!=null)

{

printf(\"(\");

dispbtnode(b->lchild);

if(b->rchild!=null)printf(\

dispbtnode(b->rchild);

printf(\")\");

}

}

}

int nodes(btnode *b)

{

int num3,num4;

if (b==null)

return 0;

else if(b->lchild==null&&b->rchild==null)

return 1;

else

{

num3=nodes(b->lchild);

num4=nodes(b->rchild);

return(num3+num4+1);

}

}

int unleafnodes(btnode *b)

{

int num1,num2;

if(b==null)

return 0;

else if (b->lchild==null&&b->rchild==null)

return 0;

else

{

num1=unleafnodes(b->lchild);

num2=unleafnodes(b->rchild);

return (num1+num2+1);

}

}

int main ()

{

btnode *b;

createbtnode(b,\"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))\");

printf(\"输出二叉树：\");dispbtnode(b);printf(\"\\n\");

printf(\"二叉树b的结点个数：%d\\n\

printf(\"二叉树b的非叶子结点个数：%d\\n\

getchar ();

return 0;

}

/**************方法3****************/

#include

#include

typedef struct BiTNode{

char data;

struct BiTNode *lchild;

struct BiTNode *rchild;

}BiTNode,*BiTree;

typedef struct {

char *q;

int front,rear;

}Queue;

int n=0;

void InitQueue(Queue &Q)

{

if(!(Q.q=(char*)malloc(100*sizeof(char)))) exit(0);

Q.rear=Q.front=0;

}

void EnQueue(Queue &Q,char c)

{

if((Q.rear+1)%100==Q.front)exit(0);

Q.q[Q.rear]=c;

Q.rear=(Q.rear+1)%100;

}

void DeQueue(Queue &Q,char &c)

{

if(Q.rear==Q.front)exit(0);

c=Q.q[Q.front];

Q.front=(Q.front+1)%100;

}

int EmptyQueue(Queue &Q)

{

return (Q.rear==Q.front);

}

BiTNode* createBiTree(BiTNode *b,Queue &Q)

{

char c;

DeQueue(Q,c);

if(c=='#')

{

b=NULL;

}

else

{

if(!(b=(BiTNode*)malloc(sizeof(BiTNode))))exit(0);

b->data=c;

b->lchild=createBiTree(b->lchild,Q);

b->rchild=createBiTree(b->rchild,Q);

}

return b;

}

int statistic(BiTNode *&T)

{

if(T!=NULL)

{

if(T->lchild!=NULL||T->rchild!=NULL)

{

n=n+1;printf(\"%c \

n=statistic(T->lchild);

n=statistic(T->rchild);

}

}

return n;

}

int main()

{

Queue Q;BiTNode *p;

char c;int i=0,n=0;

InitQueue(Q);

printf(\"请输入所创建的树字符串以回车键为结束#代表放置空元素：\\n\");

while(i<100&&(c=getchar())!='\\n')

{

EnQueue(Q,c);

i++;

}

p=createBiTree(p,Q);

printf(\"\\n改二叉树的非子叶节点有：\");

n=statistic(p);

printf(\"\\n非叶子节点个数为：%d\\n\

system(\"PAUSE\");

return 0;

}

/**********方法4***********/

#include

#include

#define MaxSize 50

typedef char ElemType;

int count=0; /*设置一个全局变量*/

int changdu;

typedef struct node

{

char data; /*数据元素*/

struct node *lchild,*rchild;/*指向左右孩子*/

}BTNode,BiTree;

BTNode * CreateBT(char * pre,char * in,int n)//由先序和中序遍历构造一个二叉树

{

BTNode * s;

char * p;

int k;

if (n<=0) return NULL;

s=(BTNode *)malloc(sizeof(BTNode));//创建二叉树结点*s

s->data=*pre;

for(p =in;pif (*p==*pre)

break;

k=p-in;

s->lchild=CreateBT(pre+1,in,k);

s->rchild=CreateBT(pre+k+1,p+1,n-k-1);

return s;

}

void DispBTNode (BTNode * b)//以括号表示法输出二叉树

{

if (b!=NULL)

{

printf(\"%c\

if (b->lchild!=NULL||b->rchild!=NULL)

{

printf(\"(\");

DispBTNode(b->lchild);//递归处理左子树

if (b->rchild!=NULL) printf(\

DispBTNode(b->rchild);//递归处理右子树

printf (\")\");

}

}

}

int PreOrder(BiTree *&b)//根据已经构建的二叉树，利用循环语句计算非子叶结点的个数

{

if(b!=NULL)

{

if(b->lchild!=NULL||b->rchild!=NULL)//判断条件

{

count++;

count=PreOrder(b->lchild);

count=PreOrder(b->rchild);

}

}

return count;

}

int main()

{

BTNode * b;

char pre[MaxSize];

char in[MaxSize] ;

printf(\"输入先序序列：\");

gets(pre);

printf(\"输入中序序列：\");

gets(in);

printf(\"输入序列的长度：\");

scanf(\"%d\

b=CreateBT(pre,in,changdu);

printf (\"先序序列:%s\\n\

printf(\"中序序列:%s\\n\

printf(\"构造一棵二叉树b：\\n\");

printf(\"括号表示法：\");

count= PreOrder(b);

DispBTNode(b);

printf(\"\\n\");

printf(\"非子叶结点数为：%d\

getch();

return 0;

}