[原创][开源]二叉树基本操作的程序实现.(页 1) - 数据结构与算法 - 编程论坛

nuciewth 发表于 2007-5-5 16:10

[原创][开源]二叉树基本操作的程序实现.

//Bintree.h #include<stdio.h> #include<malloc.h> typedef struct Binnode{//二叉树结点结构体 char data; struct Binnode *lchild; struct Binnode *rchild; }; typedef Binnode *Bintree ;
typedef struct stack{ //二叉树结点栈 Bintree data[100]; int flag[100]; int top; };
typedef struct queue{ //二叉树结点队列 Bintree data[30]; int front; int rear; };
 /*******************************************/ /* 按照前序遍历建立二叉树 */ /*******************************************/
void Creat_Bintree(Bintree *root) { char ch; if((ch=getchar())==' ') { *root=NULL;
 } else { *root=(Binnode*)malloc(sizeof(Binnode)); (*root)->data=ch; Creat_Bintree(&(*root)->lchild); Creat_Bintree(&(*root)->rchild); } }
/*******************************************/ /* 按照前序递归遍历二叉树 */ /*******************************************/
void Preorder1(Bintree t) { if(t!=NULL) { printf("%c",t->data); Preorder1(t->lchild); Preorder1(t->rchild); } }
 /*******************************************/ /* 按照中序递归遍历二叉树 */ /*******************************************/
void Inorder1(Bintree t) { if(t!=NULL) { Inorder1(t->lchild); printf("%c",t->data); Inorder1(t->rchild); } }
/*******************************************/ /* 按照后序递归遍历二叉树 */ /*******************************************/
void Posorder1(Bintree t) { if(t!=NULL) { Posorder1(t->lchild); Posorder1(t->rchild); printf("%c",t->data); } } /*******************************************/ /* 按照前序非递归遍历二叉树 */ /*******************************************/
void Preorder2(Bintree t) { Bintree pre=t; stack s; s.top=0; printf("输出前序遍历序列:"); while(pre||s.top>0) { if(pre) { printf("%c",pre->data); s.data[s.top++]=pre; pre=pre->lchild; } else { pre=s.data[--s.top]->rchild; } } printf("\n\n"); }
/*******************************************/ /* 按照中序非递归遍历二叉树 */ /*******************************************/
void Inorder2(Bintree t) { Bintree pre=t; stack s; s.top=0; printf("输出中序遍历序列:"); while(pre||s.top>0) { if(pre) { s.data[s.top++]=pre; pre=pre->lchild; } else { pre=s.data[--s.top]; printf("%c",pre->data); pre=pre->rchild; } } printf("\n\n"); }
/*******************************************/ /* 按照后序非递归遍历二叉树 */ /*******************************************/
void Posorder2(Bintree t) { stack s; s.top=-1; printf("输出后序遍历序列:"); while(t!=NULL||s.top!=-1) { while(t) { s.top++; s.flag[s.top]=0; s.data[s.top]=t; t=t->lchild; } while(s.top>=0&&s.flag[s.top]==1) { t=s.data[s.top]; printf("%c",t->data); s.top--; } if(s.top>=0) { t=s.data[s.top]; s.flag[s.top]=1; t=t->rchild; } else { t=NULL; } } printf("\n\n"); }
 /*******************************************/ /* 按照层次遍历二叉树 */ /*******************************************/ void Levelorder(Bintree t) { queue q; q.data[0]=t; q.front=0;q.rear=1; printf("层次遍历二叉树结果:"); while(q.front<q.rear) { if(q.data[q.front]) { printf("%c",q.data[q.front]->data); q.data[q.rear++]=q.data[q.front]->lchild; q.data[q.rear++]=q.data[q.front]->rchild; q.front++; } else { q.front++; } } printf("\n\n"); }

nuciewth 发表于 2007-5-5 16:11

#include"Bintree.h" /*******************************************/ /* 递归法将二叉树的左右子树互换 */ /*******************************************/ void Exchange1(Bintree t) { Bintree temp; if(t) { Exchange1(t->lchild); Exchange1(t->rchild); temp=t->lchild; t->lchild=t->rchild; t->rchild=temp; } } /*******************************************/ /* 非递归法将二叉树的左右子树互换 */ /*******************************************/ void Exchange2(Bintree t) { Bintree temp; stack s; s.top=0; while(t||s.top) { if(t) { s.data[s.top++]=t; temp=t->lchild; t->lchild=t->rchild; t->rchild=temp; t=t->lchild; } else { t=s.data[--s.top]->rchild; }
 } } int main() { Bintree t; Creat_Bintree(&t); Exchange2(t); Inorder2(t); return 0; }

nuciewth 发表于 2007-5-5 16:11

