数据结构——二叉树四种遍历的实现-2
https://developer.aliyun.com/article/1507985
3、二叉树的创建
首先创建根节点，接着创建左子树，最后创建右子树，结点不存在输入用#表示
不带形参创建用C语言实现如下：
btree_pnode create_btree(void) { btree_pnode t; datatype_bt ch; //如果结点不存在，则输入时，用#表示 scanf("%c",&ch); if('#' == ch) t = NULL; else{ //创建根结点 t = (btree_pnode)malloc(sizeof(btree_node)); if(NULL == t){ perror("malloc"); exit(1); } t->data = ch; //创建左子树 t->lchild = create_btree(); //创建右子树 t->rchild = create_btree(); } return t; }
带形参创建用C语言实现如下：
void create_btree(btree_pnode *T) { datatype_bt ch; //如果结点不存在，则输入时，用#表示 scanf("%c",&ch); if('#' == ch) *T = NULL; else{ //创建根结点 *T = (btree_pnode)malloc(sizeof(btree_node)); if(NULL == *T){ perror("malloc"); exit(1); } (*T)->data = ch; //创建左子树 create_btree(&(*T)->lchild); //创建右子树 create_btree(&(*T)->rchild); } }
四、二叉树的遍历
二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点访问一次且仅被访问一次。
对于线性表的遍历，要么从头到尾，要么从尾到头，遍历方式较为单纯，但是树不一样，它的每个结点都有可能有两个孩子结点，所以遍历的顺序面临着不同的选择。
二叉树的常用遍历方法有以下四种：先序遍历、中序遍历、后序遍历、层序遍历。
1、 先序遍历
1）算法描述
【先序遍历】如果二叉树为空，则直接返回。否则，先访问根结点，再递归先序遍历左子树，再递归先序遍历右子树。
先序遍历的结果如下：abdghcefi。
2）源码详解
先序遍历用C语言实现如下：
void pre_order(btree_pnode t) { if(t != NULL){ //访问根结点 printf("%c",t->data); //先序遍历左子树 pre_order(t->lchild); //先序遍历右子树 pre_order(t->rchild); } }
扩展：先序非递归算法实现，用到链式栈，可参考如下文章：数据结构——顺序栈与链式栈的实现-CSDN博客
用C语言实现如下：
void unpre_order(btree_pnode t) { link_pstack top; //top为指向栈顶结点的指针 init_linkstack(&top); //初始化链栈 while(t != NULL || !isempty_linkstack(top)){ if(t != NULL){ printf("%c",t->data); if(t->rchild != NULL) push_linkstack(t->rchild,&top); t = t->lchild; }else pop_linkstack(&t,&top); } }
2、 中序遍历
1）算法描述
【中序遍历】如果二叉树为空，则直接返回。否则，先递归中序遍历左子树，再访问根结点，再递归中序遍历右子树。
中序遍历的结果如下：gdhbaecif。
2）源码详解
中序遍历用C语言实现如下：
void mid_order(btree_pnode t) { if(t != NULL){ //中序遍历左子树 mid_order(t->lchild); //访问根结点 printf("%c",t->data); //中序遍历右子树 mid_order(t->rchild); } }
3、 后序遍历
1）算法描述
【后序遍历】如果二叉树为空，则直接返回。否则，先递归后遍历左子树，再递归后序遍历右子树，再访问根结点。
后序遍历的结果如下：ghdbeifca。
2）源码详解
后序遍历用C语言实现如下：
void post_order(btree_pnode t) { if(t != NULL){ //先序遍历左子树 post_order(t->lchild); //先序遍历右子树 post_order(t->rchild); //访问根结点 printf("%c",t->data); } }
4、 层序遍历
1）算法描述
【层序遍历】如果二叉树为空，则直接返回。否则，依次从树的第一层开始，从上至下逐层遍历。在同一层中，按从左到右的顺序对结点逐个访问。
层序遍历需要用到队列知识，可以参考如下文章：
2）源码详解
层序遍历用C语言实现如下：
void level_order(btree_pnode t) { link_pqueue q; init_linkqueueu(&q); //初始化链式队列 while(t != NULL){ printf("%c",t->data); if(t->lchild != NULL) in_linkqueue(t->lchild,q); if(t->rchild != NULL) in_linkqueue(t->rchild,q); if(is_empty_linkqueue(q)) break; else out_linkqueue(&t,q); } }
5、四种遍历代码整合btree.h
#ifndef __BTREE_h__ #define __BTREE_h__ #include <stdio.h> #include <stdlib.h> #include <stdbool.h> typedef char datatype_bt; typedef struct btreenode{ datatype_bt data; struct btreenode *lchild,*rchild; }btree_node,*btree_pnode; extern void create_btree(btree_pnode *T); extern void pre_order(btree_pnode t); extern void unpre_order(btree_pnode t); extern void mid_order(btree_pnode t); extern void post_order(btree_pnode t); extern void level_order(btree_pnode t); extern void travel(char const *str,void (*pfun)(btree_pnode ),btree_pnode t); #endif
btree.c
#include "btree.h" #include "linkqueue.h" #include "linkstack.h" #if 0 btree_pnode create_btree(void) { btree_pnode t; datatype_bt ch; //如果结点不存在，则输入时，用#表示 scanf("%c",&ch); if('#' == ch) t = NULL; else{ //创建根结点 t = (btree_pnode)malloc(sizeof(btree_node)); if(NULL == t){ perror("malloc"); exit(1); } t->data = ch; //创建左子树 t->lchild = create_btree(); //创建右子树 t->rchild = create_btree(); } return t; } #else void create_btree(btree_pnode *T) { datatype_bt ch; //如果结点不存在，则输入时，用#表示 scanf("%c",&ch); if('#' == ch) *T = NULL; else{ //创建根结点 *T = (btree_pnode)malloc(sizeof(btree_node)); if(NULL == *T){ perror("malloc"); exit(1); } (*T)->data = ch; //创建左子树 create_btree(&(*T)->lchild); //创建右子树 create_btree(&(*T)->rchild); } } #endif //先序遍历 void pre_order(btree_pnode t) { if(t != NULL){ //访问根结点 printf("%c",t->data); //先序遍历左子树 pre_order(t->lchild); //先序遍历右子树 pre_order(t->rchild); } } //先序非递归算法实现 void unpre_order(btree_pnode t) { link_pstack top; //top为指向栈顶结点的指针 init_linkstack(&top); //初始化链栈 while(t != NULL || !isempty_linkstack(top)){ if(t != NULL){ printf("%c",t->data); if(t->rchild != NULL) push_linkstack(t->rchild,&top); t = t->lchild; }else pop_linkstack(&t,&top); } } //中序遍历 void mid_order(btree_pnode t) { if(t != NULL){ //中序遍历左子树 mid_order(t->lchild); //访问根结点 printf("%c",t->data); //中序遍历右子树 mid_order(t->rchild); } } //后序遍历 void post_order(btree_pnode t) { if(t != NULL){ //先序遍历左子树 post_order(t->lchild); //先序遍历右子树 post_order(t->rchild); //访问根结点 printf("%c",t->data); } } //层序遍历 void level_order(btree_pnode t) { link_pqueue q; init_linkqueueu(&q); //初始化链式队列 while(t != NULL){ printf("%c",t->data); if(t->lchild != NULL) in_linkqueue(t->lchild,q); if(t->rchild != NULL) in_linkqueue(t->rchild,q); if(is_empty_linkqueue(q)) break; else out_linkqueue(&t,q); } } void travel(char const *str,void (*pfun)(btree_pnode ),btree_pnode t) { printf("%s",str); pfun(t); printf("\n"); }
linkstack.h
#ifndef __LINKSTACK_H__ #define __LINKSTACK_H__ #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include "btree.h" typedef btree_pnode datatype_ls; typedef struct linkstack{ datatype_ls data; struct linkstack *next; }link_stack,*link_pstack; extern void init_linkstack(link_pstack *Top); extern bool push_linkstack(datatype_ls data,link_pstack *Top); extern bool pop_linkstack(datatype_ls *t,link_pstack *Top); extern bool isempty_linkstack(link_pstack top); //extern void show_linkstack(link_pstack top); #endif
linkstack.c
#include "linkstack.h" //链栈的初始化 void init_linkstack(link_pstack *Top) { *Top = NULL; } //入栈 bool push_linkstack(datatype_ls data,link_pstack *Top) { link_pstack new; new = (link_pstack)malloc(sizeof(link_stack)); if(NULL == new){ perror("malloc"); return false; } new->data = data; new->next = *Top; *Top = new; return true; } //出栈 bool pop_linkstack(datatype_ls *t,link_pstack *Top) { link_pstack q; if(isempty_linkstack(*Top)){ printf("链栈是空的!\n"); return false; } //出栈 q = *Top; *Top = (*Top)->next; *t = q->data; free(q); return true; } //判断顺序栈是否空 bool isempty_linkstack(link_pstack top) { if(top == NULL) return true; else return false; } #if 0 void show_linkstack(link_pstack top) { link_pstack p; for(p = top; p != NULL; p = p->next) printf("%d\t",p->data); printf("\n"); } #endif
linkqueue.h
#ifndef __LINKQUEUE_H__ #define __LINKQUEUE_H__ #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include "btree.h" typedef btree_pnode datatype_lq; typedef struct listnode{ datatype_lq data; struct listnode *next; }list_node,*list_pnode; typedef struct linkqueue{ list_pnode front,rear; }link_queue,*link_pqueue; extern void init_linkqueueu(link_pqueue *Q); extern bool in_linkqueue(datatype_lq data,link_pqueue q); extern bool out_linkqueue(datatype_lq *t,link_pqueue q); extern bool is_empty_linkqueue(link_pqueue q); //extern void show_linkqueue(link_pqueue q); #endif
linkqueue.c
#include "linkqueue.h" void init_linkqueueu(link_pqueue *Q) { *Q = (link_pqueue)malloc(sizeof(link_queue)); if(NULL == *Q){ perror("malloc"); exit(1); } (*Q)->front = (list_pnode)malloc(sizeof(list_node)); if(NULL == (*Q)->front){ perror("malloc"); exit(1); } (*Q)->front->next = NULL; (*Q)->rear = (*Q)->front; } bool in_linkqueue(datatype_lq data,link_pqueue q) { list_pnode new; new = (list_pnode)malloc(sizeof(list_node)); if(NULL == new){ perror("malloc"); return false; } new->data = data; new->next = q->rear->next; q->rear->next = new; q->rear = new; return true; } bool out_linkqueue(datatype_lq *t,link_pqueue q) { list_pnode p; if(is_empty_linkqueue(q)){ printf("队列是空的!\n"); return false; } p = q->front; q->front = q->front->next; *t = q->front->data; free(p); return true; } bool is_empty_linkqueue(link_pqueue q) { if(q->rear == q->front) return true; else return false; } #if 0 void show_linkqueue(link_pqueue q) { list_pnode p; for(p = q->front->next;p;p = p->next) printf("%d\t",p->data); printf("\n"); } #endif
test.c
#include "btree.h" int main(void) { btree_pnode t; //定义根结点指针 create_btree(&t); //创建二叉树 travel("先序遍历二叉树:",pre_order,t); travel("先序非递归遍历二叉树:",unpre_order,t); travel("中序遍历二叉树:",mid_order,t); travel("后序遍历二叉树:",post_order,t); travel("按层遍历二叉树:",level_order,t); return 0; }
Makefile
CC = gcc CFLAGS = -Wall -g -O0 SRC = btree.c test.c linkqueue.c linkstack.c OBJS = test $(OBJS):$(SRC) $(CC) $(CFLAGS) -o $@ $^ clean: $(RM) $(OBJS) .*.sw?
- -o0"表示优化级别为0，即关闭优化。这将导致生成的可执行文件较大，但是可以方便地进行调试。
- "-g"表示生成调试信息，以便在调试程序时可以查看变量的值、函数的调用栈等信息。
- "-Wall"表示启用所有警告，编译器将会显示所有可能的警告信息，帮助开发人员发现潜在的问题。
- $(RM)：这是一个Makefile中的变量，用于表示删除命令。它可能被设置为系统中的实际删除命令，例如rm或del。
- $(OBJS)：这是一个Makefile中的变量，表示要删除的目标文件列表。
- .*.sw?：这是一个通配符表达式，用于匹配以.开头的任意文件名，后跟.sw和一个字符（例如.swp）。这通常用于删除编辑器生成的临时文件。
验证结果：
验证结果：
