数据结构——二叉树四种遍历的实现-3-阿里云开发者社区

数据结构——二叉树四种遍历的实现-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）算法描述

【先序遍历】如果二叉树为空，则直接返回。否则，先访问根结点，再递归先序遍历左子树，再递归先序遍历右子树。

c14b4fafa9f237393bd6dc33ed8b3470_06c6e94ac9ae43a187f2d9160aa44f05.png

先序遍历的结果如下：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）算法描述

【中序遍历】如果二叉树为空，则直接返回。否则，先递归中序遍历左子树，再访问根结点，再递归中序遍历右子树。

2a8ad19df2611b5c2b6a5d4c01298b15_234ee77654fb424bb9d3f45ca13daa92.png

中序遍历的结果如下：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）算法描述

【后序遍历】如果二叉树为空，则直接返回。否则，先递归后遍历左子树，再递归后序遍历右子树，再访问根结点。

b3761e4ab5c3ea526266f7b6844ce162_4a913cdb1da647cd9922404a42c0edf7.png

后序遍历的结果如下：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）算法描述

【层序遍历】如果二叉树为空，则直接返回。否则，依次从树的第一层开始，从上至下逐层遍历。在同一层中，按从左到右的顺序对结点逐个访问。

层序遍历需要用到队列知识，可以参考如下文章：

数据结构——顺序队列与链式队列的实现-CSDN博客

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）。这通常用于删除编辑器生成的临时文件。

验证结果：

数据结构——二叉树四种遍历的实现-3

四、二叉树的遍历

热门文章

最新文章

相关课程

相关电子书