#include"Bintree.h" /*******************************************/ /* 递归法求叶子结点个数 */ /*******************************************/ int Leaves_Num1(Bintree t) { if(t) { if(t->lchild==NULL&&t->rchild==NULL) { return 1; } return Leaves_Num1(t->lchild)+Leaves_Num1(t->rchild); } return 0; }
/*******************************************/ /* 非递归法求叶子结点个数 */ /*******************************************/ int Leaves_Num2(Bintree t) { int count=0; stack s; s.top=0; while(t||s.top>0) { if(t) { s.data[s.top++]=t; if(t->lchild==NULL&&t->rchild==NULL) {
 count++; } t=t->lchild; } else { t=s.data[--s.top]->rchild; } } return count; }
 int main() { int count=0; Bintree t; Creat_Bintree(&t); count=Leaves_Num2(t); printf("该二叉树的叶子结点数为:%d\n",count); return 0; }

nuciewth 发表于 2007-5-5 16:11

#include"Bintree.h"
/**********************************************/ /* 求一棵树的高度 */ /**********************************************/
int Depth(Bintree t) { int lh , rh ; if( NULL == t ) { return 0 ; } else { lh = Depth( t->lchild ) ; rh = Depth( t->rchild ) ; return ( lh > rh ? lh : rh ) + 1 ; } }
int main() { Bintree t ; Creat_Bintree( &t ) ; printf( "树的高度是%d\n" , Depth( t ) ) ; return 0 ; }

nuciewth 发表于 2007-5-5 16:13

