树、二叉树的基本操作（数据结构)

1）二叉树的基本操作
（1）给出一棵二叉树，采用二叉链表存储结构，从键盘读入节点字符，序建立二叉树（例如，ABD#G###CE##FH###）
（2）分别采用递归或非递归算法，实现对该二叉树的先序、中序和后序遍历等基本操作，输出遍历结果。
（3）实现层次遍历二叉树并输出遍历序列。
2）二叉树的应用
（1）修改遍历算法，求出二叉树的结点总数和叶子结点数，输出结果。
（2）交换二叉树的左右子树。
（3）选作题：编写判定二叉树是否是完全二叉树的算法，再编程实现该算法。
（4）选作题： 编程实现哈夫曼树的构造算法。
3）选作题：树的存储结构及基本操作
采用双亲表示法存储一棵树，编程实现下列功能
①构造该树
②求某结点的双亲结点和所有孩子结点。

#include "stdio.h"
#include "string.h"
#include
#include
#include
#define MAXQSIZE 100
typedef char TElemType ;
typedef struct BiNode
{
TElemType data;
struct BiNode * lchild ,* rchild;
}BiNode ,*BiTree;

typedef struct{
    struct BiNode *base[100];
    int front,rear;
}SqQueue;

typedef struct{
    struct BiNode *base[100];
    int top;
}Sstack;

typedef struct{
	TElemType data;
	int parent;
	 
	} Pnode;
	typedef struct{
Pnode node[MAXQSIZE];
int length;
	}Tree;
	typedef struct{
	Pnode node[MAXQSIZE];
	int front;
	int rear;	
}que;
	typedef struct{
		char data;
		int weight;
		int parent;
		int lchild;
		int rchild;
}HTNode,HuffmanTree;
	typedef struct{
			char code[10];
			int start;
			}Hfcode;
	typedef struct{
	char code[1000];
	int length;		
		}Hcode;
		HuffmanTree Ht[1000];
		Hfcode hcode[1000];

		
	

void inorder(BiTree T)   
{   Sstack s;
    s.top=0;
    BiTree p;
     p=T;
    while(p!=NULL || s.top!=0)
	{   
		if (p!=NULL)
		{	s.base[s.top]=p; 
		    s.top =s.top+1;
             p=p->lchild; 
         }  
       else   
         {  s.top =s.top-1;
		     p=s.base[s.top];  
             printf("%c",p->data);
               p=p->rchild; 
           } 
    } 
} 




void LevelOrderTraverse(BiTree T)
{  BiTree p;
    SqQueue Q;
    Q.rear=Q.front=0;
    if (T)
	{ Q.base[Q.rear]=T;
        Q.rear=(Q.rear+1)%MAXQSIZE;

    while (Q.front !=Q.rear)
        {
		   p=Q.base[Q.front];
		   printf("%c",p->data);
		   Q.front=(Q.front+1)%MAXQSIZE;
		   if(p->lchild){
		   	Q.base[Q.rear]=p->lchild;
		   	Q.rear=(Q.rear+1)%MAXQSIZE;
		   	
		   }
		   if(p->rchild){
		   	Q.base[Q.rear]=p->rchild;
		   	Q.rear=(Q.rear+1)%MAXQSIZE;
		   }
	   } 
	}
}

BiTree CreateBiTree(BiTree bt)
{       char ch;
	BiTree h=NULL;
	ch=getch();
	if(ch=='#') bt=NULL;
    else
	   {
     if((bt=(BiNode *)malloc(sizeof(BiNode)))==NULL)
		return NULL;
	  bt->data=ch;
	  printf("n构造%C的左子树n",ch);
	  bt->lchild=CreateBiTree(h);
	   printf("n构造%C的右子树n",ch);
	  bt->rchild=CreateBiTree(h);
 	}
	return(bt);
}
void PreOrderTraverse(BiTree  bt)
            {   if (bt)
		 {   printf("%c",bt->data);
                      PreOrderTraverse(bt->lchild);
                      PreOrderTraverse(bt->rchild);
                 }
            }

