7.1.cpp

对于二叉树的基本的运算

#include<iostream.h>
#include<stdio.h>
#include<malloc.h>
//#include<string.h>
typedef char elemtype;
#define Maxsize 50
//#include"btree.h"

typedef struct node 
{
	elemtype data;
	struct node *lchild;
	struct node *rchild;
}Btnode;

void createBtnode(Btnode *&b,char *str)
{
	Btnode *st[Maxsize];
	Btnode *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];
	}
}

Btnode *findnode(Btnode *b,elemtype x)
{
	Btnode *p;
	if(b==NULL)
		return NULL;
	else if (b->data==x)
		return b;
	else
	{
		p=findnode(b->lchild,x);
		if(p!=NULL)
			return p;
		else
			return findnode(b->rchild,x);
	}
}


Btnode *lchildnode(Btnode *p)
{
		return p->lchild;
}
Btnode *rchildnode(Btnode *p)
{
		return p->rchild;
}

void child(Btnode *p)
{
  //Btnode *n;
  if(p!=NULL)
  {
	  if(p->lchild==NULL && p->rchild==NULL) 
        cout<<p->data;
      child(p->lchild);
      child(p->rchild);
  }
}


int Btnodeheight(Btnode *b)
{
	int lchildh,rchildh;
	if(b==NULL) return(0);
	else
	{
		lchildh=Btnodeheight(b->lchild);
        rchildh=Btnodeheight(b->rchild);
		return (lchildh>rchildh)? (lchildh+1):(rchildh+1);
	}
}

void dispbtnode(Btnode *b)
{
	if (b!=NULL)
	{
		printf("%c",b->data);
		if (b->lchild!=NULL||b->rchild!=NULL)
		{
			printf("(");
			dispbtnode(b->lchild);
			if(b->rchild!=NULL) printf(",");
            dispbtnode(b->rchild);
			printf(")");
		}
	}
}

void preorder(Btnode *b)
{
	if (b!=NULL)
	{
		printf("%c",b->data);
		preorder(b->lchild);
		preorder(b->rchild);
	}
}
void inorder(Btnode *b)
{
	if (b!=NULL)
	{
		inorder(b->lchild);
		printf("%c",b->data);
		inorder(b->rchild);
	}
}
void postorder(Btnode *b)
{
	if (b!=NULL)
	{
      postorder(b->lchild);
	  postorder(b->rchild);
	  printf("%c",b->data);
	} 
}

void Allpath(Btnode *b)
{
	Btnode *st[50];
	Btnode *p;
	int flag,i,top=-1;
	if(b!=NULL)
	{  do
		{  while(b!=NULL)
			{    top++;
	 	         st[top]=b;
		          b=b->lchild;
			}
		    p=NULL;
		    flag=1;
		    while(top!=-1 && flag)
			{   b=st[top];
			    if(b->rchild==p)
				{  
					if(b->lchild==NULL && b->rchild==NULL)
					{
				    for(i=top;i>0;i--)
					printf("%c->",st[i]->data);
					printf("%c\n",st[0]->data);}
					top--;
					p=b;
					
				}
			    else
				{
				b=b->rchild;
				flag=0;
				}
			}
		}while(top!=-1);
         cout<<endl;
	}
}
int f(Btnode *b)
{
	if(b==NULL)
        return 0;
	else
		return(f(b->lchild)+f(b->rchild)+1);
}

void main()
{
char X;
Btnode *b,*a1,*a2;

//Btnode *p;
//char str[20]="A(B(D(G)),C(E,F))";

//cout<<"原来的树:"<<endl<<"A(B(D(G)),C(E,F))"<<endl;
cout<<"新建立的树:"<<endl;
createBtnode(b,"A(B(D,E(H(J,K(L,M(N))))),C(F,G(I))");
dispbtnode(b);
cout<<endl<<"树的高度:"<<Btnodeheight(b)<<endl;


 cout<<"先根遍历："<<endl;
 preorder(b);cout<<endl;
 cout<<"中根遍历："<<endl;
 inorder(b);cout<<endl;
 cout<<"后根遍历："<<endl;
 postorder(b);cout<<endl;
 cout<<"所有结点的个数："<<f(b)<<endl;
 cout<<"所有的叶子结点:";child(b);cout<<endl;


char a;

cout<<"是否查找结点?(y/n)";
cin>>a;

while(a!='n')
 {
 cout<<"请输入你要查找的结点：";
 cin>>X;
 a1=lchildnode(findnode(b,X)),a2=rchildnode(findnode(b,X));
 if(a1!=NULL)	
	cout<<"左孩子结点："<<a1->data<<endl;
 else 
	 cout<<"没有左孩子结点"<<endl;
 if(a2!=NULL)	
	 cout<<"右孩子结点："<<a2->data<<endl;
 else 
	 cout<<"没有左孩子结点"<<endl;
 }
 Allpath(b);
return;
}