二叉树(C语言)

<pre name="code" class="cpp">#include <stdio.h> #include <malloc.h>typedef char elemType;typedef struct BTree {elemType data;struct BTree* lTree;struct BTree* rTree;struct BTree* next;//打印二叉树时建立队列需要 }Tree;typedef struct QList {Tree* first;//队头Tree* rear;//队尾int queneSize;//队大小 }Quene;//队列初始化 生成空队列 Quene* createQuene() {Quene* Q;Q=(Quene*)malloc(sizeof(Quene));Q->first=Q->rear=NULL;Q->queneSize=0;return Q; }//入队 void enterQuene(Quene* Q,Tree* T) {Tree* p;p=(Tree*)malloc(sizeof(Tree));p->data=T->data;p->lTree=T->lTree;p->rTree=T->rTree;p->next=NULL;Q->queneSize++;if(Q->first==NULL)//空队列Q->first=Q->rear=p;else{Q->rear->next=p;Q->rear=p;}}//出队 Tree* deleteQuene(Quene* Q,elemType *elem) {Tree* p;p=(Tree*)malloc(sizeof(Tree));*elem=Q->first->data;p=Q->first;Q->first=p->next;Q->queneSize--;if(Q->queneSize==0)//重要Q->rear=NULL;return p;//free(p);//p=NULL; }//遍历队列 void displayQuene(Quene* Q) {printf("遍历队列\r\n");int i=Q->queneSize;Tree* p=(Tree*)malloc(sizeof(Tree));p=Q->first;while(i--){printf("%c\t",p->data);p=p->next;}printf("\r\n"); }//判断队列是否为空 bool isEmptyQuene(Quene* Q) {return Q->first==NULL&&Q->rear==NULL&&Q->queneSize==0; }//创建二叉树 Tree* createTree() {Tree* T;T=(Tree*)malloc(sizeof(Tree));char ch;scanf("%c",&ch);if(ch=='#')return NULL;T->data=ch;T->next=NULL;T->lTree=createTree();T->rTree=createTree();return T; }//判断是否为空树 bool isEmptyTree(Tree* T) {return T==NULL; }//先序遍历二叉树 void preOrder(Tree* T) {if(T){preOrder(T->lTree);printf("%c\t",T->data);preOrder(T->rTree);} }//中序遍历二叉树 void inOrder(Tree* T) {if(T){printf("%c\t",T->data);inOrder(T->lTree);inOrder(T->rTree);} }//后序遍历二叉树 void postOrder(Tree* T) {if(T){postOrder(T->lTree);postOrder(T->rTree);printf("%c\t",T->data);} }//打印二叉树（重点）从上往下打印二叉树 void printTree_elem(Tree* T) {printf("层次遍历打印二叉树\r\n");if(T == NULL)return;Quene* Q;Q=createQuene();printf("%c\t",T->data);if(T->lTree)enterQuene(Q,T->lTree);if(T->rTree)enterQuene(Q,T->rTree);while(!isEmptyQuene(Q)){elemType temp;Tree* p;p=deleteQuene(Q,&temp);printf("%c\t",temp);if(p->lTree)enterQuene(Q,p->lTree);if(p->rTree)enterQuene(Q,p->rTree);}printf("\r\n"); }//打印二叉树（重点）图形 队列 bool printTree(Tree* T,int nLayer) {if(T==NULL){for(int i=0;i<nLayer;i++){printf(" ");}printf("%c\n",'#');return false;}printTree(T->rTree,nLayer+3);for(int i=0;i<nLayer;i++){printf(" ");}printf("%c\n",T->data);printTree(T->lTree,nLayer+3);return true; }//清空二叉树 void clearTree(Tree* T) {if(T ==NULL)return;if(T->lTree!=NULL)clearTree(T->lTree);if(T->rTree!=NULL)clearTree(T->rTree);free(T);//T=NULL;return; } //销毁二叉树 void destroyTree(Tree* T) {if(T)clearTree(T); }//返回树的深度 int deptTree(Tree* T) {int ldept,rdept;ldept=0;rdept=0;if(T->lTree||T->rTree){if(T->lTree)ldept=deptTree(T->lTree);if(T->rTree)rdept=deptTree(T->rTree);}return 1+(ldept>rdept?ldept:rdept);//1 根节点 }//返回结点数 int cntTree(Tree* T) {int cnt=0;if(T)cnt++;if(T->lTree)cnt+=cntTree(T->lTree);if(T->rTree)cnt+=cntTree(T->rTree);return cnt; }//返回子树结点深度 void deptNode(Tree* T,Tree* p,int *dept,int *flag) {if(T->data==p->data)//找到该子树{*flag=1;return;}if(!*flag)(*dept)++;if(!*flag)if(T->lTree){deptNode(T->lTree,p,&(*dept),&(*flag));if(*flag)return;}if(!*flag)if(T->rTree){deptNode(T->rTree,p,&(*dept),&(*flag));if(*flag)return;}if(!*flag){(*dept)=(*dept)-1;return;} }int main() {Tree* T;printf("创建二叉树\r\n");T=createTree();printf("先序遍历二叉树\r\n");preOrder(T);printf("\r\n");printf("中序遍历二叉树\r\n");inOrder(T);printf("\r\n");printf("后序遍历二叉树\r\n");postOrder(T);printf("\r\n");printf("二叉树的深度:%d\r\n",deptTree(T));printf("二叉树的结点数:%d\r\n",cntTree(T));/*//测试：返回子树结点的深度Tree* p;p=(Tree*)malloc(sizeof(Tree));p->lTree=NULL;p->rTree=NULL;int dept=1;//子树深度int flag=0;//搜索标志 找到时置1 // p->data='a'; // p->data='b'; // p->data='c'; // p->data='d'; // p->data='e'; // p->data='f';p->data='g';deptNode(T,p,&dept,&flag);printf("子树结点%c的深度为:%d\r\n",p->data,dept);*/printTree_elem(T);printf("打印竖状二叉树\r\n");printTree(T,0); }

总结

以上是生活随笔为你收集整理的二叉树(C语言)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。