二叉樹大全

2019-11-10 20:30:11

字體：大中小

來源：轉載

供稿：網友

#include <stdio.h>#include <string.h>#include <stdlib.h>struct tree{ int data; struct tree *lchild, *rchild;};int i, flag;void BinarySortTreeCreat(struct tree *&t,int a);void BInarySortTreeCompare(struct tree *t1, struct tree *t2);void PReCreat(struct tree *&t,char *pre, int len);///need i = 0void PreinCreat(struct tree *&t,char *pre, char *in, int len);void InpostCreat(struct tree *&t,char *in, char *post, int len);void CengciOrder(struct tree *t);void PreOrder(struct tree *t);void InOrder(struct tree *t);void PostOrder(struct tree *t);int LeafCount(struct tree *t);void LeafOrder(struct tree *t);///up to down,left to rightint TreeHeight(struct tree *t);int main(){ int T, len, cnt, m, num[101]; struct tree *t; char pre[51], in[51], post[51]; while(~scanf("%d",&T)) { t = NULL; for(int j = 0; j < T; j++) { scanf("%d",&num[j]); BinarySortTreeCreat(t, num[j]); } flag = 0; PostOrder(t); printf("/n"); } return 0;}void BinarySortTreeCreat(struct tree *&t,int a){ if(t == NULL) { t = (struct tree *)malloc(sizeof(struct tree)); t->data = a; t->lchild = NULL; t->rchild = NULL; } else { if(a > t->data) BinarySortTreeCreat(t->rchild, a); else BinarySortTreeCreat(t->lchild, a); }}void BInarySortTreeCompare(struct tree *t1, struct tree *t2){ if(t1 == NULL&&t2 == NULL) return ; if(t1||t2) { if(t1->data!=t2->data) { flag = 1; return ; } BInarySortTreeCompare(t1->lchild, t2->lchild); BInarySortTreeCompare(t1->rchild, t2->rchild); }}void PreCreat(struct tree *&t,char *pre, int len){ if(len == 0) return ; if(pre[i] == ',') { t = NULL; i++; } else { t = (struct tree *)malloc(sizeof(struct tree)); t->data = pre[i++]; PreCreat(t->lchild, pre, len); PreCreat(t->rchild, pre, len); }}void PreinCreat(struct tree *&t,char *pre, char *in, int len){ if(len <= 0) t = NULL; else { int a = strchr(in, pre[0]) - in; t = (struct tree *)malloc(sizeof(struct tree)); t->data = pre[0]; PreinCreat(t->lchild, pre+1,in,a); PreinCreat(t->rchild,pre+a+1,in+a+1,len-a-1); }}void InpostCreat(struct tree *&t,char *in, char *post, int len){ if(len <= 0) t = NULL; else { int a = strchr(in, post[len-1]) - in; t = (struct tree *)malloc(sizeof(struct tree)); t->data = post[len-1]; InpostCreat(t->lchild,in,post,a); InpostCreat(t->rchild,in+a+1,post+a,len-1-a); }}void CengciOrder(struct tree *t){ struct tree *q[55], *p; int head=0, tail=0; q[tail++]=t; if(!t) return ; while(head < tail) { p=q[head++]; printf("%c",p->data); if(p->lchild) q[tail++]=p->lchild; if(p->rchild) q[tail++]=p->rchild; }}void PreOrder(struct tree *t){ if(t!=NULL) { printf("%c",t->data); PreOrder(t->lchild); PreOrder(t->rchild); }}void InOrder(struct tree *t){ if(t!=NULL) { InOrder(t->lchild); printf(flag==0?"%d":" %d",t->data); flag++; InOrder(t->rchild); }}void PostOrder(struct tree *t){ if(t!=NULL) { PostOrder(t->lchild); PostOrder(t->rchild); printf(flag==0?"%d":" %d",t->data); flag++; }}int LeafCount(struct tree *t){ if(t == NULL) return 0; if(t->lchild==NULL&&t->rchild==NULL) return 1; return LeafCount(t->lchild)+LeafCount(t->rchild);}void LeafOrder(struct tree *t){ struct tree *q[55], *p; int head=0, tail=0; q[tail++]=t; if(!t) return ; while(head < tail) { p=q[head++]; if(p->lchild==NULL&&p->rchild==NULL) printf("%c",p->data); if(p->lchild) q[tail++]=p->lchild; if(p->rchild) q[tail++]=p->rchild; }}int TreeHeight(struct tree *t){ int lh=0,rh=0; if(t==NULL) return 0; if(t->lchild!=NULL) lh=TreeHeight(t->lchild); else lh=0; if(t->rchild!=NULL) rh=TreeHeight(t->rchild); else rh=0; return (rh>lh)?rh+1:lh+1;}

上一篇：寄存器詳解

下一篇：數組（二）：ArrayList的實現和Arrays類的使用