资源描述：
《树和二叉树程序.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、树和二叉树常用算法创建二叉树•structnode•{chardata;•structnode*lchild,*rchild;•};•voidprecreate(structnode*T)•{}//先序、中序、后序递归建树遍历二叉树•voidinorder(structnode*p)//中序遍历•{•if(p!=NULL)•{inorder(p->lchild);•printf("%c",p->data);•inorder(p->rchild);•}•}统计二叉树中叶子节点数•intleaf(N
2、ODE*t){if(t==NULL)return(0);elseif(t->lchild==NULL&&t->rchild==NULL)return(leaf(t->lchild)+leaf(t->rchild)+1);elsereturn(leaf(t->lchild)+leaf(t->rchild));}统计二叉树中度为1的节点数•intnum=0;voidcount(NODE*p){if(p!=NULL){count(p->lchild);if(p->lchild!=NULL&&p->rc
3、hild==NULL
4、
5、p->lchild==NULL&&p->rchild!=NULL)num++;count(p->rchild);}}统计二叉树度为1的结点数方法2•intonechild(NODE*t){intnum1,num2;if(t==NULL)return(0);elseif(t->lchild==NULL&&t->rchild!=NULL
6、
7、t->lchild!=NULL&&t->rchild==NULL)return(onechild(t->lchild)+onechild(
8、t->rchild)+1);else{num1=onechild(t->lchild);num2=onechild(t->rchild);return(num1+num2);}}非递归统计出二叉树共有多少个度为1的结点•intonechild3(NODE*root){NODE*p,*s[100];inttop=0,num=0;//top为栈顶指针p=root;while((p!=NULL)
9、
10、(top>0)){while(p!=NULL){if(p->lchild!=NULL&&p->rchil
11、d==NULL
12、
13、p->lchild==NULL&&p->rchild!=NULL)num++;s[++top]=p;p=p->lchild;}p=s[top--];p=p->rchild;}returnnum;}统计二叉树中所有节点数•intsum(NODE*t){if(t==NULL)return(0);elsereturn(sum(t->lchild)+sum(t->rchild)+1);}非递归二叉树前序遍历•StatusPreOrderTraverse(BiTreeT){ StackS
14、; InitStack(S); p=T; While(p
15、
16、!StackEmpty(S)) { if(p){Visit(p->data);Push(S,p);p=p->lchild;} else{Pop(S,p);p=p->rchild;} } returnSUCCESS;}非递归二叉树中序遍历•StatusInOrderTraveser(BiTreeT){ StackS; InitStack(S); p=T; While(p
17、
18、!StackEmpty(S)) { if(p){Push(S
19、,p);p=p->lchild;} else{Pop(S,p);Visit(p->data);p=p->rchild;} } returnSUCCESS}非递归二叉树后序遍历•StatusPostOrder(BiTreeT){ StackS1,S2; InitStack(S1);InitStack(S2); While(p
20、
21、!StackEmpty(S1)) { if(p){Push(S1,p);Push(S2,LEFT);p=p->lchild;} else{ Pop(S1,p);P
22、op(S2,tag); While(tag==RIGHT){Visit(p->data);Pop(S1,p);Pop(S2,tag);} Push(S1,p); Push(S2,RIGHT); P=p->rchild; } } returnSUCCESS;}先序全线索二叉树的遍历算法•StatusPreOrderTraverseThrTree(ThreadTree&T){ p=T->lchild; while(p!=T) { while(!p->ltag)p=p->lchil
