【数据结构二叉树的链式存储讲解及前中后序遍历和层次遍历】

简介: 二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。

1. 链式存储


1.1 概念

二叉树的链式存储结构是指,


用链表来表示一棵二叉树,


即用链来指示元素的逻辑关系。


通常的方法是链表中每个结点由三个域组成

数据域和左右指针域,

左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。

链式结构又分为二叉链和三叉链,


当前我们学习中一般都是二叉链,


后面学到高阶数据结构如红黑树等会用到三叉链。


图示:

image.png


image.png



image.png


节点定义代码:


// 二叉链
struct BinaryTreeNode
{
  struct BinTreeNode* pLeft;  // 指向当前节点左孩子
  struct BinTreeNode* pRight; // 指向当前节点右孩子
  BTDataType _data; // 当前节点值域
}
// 三叉链
struct BinaryTreeNode
{
  struct BinTreeNode* pParent; // 指向当前节点的双亲
  struct BinTreeNode* pLeft;  // 指向当前节点左孩子
  struct BinTreeNode* pRight; // 指向当前节点右孩子
  BTDataType _data; // 当前节点值域
};

1.2 应用

1.2.1 前序/中序/后序的递归结构遍历(深度遍历)简述

前序/中序/后序的递归结构遍历:是根据访问结点操作发生位置命名


NLR:前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。


LNR:中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中(间)。


LRN:后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。


由于被访问的结点必是某子树的根,所以N(Node)、L(Left subtree)和R(Right subtree)又可解释为根、根的左子树和根的右子树。


NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。


图示:此图可以较好的阐述前中后序遍历,根据访问顺序不同而结果不同



image.png

所以在写代码时只要更改访问顺序就能分别实现前中后序遍历。


代码实现:


定义节点:


typedef char BTDataType;
typedef struct BinaryTreeNode
{
  struct BinaryTreeNode* left;
  struct BinaryTreeNode* right;
  BTDataType data;
}BTNode;

创造节点:


这里仅是模拟上图情况


BTNode* BuyNode(BTDataType x)
{
  BTNode* node = (BTNode*)malloc(sizeof(BTNode));
  if (node == NULL)
  {
  printf("malloc fail\n");
  exit(-1);
  }
  node->data = x;
  node->left = node->right = NULL;
  return node;
}
BTNode* CreatBinaryTree()
{
  BTNode* nodeA = BuyNode('A');
  BTNode* nodeB = BuyNode('B');
  BTNode* nodeC = BuyNode('C');
  BTNode* nodeD = BuyNode('D');
  BTNode* nodeE = BuyNode('E');
  BTNode* nodeF = BuyNode('F');
  nodeA->left = nodeB;
  nodeA->right = nodeC;
  nodeB->left = nodeD;
  nodeB->right = nodeE;
  nodeC->right = nodeF;
  return nodeA;
}



1.2.1.1 前序遍历的实现

二叉树前序遍历函数:


先访问根节点再访问左孩子和右孩子,若为NULL则返回


void PreOrder(BTNode* root)
{
   if (root == NULL){
      printf("NULL ");
      return;
   }
   printf("%c ", root->data);
   PreOrder(root->left);
   PreOrder(root->right);
}


1.2.1.2中序遍历的实现

二叉树中序遍历函数:


先一直访问左孩子再访问根节点再访问右孩子,若为NULL则返回


void InOrder(BTNode* root)
{
   if (root == NULL){
      printf("NULL ");
      return;
   }
   InOrder(root->left);
   printf("%C ", root->data);
   InOrder(root->right);
}


1.2.1.3 后序遍历的实现

二叉树后序遍历函数:


先访问完它的左孩子和右孩子再访问根节点,若为NULL则返回

void PostOrder(BTNode* root)
{
    if (root == NULL){
       printf("NULL ");
       return;
    }
    PostOrder(root->left);
    PostOrder(root->right);
    printf("%C ", root->data);
}


主函数:


int main()
{
  BTNode* root = CreatBinaryTree();
  PreOrder(root);
  printf("\n");
  InOrder(root);
  printf("\n");
    PostOrder(root);
    printf("\n");
    return 0;
}


可能你到了这里还是觉得模糊,不太理解,我画个图你就理解了:


前序遍历解析图:

image.png



中序后序也是相同的原理,不过访问根节点的顺序不同而已。


1.2.1.4 根据遍历结果重构二叉树

这也是考研常考内容


根据前中序遍历结果推断后序遍历结果或者画出这棵树

根据中后序遍历结果推断前序遍历结果或者画出这棵树

其实都是一样的思路,把树画出来,再求前or后序遍历顺序


在这里通过两个例子来带你学习怎么推算:


1.2.2 已知前中序遍历顺序求后序遍历顺序

