一、思维导图
+
二、二叉树序列练习题
2.1. 根据给出的二叉树序列，画出该二叉树的图，并给出后序序列。
前序遍历的顺序是: CABGHEDF
中序遍历的顺序是: GHBACDEF
2.2. 已知如下：
中序遍历：HDMIBJNEAFKCG
后序遍历：HMIDNJEBKFGCA
画出二叉树并写出前序遍历。
三、代码
3.1. 链式队列
【linkQueue.h】
#ifndef __LINKQUEUE_H__
#define __LINKQUEUE_H__#include <stdio.h>
#include <stdlib.h>typedef char DataType;
//定义节点类型
typedef struct Node
{union{int len; //头节点数据域DataType data; //普通节点数据域};struct Node *next; //指针域
}Node, *NodePtr;//定义队列类型
typedef struct
{NodePtr head; //指向头节点的指针NodePtr tail; //指向位节点的指针
}linkQueue, *linkQueuePtr;//创建链式队列
linkQueuePtr create();//判空
int empty(linkQueuePtr L);//入队
int push(linkQueuePtr L, DataType e);//遍历
void show(linkQueuePtr L);//出队
int pop(linkQueuePtr L);//求大小
int size(linkQueuePtr L);//销毁
void my_free(linkQueuePtr L);#endif【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; //链表长度为0L->head->next = NULL; //指针域置空//将尾指针也指向头节点L->tail = L->head;printf("链式队列创建成功！\n");return L;
}//判空：1空，0非空
int empty(linkQueuePtr L)
{if(NULL == L || L->head == NULL){printf("所给队列不合法！\n");return -1;}//返回队头和队尾是否相等return L->head == L->tail ? 1:0;
}//入队
int push(linkQueuePtr L, DataType e)
{ if(NULL == L || L->head == NULL){printf("所给队列不合法！\n");return -1;}//申请节点封装数据NodePtr p = (NodePtr)malloc(sizeof(Node));if(NULL == p){printf("入队失败！\n");return -2;}p->data = e; //将数据封装进节点中p->next = NULL; //指针域置空，防止野指针//插入逻辑L->tail->next = p; //将新节点连到链表上L->tail = p; //更新尾指针，指向最后一个节点//表长变化L->head->len++;printf("入队成功！\n");return 0;
}//遍历
void show(linkQueuePtr L)
{if(NULL == L || L->head == NULL || empty(L)){printf("遍历失败！\n");}//遍历逻辑printf("从队头到队尾元素为：");NodePtr q = L->head->next; //定义遍历指针从第一个节点出发while(q != NULL){//说明q指向的是正常节点，输出其数据域printf("%c ", q->data);q = q->next;}printf("\n");
}//出队
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);free(p); //释放节点p=NULL;//表长变化L->head->len--;//判断是否已全部删除if(L->head->next == NULL){L->tail = L->head; //将尾指针重新指向头节点}return 0;
}//求大小
int size(linkQueuePtr L)
{return L->head->len;
}//销毁
void my_free(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");
}【main.c】
#include "linkQueue.h"int main()
{linkQueuePtr L = create();if(NULL == L){return -1;}//调用入队函数push(L, 'A'); push(L, 'B'); push(L, 'C'); push(L, 'D'); //遍历show(L);//出队pop(L);show(L);pop(L);show(L);//求大小size(L);//销毁my_free(L);return 0;
}3.2. 二叉树
【bitree.h】
#ifndef __BITREE_H__
#define __BITREE_H__#include <stdio.h>
#include <stdlib.h>typedef char DataType;typedef struct Node
{DataType data;struct Node *L;struct Node *R;
}Node, *NodePtr;//二叉树创建
NodePtr create();//先序遍历
void pri_order(NodePtr T);//中序遍历
void in_order(NodePtr T);//后序遍历
void post_order(NodePtr T);#endif【bitree.c】
#include "bitree.h"//二叉树创建
NodePtr create()
{char value = 0;scanf("%c", &value);getchar();//判断输入数据if(value == '#'){return NULL;}//申请节点封装数据NodePtr T = (NodePtr)malloc(sizeof(Node));if(NULL == T){printf("节点申请失败！\n");return NULL;}//将数据放入数据域中T->data = value;//递归创建左子树T->L = create();//递归创建右子树T->R = create();return T;
}//先序遍历
void pri_order(NodePtr T)
{//判断逻辑if(NULL == T){return; //递归出口}//输出节点数据域printf("%c ", T->data);//先序遍历左子树pri_order(T->L);//先序遍历右子树pri_order(T->R);
}//中序遍历
void in_order(NodePtr T)
{//判断逻辑if(NULL == T){return; //递归出口}//中序遍历左子树in_order(T->L);//输出节点数据域printf("%c ", T->data);//中序遍历右子树in_order(T->R);
}//后序遍历
void post_order(NodePtr T)
{//判断逻辑if(NULL == T){return; //递归出口}//后序遍历左子树post_order(T->L);//后序遍历右子树post_order(T->R);//输出节点数据域printf("%c ", T->data);
}【main.c】
#include "bitree.h"int main()
{NodePtr T= create();if(NULL == T){return -1;}printf("二叉树创建成功！\n");printf("先序序列为：");pri_order(T);printf("\n");printf("中序序列为：");in_order(T);printf("\n");printf("后序序列为：");post_order(T);printf("\n");return 0;
}【执行结果】
