树和二叉树程序.docx

《树和二叉树程序.docx》由会员分享，可在线阅读，更多相关《树和二叉树程序.docx（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、树和二叉树常用算法创建二叉树 struct node char data; struct node *lchild,*rchild; ; void precreate(struct node *T) /先序、中序、后序递归建树遍历二叉树 void inorder(struct node *p)/中序遍历 if(p!=NULL) inorder(p-lchild); printf(%c ,p-data); inorder(p-rchild); 统计二叉树中叶子节点数 int leaf(NODE *t) if(t=NULL) return(0);else if(t-lchild=NULL&t-rc

2、hild=NULL) return(leaf(t-lchild)+leaf(t-rchild)+1);elsereturn(leaf(t-lchild)+leaf(t-rchild);统计二叉树中度为1的节点数 int num=0;void count(NODE *p) if(p!=NULL)count(p-lchild);if(p-lchild!=NULL&p-rchild=NULL|p-lchild=NULL&p-rchild!=NULL)num+;count(p-rchild);统计二叉树度为1的结点数方法2 int onechild(NODE *t) int num1,num2;if(

3、t=NULL) return(0);else if(t-lchild=NULL&t-rchild!=NULL|t-lchild!=NULL&t-rchild=NULL)return(onechild(t-lchild)+onechild(t-rchild)+1);elsenum1=onechild(t-lchild);num2=onechild(t-rchild);return(num1+num2);非递归统计出二叉树共有多少个度为1的结点 int onechild3(NODE *root) NODE *p,*s100;int top=0,num=0; /top为栈顶指针p=root;whil

4、e(p!=NULL)|(top0) while(p!=NULL)if(p-lchild!=NULL&p-rchild=NULL |p-lchild=NULL&p-rchild!=NULL)num+;s+top=p; p=p-lchild; p=stop-; p=p-rchild; return num;统计二叉树中所有节点数 int sum(NODE *t) if(t=NULL) return(0);else return(sum(t-lchild)+sum(t-rchild)+1);非递归二叉树前序遍历 Status PreOrderTraverse(BiTree T)Stack S;Ini

5、tStack(S);p=T;While(p|!StackEmpty(S)if(p) Visit(p-data);Push(S,p);p=p-lchild;elsePop(S,p);p=p-rchild;return SUCCESS;非递归二叉树中序遍历 Status InOrderTraveser(BiTree T)Stack S;InitStack(S);p=T;While(p|!StackEmpty(S)if(p)Push(S,p);p=p-lchild;else Pop(S,p);Visit(p-data);p=p-rchild;return SUCCESS非递归二叉树后序遍历 Stat

6、us PostOrder(BiTree T)Stack S1,S2;InitStack(S1);InitStack(S2);While(p|!StackEmpty(S1)if(p)Push(S1,p);Push(S2,LEFT);p=p-lchild;elsePop(S1,p);Pop(S2,tag);While(tag=RIGHT)Visit(p-data);Pop(S1,p);Pop(S2,tag);Push(S1,p);Push(S2,RIGHT);P=p-rchild;return SUCCESS;先序全线索二叉树的遍历算法 Status PreOrderTraverseThrTree

7、(ThreadTree &T)p=T-lchild;while(p!=T)while(!p-ltag) p=p-lchild;Visit(p-data); While(p-rtag&p!=T)p=p-rchild;Viste(p-data);p=p-rchild;return SUCCESS;二叉树的层次遍历算法 void LevelTraverse(BiTree T)Queue Q;InitQueue(Q);EnQue(Q,T);while(!Queue(Empty)DeQue(Q,q);printf(%c,q-data);if(q-lchild) EnQue(Q,q-lchild);if(

8、q-rchild) EnQue(Q,q-rchild);return SUCCESS;删去并释放数据值为k的叶结点 void delk(NODE *root,char k) NODE *p,*s100,*q; /q为p的双亲结点int top=0; /top为栈顶指针if(*root)=NULL)return;if(*root)-lchild=NULL &(*root)-rchild=NULL&(*root)-data=k) *root=NULL;return;p=*root;q=p;while(p!=NULL)|(top0) while(p!=NULL)if(p-lchild=NULL&p-

9、rchild=NULL &p-data=k)if(q-lchild=p) q-lchild=NULL;else q-rchild=NULL; free(p);return;s+top=p; q=p; p=p-lchild; p=stop-; q=p;p=p-rchild; 按层次从上到下,每层从右到左的顺序列出二叉树所有结点的数据信息 void lev_traverse(NODE *TNODE *q100,*p;int head,tail;q0=T;head=0;tail=1;while(headdata);if(p-rchild!=NULL)qtail+=p-rchild;if(p-lchi

10、ld!=NULL)qtail+=p-lchild;求二叉树的深度 int depth(NODE *t) int num1,num2;if(t=NULL) return(0);if(t-lchild =NULL&t-rchild =NULL) return(1);elsenum1=depth(t-lchild );num2=depth(t-rchild );if(num1num2)return(num1+1);elsereturn(num2+1);判定两棵二叉树是否相似 int like(NODE *t1,NODE *t2) int like1,like2;if(t1=t2&t2=NULL) r

11、eturn(1);else if(t1=NULL &t2!=NULL|t1!=NULL&t2=NULL) return(0);elselike1=like(t1-lchild,t2-lchild);like2=like(t1-rchild ,t2-rchild );return(like1&like2);将二叉树的链接存储转换为顺序存储 char a100; /数组顺序存储二叉树void change(NODE *t,int i) if(t!=NULL) ai=t-data;change(t-lchild,2*i);change(t-rchild,2*i+1);判断二叉树是否为完全二叉树 int complete(NODE *t) int i,flag=0;change(t,1);for(i=1;i100;i+)if(!flag&ai=0) flag=1;if(flag&ai!=0) break;if(i=100) return(1);else return(0);