void InOrderTraverse(BiTree  bt)
{
   if(bt){
   	InOrderTraverse(bt->lchild);
   	printf("%c",bt->data);
   		InOrderTraverse(bt->rchild);
   } 
}
void PostOrderTraverse(BiTree  bt)
{
   if(bt){
   	PostOrderTraverse(bt->lchild);
   		PostOrderTraverse(bt->rchild);
   		printf("%c",bt->data);
   }
}

void MenuList() 
{   
  printf("nnn**************************************************n");
  printf("**************** 二叉树的生成和遍历实验***********n");
  printf("**** 1  -------生成二叉树                     ****n");
  printf("**** 2  -------先序遍历二叉树(含递归和非递归）****n");
  printf("**** 3  -------中序遍历二叉树(含递归和非递归）****n");
  printf("**** 4  -------后序遍历二叉树(含递归和非递归）****n");
  printf("**** 5  -------层次遍历                       ****n");
 
  printf("**** 6  ------非递归中序遍历    ****n");
  printf("**** 7  ------二叉树的结点总数和叶子结点数    ****n");
  printf("**** 8  ------交换二叉树的左右子树            ****n");
  printf("**** 9 -----判断一棵树是否为完全二叉树        ****n");
  printf("**** 10 -----采用双亲表示法构造棵树           ****n");
  printf("**** 11 -----求某结点的双亲结点               ****n");
  printf("**** 12-----求某结点的所有孩子结点            ****n");
  printf("**** 13-----实现哈夫曼树的构造算法            ****n");
  printf("**** 0  -------结束运行                       ****n") ; 
  printf("**************************************************n");
}
void Traversecount(BiTree T,int &count,int &count_leaf)
{
if(T){
	count++;
	if(T->lchild==NULL&&T->rchild==NULL){
		count_leaf+=1;
	}
	 Traversecount(T->lchild,count,count_leaf);
	  Traversecount(T->rchild,count,count_leaf);
}
}
void change_left_right(BiTree T)
{  //操作结果：交换二叉树T的左右子树
BiNode * p; 
	if (T) 
   {   change_left_right(T->lchild);
       change_left_right(T->rchild);
      p=T->lchild;
	  T->lchild=T->rchild;
	  T->rchild=p;
    } }

int fullbitree(BiTree T){
	if(!T){
		return 0;
	}
	if((T->lchild==NULL&&T->rchild==NULL)||(T->lchild&&T->rchild==NULL)){
		return 1;
	}
	return fullbitree(T->lchild)&fullbitree(T->rchild);
}

//
void safe_flush(FILE *fp){
	int ch;
	while((ch=fgetc(fp))!=EOF&&ch!='n');
}
//构造双亲表示法的树
void createtree(Tree &tree){
	char ch;
	int i,j,k;
	printf("请输入入数的结点个数：n");
	scanf("%d",&k);
	tree.length=k;
	printf("请输入树中结点的字符型值，需第一个输入根节点n");
	for(i=0;i
		printf("请输入第%d个节点的值：",i+1);
		safe_flush(stdin);
		scanf("%c",&ch);
		tree.node[i].data=ch;
		
	}
	tree.node[0].parent=-1;//根节点的双亲下标设为1
	printf("请输入结点的双亲存储位置下标n") ;
	for(i=1;i
		printf("请输入第%d个结点的双亲下标：",i+1);
		scanf("%d",&j);
		tree.node[i].parent=j; 
			}
} 
void parent_find(Tree tree){
	char ch;
	int i,j;
	printf("请输入要查找的双亲的结点：n");
	safe_flush(stdin);
	scanf("%c",&ch);
	for(i=0;i
		if(tree.node[i].data==ch)
		break;
	}
	if(i>=tree.length){
		printf("树中不存在值为%c的结点，查找失败n",ch);
		
	}
	j=tree.node[i].parent;
	if(j==-1){
		printf("%c是根结点，没有双亲",tree.node[i].data);
	}
	else
	printf("%c的双亲为%c n",ch,tree.node[j].data); 
}
//查找某结点的所有孩子
void child_find(Tree tree){
	int i,j=0,k;
	char ch;
	printf("请输入你要找的所有孩子的节点值：n");
	safe_flush(stdin);
	scanf("%c",&ch);
	for(i=0;i
		if(tree.node[i].data==ch){
			break;
		}
	}
	k=i;
	if(k>=tree.length){
		printf("树中不存在值为%c的结点，查找失败",ch);
		printf("n");
	}
	for(i=0;i
		if(tree.node[i].parent==k){
			j++;
			printf("%c的第%d个孩子是：%cn",ch,j,tree.node[i].data);
		}
	}
	if(j==0)
	printf("%c没有孩子结点！",ch);
} 