#include"Bintree.h" /*******************************************************/ /* 已知一课棵二叉树的中序和后序，建立这棵树 */ /*******************************************************/
void In_Pos_order(Bintree *t,char *s,char *r) { char La[30],Lb[30],Ra[30],Rb[30]; int i,len,length=strlen(r); if(length>0&&r[length-1]!='\0') { *t=(Binnode *)malloc(sizeof(Binnode)); (*t)->data=r[length-1]; for(i=0;s[i]!=r[length-1];i++) { Ra[i]=s[i]; La[i]=r[i]; } len=i; Ra[len]='\0'; //左中 La[len]='\0'; //左后 for(i=len+1;i<strlen(s);i++) { Rb[i-len-1]=s[i]; } Rb[i-len-1]='\0'; for(i=len;i<strlen(r)-1;i++) { Lb[i-len]=r[i]; } Lb[i-len]='\0'; In_Pos_order(&(*t)->lchild,Ra,La); In_Pos_order(&(*t)->rchild,Rb,Lb); } else { *t=NULL; } }
int main() { Bintree t; char in[30]="ABCEFGHD",pos[30]="ABFHGEDC";//测试数据 printf("输入中序遍历序列:"); scanf("%s",in); printf("输入后序遍历序列:"); scanf("%s",in); In_Pos_order(&t,in,pos); Preorder2(t); }

nuciewth 发表于 2007-5-5 16:13

#include"Bintree.h" /*******************************************************/ /* 判断两棵是否等价 */ /*******************************************************/
int Is_equal( Bintree t1 , Bintree t2 ) { int t=0; if(NULL == t1 && NULL == t2) { t=1; } else { if(NULL !=t1 &&NULL != t2 ) { if(t1->data == t2->data) { if(Is_equal(t1->lchild,t2->lchild)) { t=Is_equal(t1->rchild,t2->rchild); } } } } return t; } int main() { Bintree t1,t2; Creat_Bintree(&t1); getchar(); Creat_Bintree(&t2); if(Is_equal(t1,t2)) { printf( "Yes!\n") ; } else { printf( "No!\n" ) ; } return 0 ; }

nuciewth 发表于 2007-5-5 16:15

#include"Bintree.h" /****************************************************/ /* 查找某个信息是否在这棵树中 */ /****************************************************/
Bintree locale_x(Bintree t,char x) { Bintree p; if(t==NULL) return NULL; else { if( t -> data == x ) return t; else { p = locale_x(t->lchild,x); if(p)return p; else return locale_x(t->rchild,x); } } }
int main() { Bintree root,p; char ch; Creat_Bintree(&root); getchar(); printf("输入要查找的值:"); scanf("%c",&ch); p=locale_x(root,ch); if(p)printf( "YES!\n" ) ; else printf( "NO!\n" ) ; return 0; }

nuciewth 发表于 2007-5-5 16:16

#include"Bintree.h"
/****************************************************/ /* 树的结点个数 */ /****************************************************/ int num_of_node(Bintree t) { if(t==NULL)return 0 ; else return num_of_node(t->lchild)+num_of_node(t->rchild)+1; }
 int main() { Bintree root,p; Creat_Bintree(&root); printf("%d\n",num_of_node(root)); return 0; }

nuciewth 发表于 2007-5-5 16:17

#include"Bintree.h"
/*******************************************************/ /* 已知一课棵二叉树的中序和前序序列，建立这棵树 */ /*******************************************************/
void Pre_In_order(Bintree *t,char *s,char *r) { char La[30],Lb[30],Ra[30],Rb[30]; int i,len; if(s[0]!='\0') { *t=(Binnode *)malloc(sizeof(Binnode)); (*t)->data=s[0]; for(i=0;r[i]!=s[0];i++) { Ra[i]=r[i]; } len=i; Ra[len]='\0'; //左中 for(i=0;i<len;i++) { La[i]=s[i+1]; } La[len]='\0'; //左前 for(i=len+1;i<strlen(r);i++) { Rb[i-len-1]=r[i]; } Rb[i-len-1]='\0'; for(i=len+1;i<strlen(s);i++) { Lb[i-len-1]=s[i]; } Lb[i-len-1]='\0'; Pre_In_order(&(*t)->lchild,La,Ra); Pre_In_order(&(*t)->rchild,Lb,Rb); } else { *t=NULL; } }
int main() { Bintree t; char pre[30]="ABCDEF",in[30]="CBAEDF";//测试数据 printf("输入前序遍历序列:"); scanf("%s",pre); printf("输入中序遍历序列:"); scanf("%s",in); Pre_In_order(&t,pre,in); Posorder1(t); }

nuciewth 发表于 2007-5-5 16:19

#include<stdio.h> #include<malloc.h> typedef struct node{ int data; struct node *lchild,*rchild,*next; }hufnode;
typedef hufnode *linkhuf; /****************************************************/ /* huffman树 */ /****************************************************/ linkhuf Creat_Node(int n) //创建一单链表 { linkhuf head,pre,p; int x; head=NULL; while(n--) { scanf("%d",&x); p=(linkhuf)malloc(sizeof(hufnode)); p->data=x; p->lchild=NULL; p->rchild=NULL; if(NULL==head) { head=p; pre=head; } else { p->next=pre->next; pre->next=p; pre=pre->next; } } return head; } linkhuf insert(linkhuf root , linkhuf s)//将结点S插入到有序Huffman root中。 { linkhuf p1,p2; if(NULL == root ) root=s; else { p1=NULL; p2=root; while(p2&&p2->data<s->data) { p1=p2; p2=p2->next; } s->next=p2; if(NULL==p1) { root=s; } else { p1->next=s; } } return root; }
 void Preorder1(linkhuf t) { if(t!=NULL) { printf("%-6d",t->data); Preorder1(t->lchild); Preorder1(t->rchild); } } void creathuffman(linkhuf *root)//构造Huffman树。 { linkhuf s, rl,rr; while(*root && (*root)->next) { rl=*root; rr=(*root)->next; *root=rr->next; s=(linkhuf)malloc(sizeof(hufnode)); s->next=NULL; s->data=rl->data+rr->data; s->lchild=rl; s->rchild=rr; rl->next=rr->next=NULL; *root=insert(*root,s); } }
int main() { linkhuf root; int n; scanf("%d",&n); root=Creat_Node(n); creathuffman(&root); Preorder1(root); printf("\n"); return 0; }

fyi1106 发表于 2007-5-5 16:26

我顶，虽然我没看，但实在感动楼主的用苦良心，我们做数据结构实验时就写了这些，写得好烦呀，楼主早贴出来该多好。

lishiyong110 发表于 2007-5-5 22:48

看了一些特别是非递归形式非常好非常感谢

kongbei 发表于 2007-5-7 08:52

写得很好呀！！！

nuciewth 发表于 2007-5-12 20:04

/************************************************************/ /* 按层次顺序建立一棵二叉树 */ /************************************************************/ #include"Bintree.h"
Bintree Level_Creat() { Bintree root,p,s; queue node; node.front=node.rear=0; char ch; ch=getchar(); if(ch==' ') { return NULL; } root=(Binnode*)malloc(sizeof(Binnode)); //生成根结点 root->data=ch; node.data[node.rear++]=root; //用队列实现层次遍历 while(node.front<node.rear) { p=node.data[node.front++]; ch=getchar(); //为了简化操作，分别对左右子结点进行赋值。 if(ch!=' ')//子树不空则进队列进行扩充。下同 { s=(Binnode*)malloc(sizeof(Binnode)); s->data=ch; p->lchild=s; node.data[node.rear++]=s; } else { p->lchild=NULL; } ch=getchar(); if(ch!=' ') { s=(Binnode*)malloc(sizeof(Binnode)); s->data=ch; p->rchild=s; node.data[node.rear++]=s; } else { p->rchild=NULL; } } return root; } int main() { Bintree root; root=Level_Creat(); Inorder1(root);//测试，中序遍历 return 0; }

Gislover 发表于 2007-5-15 10:21

[em17]

yuesheng 发表于 2007-5-15 11:46

接受了你的算法思想，谢谢了啊，不过问下，递归建树，为什么要用指针的指针？不能直接用指针啊？

nuciewth 发表于 2007-5-15 12:32

对结点本身是个指针.如果你要修改根结点,那就得用指针的指针才可以保存修改.

yuji512512 发表于 2007-5-16 08:46

楼主写的很好，前几个看懂了，后几个不是太明白

yuesheng 发表于 2007-5-20 21:52

问下楼主，比较复杂的程序是怎样想到怎么做的？看的懂，但是自己通常编不出来

nuciewth 发表于 2007-5-21 21:51

练多了就可以了.有些经典的算法可以去背,不过我记性差点,至今没背好. 熟能生巧.呵呵.

页: [1] 2

编程论坛's Archiver

[原创][开源]二叉树基本操作的程序实现.