二叉树基本操作的程序实现

1、二叉树基本操作的程序实现作者：nuciewth 阅读人次：43966 文章来源：本站原创发布时间：2007-6-13条原帖及讨论：http:/ 尸0;左中for(i=0;ilen;i+)(Lai=si+1;Lalen=0;/左前for(i=len+1;istrlen(r);i+)(Rbi-len-1=ri;Rbi-len-1=0;for(i=len+1;ilchild,La,Ra);Pre_In_order(&(*t)-rchild,Lb,Rb);else(*t=NULL;intmain()(Bintreet;charpre30=ABCDEF,in30=CBAEDF;/测试数据prin

2、tf(输入前序遍历序列：)；scanf(%s,pre);printf(输入中序遍历序列：);scanf(%s,in);Pre_In_order(&t,pre,in);Posorderl(t);)#include#includetypedefstructnodeintdata;structnode*lchild,*rchild,*next;hufnode;typedefhufnode*linkhuf;/*/*/linkhufCreat_Node(intn)/创建一单链表linkhufhead,pre,p;intx;head=NULL;while(n-)scanf(%d,&x);p

3、=(linkhuf)malloc(sizeof(hufnode);p-data=x;p-lchild=NULL;p-rchild=NULL;if(NULL=head)head=p;pre=head;elsep-next=pre-next;pre-next=p;pre=pre-next;returnhead;/*huffman 树*/linkhufinsert(linkhufroot,linkhufs)/将结点 S 插入到有序(linkhufp1,p2;if(NULL=root)root=s;else(p1=NULL;p2=root;while(p2&p2-datadata)(p1=p2

4、;p2=p2-next;s-next=p2;if(NULL=p1)(root=s;else(p1-next=s;returnroot;voidPreorder1(linkhuft)(if(t!=NULL)(printf(%-6d”,t-data);Preorder1(t-lchild);Preorder1(t-rchild);voidcreathuffman(linkhuf*root)/构造 Huffman 树。(linkhufs,rl,rr;while(*root&(*root)-next)(rl=*root;rr=(*root)-next;*root=rr-next;Huffman

5、root 中。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);intmain()linkhufroot;intn;scanf(%d,&n);root=Creat_Node(n);creathuffman(&root);Preorder1(root);printf(n);return0;/*/*按层次顺序建立一棵二叉树/*/#includeBintree.hB

6、intreeLevel_Creat()Bintreeroot,p,s;queuenode;node.front=node.rear=0;charch;ch=getchar();if(ch=)returnNULL;root=(Binnode*)malloc(sizeof(Binnode);/生成根结点root-data=ch;node.datanode.rear+=root;/用队列实现层次遍历while(node.frontdata=ch;p-lchild=s;node.datanode.rear+=s;else(p-lchild=NULL;ch=getchar();if(ch!=)(s=(Binnode*)malloc(sizeof(Binnode);s-data=ch;p-rchild=s;node.datanode.rear+=s;else