//实现哈夫曼树的构造算法
void HmTree(HuffmanTree Ht[],int w[],char a[],int n){
		//w存放n个字符的权值，均大于0
		int m,i,j,min1,min2,s1,s2;
		if(n<=1){
			return;
		}
		m=2*n-1;
		for(i=0;i<=n;i++){
			Ht[i].weight=w[i-1];
			 Ht[i].data=a[i-1];
			 Ht[i].parent=0;
			 Ht[i].lchild=0;
			 Ht[i].rchild=0;
		}
		for(;i<=m;++i){
			Ht[i].weight=0;
			Ht[i].data='#';
			Ht[i].parent=0;
			Ht[i].lchild=0;
			Ht[i].rchild=0;
		}
		for(i=n+1;i<=m;i++){
			//创建哈夫曼树
			s1=0;
			s2=0;
			min1=0;
			for(j=0;j<=i-1;j++){
				if(Ht[j].parent==0)
				if(Ht[j].weight
				min1=Ht[j].weight;
				s1=j;
					
				}
			}
				min2=0;
				for(j=0;j<=i-1;j++){
					if(Ht[j].parent==0&&j!=s1)
					if(min2==0||Ht[j].weight
						min2=Ht[j].weight;
						s2=j;
						
					}
				}
				//
				Ht[i].weight=Ht[s1].weight+Ht[s2].weight;
				Ht[s1].parent=i;
				Ht[s2].parent=i;
				Ht[i].lchild=s1;
				Ht[i].rchild=s2;
			} 
		}
		

int main()
{
   BiTree T;
  	int i=100;
  	int count=0,count_leaf=0;
	MenuList();
	Tree tree;
	int m;
	int n,w[100];
	char a[20];
	
   while(i!=0)
	{
		printf("请输入选择:");
	    scanf("%d" ,&i);
  	if (i==1)
	{	printf("请输入二叉树的先序遍历序列，#代表空树:");
		T=CreateBiTree(NULL);
    }
	if (i==2)
	{
	   printf("先序递归遍历二叉树：");
	    PreOrderTraverse(T);
         printf("n") ;
		}
  
	if (i==3)
	{  printf("中序递归遍历二叉树：");
InOrderTraverse(T); 
	 printf("n") ;
			}
     
	if (i==4)
	{	 printf("后序递归遍历二叉树：");
			 PostOrderTraverse(T); 
	 printf("n") ;
			}

    if (i==5)
	{printf("层次递归遍历二叉树：");
		LevelOrderTraverse(T); 
			 printf("n") ;
			}

   if (i==6)
	{printf("中序非递归遍历二叉树：");
		inorder(T);
			 printf("n") ; 
	
		}

if (i==7)
{  
	 Traversecount(T,count,count_leaf);
printf("二叉树的结点总数为%dn",count);
 
	 printf("二叉树的叶子结点总数为%dn",count_leaf);
 printf("n") ; 

		}
if (i==8)
{  printf("交换二叉树的左右子树n");
	change_left_right(T);
 printf("n") ; 

		}
		if (i==9)
{  printf("判断一棵树是否为完全二叉树  n");
int a= fullbitree(T);
if(a==1)
printf("是完全二叉树");
if(a==0) 
printf("不是完全二叉树"); 
 printf("n") ; 

		}
		if(i==10){
			createtree(tree);
		}
		if(i==11){
		parent_find(tree);	
		} 
		if(i==12){
		child_find(tree);
		}
		if(i==13){
			printf("请输入权值个数(小于20)：n");
			scanf("%d",&n);
			printf("请输入%d个权值：n",n);
			for(i=0;i
				scanf("%d",&w[i]);
				safe_flush(stdin);
				printf("请输入%d个权值对应的字符：",n);
				for(i=0;i
					a[i]=getchar();
					HmTree(Ht,w,a,n);
					
				}
			}
			
		}
		
		
    }

}