1.若某二叉树的前遍历访问顺序是abdgcefh,中序遍历顺序是dgbaechf,则后序遍历的访问顺序是什么。


思路


前序遍历,先访问根节点,再访问左子树,最后访问右子树

故第1个访问的节点就是整个树的根节点

中序遍历,先访问左子树,再访问根节点,最后访问右子树

已知整个树的根节点,中序遍历顺序中以前序遍历访问的第一个节点为限,左边是左子树,右边是右子树。

再反复利用前序遍历结果,反复判断左右子树,直至叶子节点

是不是感觉好复杂?


画图带你理解:


前序遍历的第一个元素,就是树根,此处是a。


那么就能构造出下图所示的二叉树


image.png


根据“a”在中序出现的位置,将中序遍历的结果分成左右两棵子树,它们的中序遍历分别是:

{d,g,b} 和{e,c,h,f};这两棵子树的前序结果:{b,d,g}和{c,e,f,h}。


现在我们重复步骤1、2,先构造左子树,再构建右子树。


如下图所示:

image.png



故最终树结构为

image.png



此时再根据树结构来推算后序遍历的顺序为:gdbehfca


1.2.3 已知中后序遍历顺序求前序遍历顺序

已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG 和 DECBHGFA,请求前序遍历顺序。


和上面的思路相同:


思路


后序遍历,先访问左子树,再访问右子树,最后访问根节点

故最后1个访问的节点就是整个树的根节点

中序遍历,先访问左子树,再访问根节点,最后访问右子树

已知整个树的根节点,中序遍历顺序中以后序遍历访问的最后一个节点为限,左边是左子树,右边是右子树。

再反复利用后序遍历结果,反复判断左右子树,直至叶子节点

同样画图演示:


后序遍历的最后一个元素,就是树根,此处是A。


那么就能构造出下图所示的二叉树


image.png


根据“A”在中序出现的位置,将中序遍历的结果分成左右两棵子树,它们的中序遍历分别是:

{B,D,C,E} 和{F,H,G};这两棵子树的后序结果:{D,E,C,B}和{H,G,F}。


现在我们重复步骤1、2,先构造右子树,再构建左子树。


如下图所示:


image.png


故最终树结构为

image.png



此时再根据树结构来推算前序遍历的顺序为:ABCDEFGH


1.2.4 已知前后序遍历顺序可以求中序遍历顺序吗?

不可以。


因为它不能重构出唯一的二叉树。


举例:


情况一:


假设前序结果是{C,A,B},后序结果是{B,A,C}


那么二叉树的结构可能如下:



image.png


image.png

这种情况下,二叉树并不唯一;

情况二:


假设前序结果是{C,A,B},后序结果是{A,B,C}


那么二叉树的结构如下:


image.png


1.2.5 层次遍历(广度遍历)

除了先序遍历、中序遍历、后序遍历外,还可以对二叉树进行层序遍历。


设二叉树的根节点所在层数为1,层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树根节点,然后从左到右访问第2层上的节点,接着是第三层的节点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历。


图示:自上而下,自左至右逐层访问树的结点




思路

你看我们要将每一层从上到下,从左至右,依次访问。


所以想到了使用队列这一数据结构的性质,


先入根,当前节点出来,把孩子带进去,


这样上一层节点出的时候,带入下一层,


直至队列为空,说明最后一层没有节点了,遍历结束。


图示

注意:此图队列中(黑色框中)红色元素为将要Pop的元素,然后右边是其左右孩子节点的进入,为空则不进入。



image.png

如上,这就实现了层次遍历


代码实现

得实现两个数据结构,而且注意进入队列中的元素是树的节点


队列的实现就不过多赘述了,相信各位看官可以自行理解~~


层次遍历的代码会做注释方便理解。


Test.c

先构建一棵树:

typedef char BTDataType;
typedef struct BinaryTreeNode
{
   struct BinaryTreeNode* left;
   struct BinaryTreeNode* right;
   BTDataType data;
}BTNode;
BTNode* BuyNode(BTDataType x)
{
   BTNode* node = (BTNode*)malloc(sizeof(BTNode));
   if (node == NULL)
   {
      printf("malloc fail\n");
      exit(-1);
   }
   node->data = x;
   node->left = node->right = NULL;
   return node;
}
BTNode* CreatBinaryTree()
{
   BTNode* nodeA = BuyNode('A');
   BTNode* nodeB = BuyNode('B');
   BTNode* nodeC = BuyNode('C');
   BTNode* nodeD = BuyNode('D');
   BTNode* nodeE = BuyNode('E');
   BTNode* nodeF = BuyNode('F');
   nodeA->left = nodeB;
   nodeA->right = nodeC;
   nodeB->left = nodeD;
   nodeB->right = nodeE;
   nodeC->right = nodeF;
   return nodeA;
}


