C语言二叉树

1.思维导图

树

二叉树

 

2.将链式队列重新实现一遍

linkqueue.c

#include"linkqueue.h"
linkqueuePtr create()
{linkqueuePtr L=(linkqueuePtr)malloc(sizeof(linkqueue));if(NULL==L){printf("队列创建失败\n");return NULL;}L->head=(nodePtr)malloc(sizeof(node));if(NULL==L->head){printf("链式队列创建失败\n");free(L);L=NULL;return NULL;}L->head->len=0;L->head->next=NULL;L->tail=L->head;printf("链式队列创建成功\n");return L;
}int empty(linkqueuePtr L)
{if(NULL==L||L->head==NULL){printf("队列不合法\n");return -1;}return L->head==L->tail;
}void show(linkqueuePtr L)
{if(NULL==L||L->head==NULL||empty(L)){printf("遍历失败\n");return;}nodePtr q=L->head->next;while(q!=NULL){printf("%c ",q->data);q=q->next;}printf("\n");return;
}int push(linkqueuePtr L,DataType e)
{if(NULL==L||L->head==NULL){printf("队列不合法\n");return -1;}nodePtr n=(nodePtr)malloc(sizeof(node));if(NULL==n){printf("入队失败\n");return -2;}n->data=e;n->next=NULL;L->tail->next=n;L->tail=n;L->head->len++;show(L);return 0;
}int pop(linkqueuePtr L)
{if(NULL==L||L->head==NULL||empty(L)){printf("队列不合法\n");return -1;}nodePtr p=L->head->next;L->head->next=p->next;printf("%c出列\n",p->data);show(L);free(p);p=NULL;L->head->len--;if(L->head->next==NULL){L->tail=L->head;}return 0;
}int size(linkqueuePtr L)
{printf("队列大小为%d\n",L->head->len);show(L);return 0;
}void destroy(linkqueuePtr L)
{if(NULL==L){return;}if(NULL==L->head){free(L);L=NULL;}while(!empty(L)){pop(L);}free(L->head);free(L);L=NULL;printf("队列销毁成功\n");return;
}

 linkqueue.h

#ifndef LINKQUEUE_H
#define LINKQUEUE_H#include<stdio.h>
#include<stdlib.h>
#include<string.h>typedef char DataType;typedef struct node
{union{int len;DataType data;};struct node *next;
}node,*nodePtr;typedef struct LinkQueue
{nodePtr head;nodePtr tail;
}linkqueue,*linkqueuePtr;linkqueuePtr create();int empty(linkqueuePtr L);void show(linkqueuePtr L);int push(linkqueuePtr L,DataType e);int pop(linkqueuePtr L);int size(linkqueuePtr L);void destroy(linkqueuePtr L);#endif

main.c

#include"linkqueue.h"
int main()
{linkqueuePtr L=create();push(L,'a');push(L,'b');push(L,'c');push(L,'d');push(L,'e');pop(L);pop(L);pop(L);size(L);destroy(L);return 0;
}

输出结果:

3.将二叉树的创建和遍历重新实现一遍

tree.c

#include"tree.h"nodePtr tree_create()
{char value = 0;scanf("%c",&value);getchar();if(value=='#'){return NULL;}nodePtr n=(nodePtr)malloc(sizeof(node));if(NULL==n){printf("节点申请失败\n");return NULL;}n->data=value;n->L=tree_create();n->R=tree_create();return n;
}void pri_show(nodePtr T)
{if(NULL==T){return;}printf("%c ",T->data);pri_show(T->L);pri_show(T->R);
}void in_show(nodePtr T)
{if(NULL==T){return;}in_show(T->L);printf("%c ",T->data);in_show(T->R);
}void post_show(nodePtr T)
{if(NULL==T){return;}post_show(T->L);post_show(T->R);printf("%c ",T->data);
}

 tree.h

#ifndef TREE_H
#define TREE_H#include<stdio.h>
#include<stdlib.h>typedef int DataType;typedef struct node
{DataType data;struct node *L;struct node *R;
}node,*nodePtr;nodePtr tree_create();void pri_show(nodePtr T);void in_show(nodePtr T);void post_show(nodePtr T);#endif

main.c

#include"tree.h"
int main()
{nodePtr T=tree_create();if(NULL==T){return -1;}printf("二叉树创建成功\n");pri_show(T);printf("\n");return  0;
}

输出结果：

4.根据给出的二叉树序列画出该二叉树的图，并给出后序序列

前序遍历的顺序是: CABGHEDF

中序遍历的顺序是: GHBACDEF

5.