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 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("");}
按照中序非递归遍历二叉树
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("");}
/* 按照后序非递归遍历二叉树 */
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("");
}
按照层次遍历二叉树 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("");}
/* 递归法将二叉树的左右子树互换 */
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;}
/* 递归法求叶子结点个数 */
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",count); return 0;}
/* 求一棵树的高度 */
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" , Depth( t ) ) ; return 0 ;}
/* 判断两棵是否等价 */
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!") ; }else printf( "No!" ) ; }return 0 ;
}
/* 查找某个信息是否在这棵树中 */
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; elsereturn 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!" ) ; else printf( "NO!" ) ; return 0;
} 树的结点个数
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",num_of_node(root)); return 0;}
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);}
int main(){ linkhuf root; int n; scanf("%d",&n); root=Creat_Node(n); creathuffman(&root); Preorder1(root); printf("");return 0;}
int main(){Bintree root; root=Level_Creat();Inorder1(root);//测试，中序遍历 return 0;}
评论10