层次遍历函数:


void BinaryTreeLevelOrder(BTNode* root)
{
   if (root == NULL)//节点为空则返回
      return;
   Queue q;
   QueueInit(&q);//队列初始化
   QueuePush(&q, root);//入根节点
   while (!QueueEmpty(&q))//如果队列不为空就继续
   {
      BTNode* front = QueueFront(&q);
      //把队头元素做备份,方便后面调用其左右孩子节点
      QueuePop(&q);
      printf("%c ", front->data);
      // 孩子存在则带进队列,
      if (front->left)
         QueuePush(&q, front->left);
      if (front->right)
         QueuePush(&q, front->right);
   }
   printf("\n");
   QueueDestroy(&q);//销毁队列
}


二叉树销毁函数:


注意:这里销毁的原理是:后序列遍历,将节点一个个free掉。


void BinaryTreeDestory(BTNode* root)
{
   if (root == NULL)
   {
      return;
   }
   BinaryTreeDestory(root->left);
   BinaryTreeDestory(root->right);
   free(root);
}


主函数:


int main()
{
  BTNode* root = CreatBinaryTree();
  BinaryTreeLevelOrder(root);
  BinaryTreeDestory(root);
  root = NULL;
  return 0;
}


Queue.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
// 前置声明
struct BinaryTreeNode;
typedef struct BinaryTreeNode* QDataType;
//数据类型为树的节点
typedef struct QueueNode
{
  struct QueueNode* next;
  QDataType data;
}QueueNode;
typedef struct Queue
{
  QueueNode* head;
  QueueNode* tail;
}Queue;
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
bool QueueEmpty(Queue* pq);



Queue.c

#include "Queue.h"
void QueueInit(Queue* pq)
{
   assert(pq);
   pq->head = NULL;
   pq->tail = NULL;
}
void QueueDestroy(Queue* pq)
{
   assert(pq);
   QueueNode* cur = pq->head;
   while (cur != NULL)
   {
      QueueNode* next = cur->next;
      free(cur);
      cur = next;
   }
   pq->head = pq->tail = NULL;
}
void QueuePush(Queue* pq, QDataType x)
{
   assert(pq);
   QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
   newnode->data = x;
   newnode->next = NULL;
   if (pq->head == NULL)
   {
      pq->head = pq->tail = newnode;
   }
   else
   {
      pq->tail->next = newnode;
      pq->tail = newnode;
   }
}
void QueuePop(Queue* pq)
{
   assert(pq);
   assert(!QueueEmpty(pq));
   QueueNode* next = pq->head->next;
   free(pq->head);
   pq->head = next;
   if (pq->head == NULL)
   {
      pq->tail = NULL;
   }
}
QDataType QueueFront(Queue* pq)
{
   assert(pq);
   assert(!QueueEmpty(pq));
   return pq->head->data;
}
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->head == NULL;
}



后记


这一篇讲述了二叉树链式存储,前中后序遍历,以及怎么根据前中,后中的遍历结果推出二叉树的结构,和层次遍历的实现。


下一篇将讲述一些二叉树的OJ题,感谢支持,如果有什么问题,可在评论区提出!


相关文章
|
5天前
|
Java C++
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
31 12
|
5天前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
31 10
|
5天前
|
存储 算法 C++
【C++数据结构——图】图的邻接矩阵和邻接表的存储(头歌实践教学平台习题)【合集】
本任务要求编写程序实现图的邻接矩阵和邻接表的存储。需掌握带权有向图、图的邻接矩阵及邻接表的概念。邻接矩阵用于表示顶点间的连接关系,邻接表则通过链表结构存储图信息。测试输入为图的顶点数、边数及邻接矩阵,预期输出为Prim算法求解结果。通关代码提供了完整的C++实现,包括输入、构建和打印邻接矩阵与邻接表的功能。
28 10
|
5天前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
23 2
|
5天前
|
数据采集 存储 算法
【C++数据结构——图】图的遍历(头歌教学实验平台习题) 【合集】
本文介绍了图的遍历算法,包括深度优先遍历(DFS)和广度优先遍历(BFS)。深度优先遍历通过递归方式从起始节点深入探索图,适用于寻找路径、拓扑排序等场景;广度优先遍历则按层次逐层访问节点,适合无权图最短路径和网络爬虫等应用。文中提供了C++代码示例,演示了如何实现这两种遍历方法,并附有测试用例及结果,帮助读者理解和实践图的遍历算法。
17 0
|
2月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
265 9
|
2月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
42 1
|
5天前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
116 75
|
5天前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
27 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
5天前
|
存储 C语言 C++
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
30 9