最最最基本的-树的操作
目录
树的建立
先序建立二叉树
先序+中序建立二叉树
后序+中序建立二叉树
树的遍历
递归遍历
先序遍历
中序遍历
后序遍历
非递归遍历
先序遍历
中序遍历
后序遍历
层次遍历
求叶子节点个数
完整代码
树的建立
先序建立二叉树
BTree * PreCreateBTree()
{BTree *T;int elem;scanf("%d",&elem);if(elem==0){T=NULL;}else{T=(BTree*)malloc(sizeof(BTree));T->elem=elem;T->lchild=PreCreateBTree();T->rchild=PreCreateBTree();}return T;
}先序+中序建立二叉树
BTree * Pre_Mid_CreateBTree(ElemType * Pre,ElemType *Mid,int n)//前序+中序建立二叉树
{BTree *root=(BTree*)malloc(sizeof(BTree));root->elem=Pre[0];root->lchild=root->rchild=NULL;int i;int j;for(i=0;i<n;i++){if(Mid[i]==root->elem)break;} if(i>0){ElemType*LSubPre=(ElemType*)malloc(i*sizeof(ElemType));ElemType*LSubMid=(ElemType*)malloc(i*sizeof(ElemType));for(j=0;j<i;j++){LSubPre[j]=Pre[j+1];}for(j=0;j<i;j++){LSubMid[j]=Mid[j];} root->lchild=Pre_Mid_CreateBTree(LSubPre,LSubMid,i);ElemType*RSubPre=(ElemType*)malloc(i*sizeof(ElemType));ElemType*RSubMid=(ElemType*)malloc(i*sizeof(ElemType));for(j=0;j<i;j++){RSubPre[j]=Pre[j+i+1];}for(j=0;j<i;j++){RSubMid[j]=Mid[j+i+1];} root->rchild=Pre_Mid_CreateBTree(RSubPre,RSubMid,i);}return root;
}后序+中序建立二叉树
BTree * Post_Mid_CreateBTree(ElemType * Post,ElemType *Mid,int n)//后序+中序建立二叉树
{BTree *root=(BTree*)malloc(sizeof(BTree));root->elem=Post[n-1];root->lchild=root->rchild=NULL;int i;int j;for(i=0;i<n;i++){if(Mid[i]==root->elem)break;} if(i>0){ElemType*LSubPost=(ElemType*)malloc(i*sizeof(ElemType));ElemType*LSubMid=(ElemType*)malloc(i*sizeof(ElemType));for(j=0;j<i;j++){LSubPost[j]=Post[j];}for(j=0;j<i;j++){LSubMid[j]=Mid[j];} root->lchild=Post_Mid_CreateBTree(LSubPost,LSubMid,i);ElemType*RSubPost=(ElemType*)malloc(i*sizeof(ElemType));ElemType*RSubMid=(ElemType*)malloc(i*sizeof(ElemType));for(j=0;j<i;j++){RSubPost[j]=Post[j+i];}for(j=0;j<i;j++){RSubMid[j]=Mid[j+i+1];} root->rchild=Post_Mid_CreateBTree(RSubPost,RSubMid,i);}return root;
}树的遍历
递归遍历
先序遍历
void PrePrintBTree(BTree *T)
{if(T){printf("%d",T->elem);PrePrintBTree(T->lchild);PrePrintBTree(T->rchild);}
}
中序遍历
void MidPrintBTree(BTree *T)
{if(T){MidPrintBTree(T->lchild);printf("%d",T->elem);MidPrintBTree(T->rchild);}
}
后序遍历
void PostPrintBTree(BTree *T)
{if(T){PostPrintBTree(T->lchild);PostPrintBTree(T->rchild);printf("%d",T->elem);}
}
非递归遍历
先序遍历
void PrintBTreePre(BTree *T)
{Stack S;S.top=-1;while(T || S.top!=-1){while(T){printf("%d",T->elem);Push(&S,T);T=T->lchild;}if(S.top!=-1){T=Pop(&S);T=T->rchild;}}
}
中序遍历
void PrintBTreeMid(BTree *T)
{Stack S;S.top=-1;while(T || S.top>-1){while(T){Push(&S,T);T=T->lchild;}if(S.top!=-1){T=Pop(&S);printf("%d",T->elem);T=T->rchild;}}
}
后序遍历
void PrintBTreePost(BTree *T)
{Stack S;S.top=-1;while(T || S.top!=-1){while(T){Push(&S,T);S.flag[S.top]=0;T=T->lchild;}while( S.flag[S.top]==1)//while(S.top!=-1 && S.flag[S.top==1]){printf("%d",Pop(&S)->elem);}if(S.top!=-1) {S.flag[S.top]=1;T=S.data[S.top];T=T->rchild;}
// else
// {
// T=NULL;
// }}
}
层次遍历
void LevelPrint(BTree *T)//层次遍历
{if(T){Queue Q=CreateQueue();AddQ(&Q,T);while(Q.front->next){T=DeleteQ(&Q);printf("%d",T->elem);if(T->lchild) AddQ(&Q,T->lchild);if(T->rchild) AddQ(&Q,T->rchild);} }
}
求叶子节点个数
int LeafNum(BTree *T)
{if(T){if(!T->lchild && !T->rchild){return 1; }else{return LeafNum(T->lchild)+LeafNum(T->rchild);}}else{return 0;}
}
完整代码
//BT.h
#pragma once
#define N 100
typedef int ElemType;
typedef struct BTree
{int elem;struct BTree *lchild;struct BTree *rchild;
}BTree;typedef struct Stack
{int top;BTree * data[N];int flag[N];//用于非递归后序遍历
}Stack;typedef struct Node
{BTree *elem;struct Node *next;
}Node;typedef struct Queue
{Node *front;Node *rear;
}Queue;BTree * PreCreateBTree();//先序建立二叉树
BTree * Pre_Mid_CreateBTree(ElemType * Pre,ElemType *Mid,int n);//先序+中序建立二叉树
BTree * Post_Mid_CreateBTree(ElemType * Post,ElemType *Mid,int n);//后序+中序建立二叉树void PrePrintBTree(BTree *T);//递归先序遍历
void MidPrintBTree(BTree *T);//递归中序遍历
void PostPrintBTree(BTree *T);//递归后序遍历void PrintBTreePre(BTree *T);//非递归先序遍历
void PrintBTreeMid(BTree *T);//非递归中序遍历
void PrintBTreePost(BTree *T);//非递归后序遍历void LevelPrint(BTree *T);//层次遍历int LeafNum(BTree *T);//求叶子节点个数void Push(Stack *S,BTree * elem);//入栈
BTree *Pop(Stack *S);//出栈
Queue CreateQueue();//创建队列
void AddQ(Queue *Q,BTree *elem);//入队
BTree *DeleteQ(Queue *Q);//出队
//BT.c
#include <stdio.h>
#include <stdlib.h>
#include "BT.h"//先序遍历创建二叉树
BTree * PreCreateBTree()
{BTree *T;int elem;scanf("%d",&elem);if(elem==0){T=NULL;}else{T=(BTree*)malloc(sizeof(BTree));T->elem=elem;T->lchild=PreCreateBTree();T->rchild=PreCreateBTree();}return T;
}BTree * Pre_Mid_CreateBTree(ElemType * Pre,ElemType *Mid,int n)//前序+中序建立二叉树
{BTree *root=(BTree*)malloc(sizeof(BTree));root->elem=Pre[0];root->lchild=root->rchild=NULL;int i;int j;for(i=0;i<n;i++){if(Mid[i]==root->elem)break;} if(i>0){ElemType*LSubPre=(ElemType*)malloc(i*sizeof(ElemType));ElemType*LSubMid=(ElemType*)malloc(i*sizeof(ElemType));for(j=0;j<i;j++){LSubPre[j]=Pre[j+1];}for(j=0;j<i;j++){LSubMid[j]=Mid[j];} root->lchild=Pre_Mid_CreateBTree(LSubPre,LSubMid,i);ElemType*RSubPre=(ElemType*)malloc(i*sizeof(ElemType));ElemType*RSubMid=(ElemType*)malloc(i*sizeof(ElemType));for(j=0;j<i;j++){RSubPre[j]=Pre[j+i+1];}for(j=0;j<i;j++){RSubMid[j]=Mid[j+i+1];} root->rchild=Pre_Mid_CreateBTree(RSubPre,RSubMid,i);}return root;
}BTree * Post_Mid_CreateBTree(ElemType * Post,ElemType *Mid,int n)//后序+中序建立二叉树
{BTree *root=(BTree*)malloc(sizeof(BTree));root->elem=Post[n-1];root->lchild=root->rchild=NULL;int i;int j;for(i=0;i<n;i++){if(Mid[i]==root->elem)break;} if(i>0){ElemType*LSubPost=(ElemType*)malloc(i*sizeof(ElemType));ElemType*LSubMid=(ElemType*)malloc(i*sizeof(ElemType));for(j=0;j<i;j++){LSubPost[j]=Post[j];}for(j=0;j<i;j++){LSubMid[j]=Mid[j];} root->lchild=Post_Mid_CreateBTree(LSubPost,LSubMid,i);ElemType*RSubPost=(ElemType*)malloc(i*sizeof(ElemType));ElemType*RSubMid=(ElemType*)malloc(i*sizeof(ElemType));for(j=0;j<i;j++){RSubPost[j]=Post[j+i];}for(j=0;j<i;j++){RSubMid[j]=Mid[j+i+1];} root->rchild=Post_Mid_CreateBTree(RSubPost,RSubMid,i);}return root;
}//先序递归遍历
void PrePrintBTree(BTree *T)
{if(T){printf("%d",T->elem);PrePrintBTree(T->lchild);PrePrintBTree(T->rchild);}
}//中序递归遍历
void MidPrintBTree(BTree *T)
{if(T){MidPrintBTree(T->lchild);printf("%d",T->elem);MidPrintBTree(T->rchild);}
}//后序递归遍历
void PostPrintBTree(BTree *T)
{if(T){PostPrintBTree(T->lchild);PostPrintBTree(T->rchild);printf("%d",T->elem);}
}//非递归先序遍历
void PrintBTreePre(BTree *T)
{Stack S;S.top=-1;while(T || S.top!=-1){while(T){printf("%d",T->elem);Push(&S,T);T=T->lchild;}if(S.top!=-1){T=Pop(&S);T=T->rchild;}}
}//非递归中序遍历
void PrintBTreeMid(BTree *T)
{Stack S;S.top=-1;while(T || S.top>-1){while(T){Push(&S,T);T=T->lchild;}if(S.top!=-1){T=Pop(&S);printf("%d",T->elem);T=T->rchild;}}
}//非递归后序遍历
void PrintBTreePost(BTree *T)
{Stack S;S.top=-1;while(T || S.top!=-1){while(T){Push(&S,T);S.flag[S.top]=0;T=T->lchild;}while( S.flag[S.top]==1)//while(S.top!=-1 && S.flag[S.top==1]){printf("%d",Pop(&S)->elem);}if(S.top!=-1) {S.flag[S.top]=1;T=S.data[S.top];T=T->rchild;}
// else
// {
// T=NULL;
// }}
}void LevelPrint(BTree *T)//层次遍历
{if(T){Queue Q=CreateQueue();AddQ(&Q,T);while(Q.front->next){T=DeleteQ(&Q);printf("%d",T->elem);if(T->lchild) AddQ(&Q,T->lchild);if(T->rchild) AddQ(&Q,T->rchild);} }
}int LeafNum(BTree *T)
{if(T){if(!T->lchild && !T->rchild){return 1; }else{return LeafNum(T->lchild)+LeafNum(T->rchild);}}else{return 0;}
}void Push(Stack *S,BTree * elem)
{if(S->top<N){S->data[++(S->top)]=elem;}else{printf("栈满，失败");}
}BTree *Pop(Stack *S)
{if(S->top==-1){printf("栈空，失败");return NULL;}else{return S->data[(S->top)--];}
}
Queue CreateQueue()
{Queue Q;Q.front=Q.rear=(Node*)malloc(sizeof(Node));Q.front->next=NULL;return Q;
}
void AddQ(Queue *Q,BTree *elem)
{Node *p=(Node*)malloc(sizeof(Node));p->elem=elem;p->next=Q->rear->next;Q->rear->next=p;Q->rear=p;
}BTree * DeleteQ(Queue *Q)
{if(Q->front->next){BTree *elem;if(Q->front->next==Q->rear)Q->rear=Q->front;Node *p = Q->front->next;Q->front->next=p->next;elem=p->elem;free(p);p=NULL;return elem;}else{puts("队列为空!");return NULL;}
}
//main.c
#include <stdio.h>
#include <stdlib.h>
#include "BT.h"int main(int argc, char *argv[])
{
/* int pre[]={1,2,4,5,3,6,7};int in[] ={4,2,5,1,6,3,7};BTree *root=Pre_Mid_CreateBTree(pre,in,7);PostPrintBTree(root);printf("\n");*/puts("--------------------------------------------");int in[]={4,2,5,1,6,3,7};int post[]={4,5,2,6,7,3,1};BTree*root=Post_Mid_CreateBTree(post,in,7); PrePrintBTree(root);/*BTree *T=PreCreateBTree();PrePrintBTree(T);printf("\n");MidPrintBTree(T);printf("\n");PostPrintBTree(T);printf("\n");PrintBTreePre(T);printf("\n");PrintBTreeMid(T);printf("\n");PrintBTreePost(T);printf("\n");printf("叶子节点数为:%d\n",LeafNum(T));LevelPrint(T);printf("\n");system("pause");*/return 0;
}
void PrePrintBTree(BTree *T)
{if(T){printf("%d",T->elem);PrePrintBTree(T->lchild);PrePrintBTree(T->rchild);}
}void MidPrintBTree(BTree *T)
{if(T){MidPrintBTree(T->lchild);printf("%d",T->elem);MidPrintBTree(T->rchild);}
}void PostPrintBTree(BTree *T)
{if(T){PostPrintBTree(T->lchild);PostPrintBTree(T->rchild);printf("%d",T->elem);}
}void PrintBTreePre(BTree *T)
{Stack S;S.top=-1;while(T || S.top!=-1){while(T){printf("%d",T->elem);Push(&S,T);T=T->lchild;}if(S.top!=-1){T=Pop(&S);T=T->rchild;}}
}void PrintBTreeMid(BTree *T)
{Stack S;S.top=-1;while(T || S.top>-1){while(T){Push(&S,T);T=T->lchild;}if(S.top!=-1){T=Pop(&S);printf("%d",T->elem);T=T->rchild;}}
}void PrintBTreePost(BTree *T)
{Stack S;S.top=-1;while(T || S.top!=-1){while(T){Push(&S,T);S.flag[S.top]=0;T=T->lchild;}while( S.flag[S.top]==1)//while(S.top!=-1 && S.flag[S.top==1]){printf("%d",Pop(&S)->elem);}if(S.top!=-1) {S.flag[S.top]=1;T=S.data[S.top];T=T->rchild;}
// else
// {
// T=NULL;
// }}
}void LevelPrint(BTree *T)//层次遍历
{if(T){Queue Q=CreateQueue();AddQ(&Q,T);while(Q.front->next){T=DeleteQ(&Q);printf("%d",T->elem);if(T->lchild) AddQ(&Q,T->lchild);if(T->rchild) AddQ(&Q,T->rchild);} }
}int LeafNum(BTree *T)
{if(T){if(!T->lchild && !T->rchild){return 1; }else{return LeafNum(T->lchild)+LeafNum(T->rchild);}}else{return 0;}
}//BT.h
#pragma once
#define N 100
typedef int ElemType;
typedef struct BTree
{int elem;struct BTree *lchild;struct BTree *rchild;
}BTree;typedef struct Stack
{int top;BTree * data[N];int flag[N];//用于非递归后序遍历
}Stack;typedef struct Node
{BTree *elem;struct Node *next;
}Node;typedef struct Queue
{Node *front;Node *rear;
}Queue;BTree * PreCreateBTree();//先序建立二叉树
BTree * Pre_Mid_CreateBTree(ElemType * Pre,ElemType *Mid,int n);//先序+中序建立二叉树
BTree * Post_Mid_CreateBTree(ElemType * Post,ElemType *Mid,int n);//后序+中序建立二叉树void PrePrintBTree(BTree *T);//递归先序遍历
void MidPrintBTree(BTree *T);//递归中序遍历
void PostPrintBTree(BTree *T);//递归后序遍历void PrintBTreePre(BTree *T);//非递归先序遍历
void PrintBTreeMid(BTree *T);//非递归中序遍历
void PrintBTreePost(BTree *T);//非递归后序遍历void LevelPrint(BTree *T);//层次遍历int LeafNum(BTree *T);//求叶子节点个数void Push(Stack *S,BTree * elem);//入栈
BTree *Pop(Stack *S);//出栈
Queue CreateQueue();//创建队列
void AddQ(Queue *Q,BTree *elem);//入队
BTree *DeleteQ(Queue *Q);//出队
//BT.c
#include <stdio.h>
#include <stdlib.h>
#include "BT.h"//先序遍历创建二叉树
BTree * PreCreateBTree()
{BTree *T;int elem;scanf("%d",&elem);if(elem==0){T=NULL;}else{T=(BTree*)malloc(sizeof(BTree));T->elem=elem;T->lchild=PreCreateBTree();T->rchild=PreCreateBTree();}return T;
}BTree * Pre_Mid_CreateBTree(ElemType * Pre,ElemType *Mid,int n)//前序+中序建立二叉树
{BTree *root=(BTree*)malloc(sizeof(BTree));root->elem=Pre[0];root->lchild=root->rchild=NULL;int i;int j;for(i=0;i<n;i++){if(Mid[i]==root->elem)break;} if(i>0){ElemType*LSubPre=(ElemType*)malloc(i*sizeof(ElemType));ElemType*LSubMid=(ElemType*)malloc(i*sizeof(ElemType));for(j=0;j<i;j++){LSubPre[j]=Pre[j+1];}for(j=0;j<i;j++){LSubMid[j]=Mid[j];} root->lchild=Pre_Mid_CreateBTree(LSubPre,LSubMid,i);ElemType*RSubPre=(ElemType*)malloc(i*sizeof(ElemType));ElemType*RSubMid=(ElemType*)malloc(i*sizeof(ElemType));for(j=0;j<i;j++){RSubPre[j]=Pre[j+i+1];}for(j=0;j<i;j++){RSubMid[j]=Mid[j+i+1];} root->rchild=Pre_Mid_CreateBTree(RSubPre,RSubMid,i);}return root;
}BTree * Post_Mid_CreateBTree(ElemType * Post,ElemType *Mid,int n)//后序+中序建立二叉树
{BTree *root=(BTree*)malloc(sizeof(BTree));root->elem=Post[n-1];root->lchild=root->rchild=NULL;int i;int j;for(i=0;i<n;i++){if(Mid[i]==root->elem)break;} if(i>0){ElemType*LSubPost=(ElemType*)malloc(i*sizeof(ElemType));ElemType*LSubMid=(ElemType*)malloc(i*sizeof(ElemType));for(j=0;j<i;j++){LSubPost[j]=Post[j];}for(j=0;j<i;j++){LSubMid[j]=Mid[j];} root->lchild=Post_Mid_CreateBTree(LSubPost,LSubMid,i);ElemType*RSubPost=(ElemType*)malloc(i*sizeof(ElemType));ElemType*RSubMid=(ElemType*)malloc(i*sizeof(ElemType));for(j=0;j<i;j++){RSubPost[j]=Post[j+i];}for(j=0;j<i;j++){RSubMid[j]=Mid[j+i+1];} root->rchild=Post_Mid_CreateBTree(RSubPost,RSubMid,i);}return root;
}//先序递归遍历
void PrePrintBTree(BTree *T)
{if(T){printf("%d",T->elem);PrePrintBTree(T->lchild);PrePrintBTree(T->rchild);}
}//中序递归遍历
void MidPrintBTree(BTree *T)
{if(T){MidPrintBTree(T->lchild);printf("%d",T->elem);MidPrintBTree(T->rchild);}
}//后序递归遍历
void PostPrintBTree(BTree *T)
{if(T){PostPrintBTree(T->lchild);PostPrintBTree(T->rchild);printf("%d",T->elem);}
}//非递归先序遍历
void PrintBTreePre(BTree *T)
{Stack S;S.top=-1;while(T || S.top!=-1){while(T){printf("%d",T->elem);Push(&S,T);T=T->lchild;}if(S.top!=-1){T=Pop(&S);T=T->rchild;}}
}//非递归中序遍历
void PrintBTreeMid(BTree *T)
{Stack S;S.top=-1;while(T || S.top>-1){while(T){Push(&S,T);T=T->lchild;}if(S.top!=-1){T=Pop(&S);printf("%d",T->elem);T=T->rchild;}}
}//非递归后序遍历
void PrintBTreePost(BTree *T)
{Stack S;S.top=-1;while(T || S.top!=-1){while(T){Push(&S,T);S.flag[S.top]=0;T=T->lchild;}while( S.flag[S.top]==1)//while(S.top!=-1 && S.flag[S.top==1]){printf("%d",Pop(&S)->elem);}if(S.top!=-1) {S.flag[S.top]=1;T=S.data[S.top];T=T->rchild;}
// else
// {
// T=NULL;
// }}
}void LevelPrint(BTree *T)//层次遍历
{if(T){Queue Q=CreateQueue();AddQ(&Q,T);while(Q.front->next){T=DeleteQ(&Q);printf("%d",T->elem);if(T->lchild) AddQ(&Q,T->lchild);if(T->rchild) AddQ(&Q,T->rchild);} }
}int LeafNum(BTree *T)
{if(T){if(!T->lchild && !T->rchild){return 1; }else{return LeafNum(T->lchild)+LeafNum(T->rchild);}}else{return 0;}
}void Push(Stack *S,BTree * elem)
{if(S->top<N){S->data[++(S->top)]=elem;}else{printf("栈满，失败");}
}BTree *Pop(Stack *S)
{if(S->top==-1){printf("栈空，失败");return NULL;}else{return S->data[(S->top)--];}
}
Queue CreateQueue()
{Queue Q;Q.front=Q.rear=(Node*)malloc(sizeof(Node));Q.front->next=NULL;return Q;
}
void AddQ(Queue *Q,BTree *elem)
{Node *p=(Node*)malloc(sizeof(Node));p->elem=elem;p->next=Q->rear->next;Q->rear->next=p;Q->rear=p;
}BTree * DeleteQ(Queue *Q)
{if(Q->front->next){BTree *elem;if(Q->front->next==Q->rear)Q->rear=Q->front;Node *p = Q->front->next;Q->front->next=p->next;elem=p->elem;free(p);p=NULL;return elem;}else{puts("队列为空!");return NULL;}
}
//main.c
#include <stdio.h>
#include <stdlib.h>
#include "BT.h"int main(int argc, char *argv[])
{
/* int pre[]={1,2,4,5,3,6,7};int in[] ={4,2,5,1,6,3,7};BTree *root=Pre_Mid_CreateBTree(pre,in,7);PostPrintBTree(root);printf("\n");*/puts("--------------------------------------------");int in[]={4,2,5,1,6,3,7};int post[]={4,5,2,6,7,3,1};BTree*root=Post_Mid_CreateBTree(post,in,7); PrePrintBTree(root);/*BTree *T=PreCreateBTree();PrePrintBTree(T);printf("\n");MidPrintBTree(T);printf("\n");PostPrintBTree(T);printf("\n");PrintBTreePre(T);printf("\n");PrintBTreeMid(T);printf("\n");PrintBTreePost(T);printf("\n");printf("叶子节点数为:%d\n",LeafNum(T));LevelPrint(T);printf("\n");system("pause");*/return 0;
}
发布评论