初阶数据结构之---二叉树链式结构(二叉树的构建,二叉树的前序,中序,后序和层序遍历,计算二叉树结点个数,第k层结点个数,叶子结点个数,判断是否为完全二叉树)

简介: 初阶数据结构之---二叉树链式结构(二叉树的构建,二叉树的前序,中序,后序和层序遍历,计算二叉树结点个数,第k层结点个数,叶子结点个数,判断是否为完全二叉树)

引言

本篇博客是初阶数据结构树的收尾,将会讲掉基本二叉树链式结构的具体内容和实现,包括二叉树的构建,前序遍历,中序遍历,后序遍历和层序遍历,计算二叉树结点个数,第k层结点个数,二叉树叶子结点个数,以及判断一个二叉树是否为完全二叉树。话不多说,开始我们今天的内容。

二叉树链式结构

在之前的博客中,已经讲到了关于链式二叉树相关定义的内容。

这里我们可以来看一看关于二叉树结点的定义:

typedef char BTDataType;//定义存储数据类型
typedef struct BinaryTreeNode
{
  BTDataType _data; //存储数据
  struct BinaryTreeNode* _left; //指向左孩子(左子树)
  struct BinaryTreeNode* _right; //指向右孩子(右子树)
}BTNode;

二叉树:

1. 空树

2. 非空树:由根结点,根节点的左子树,根节点的右子树组成。

从概念上可以看出,二叉树是递归定义的,后面对二叉树的构建和遍历操作都是围绕递归的思路展开。

二叉树的遍历方式及实现

学习二叉树,首先就需要学会其遍历方式,所谓二叉树遍历(Traversal)是按照某种特定的规则,依次对二叉树中的节点进行相应的操作,并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一,也是二叉树上进行其它运算的基础。

按照不同的遍历规则,二叉树的遍历方式有四种:前序遍历,中序遍历,后序遍历和层序遍历

  1. 前序遍历(Preorder Traversal 亦称先序遍历)访问根结点的操作发生在遍历其左右子树之前
  2. 中序遍历(Inorder Traversal)访问根结点的操作发生在遍历其左右子树之中(间)
  3. 后序遍历(Postorder Traversal)访问根结点的操作发生在遍历其左右子树之后

这三种遍历方式大同小异,层序遍历放到后面单独再讲。

下面仔细讲下前序遍历,弄懂前序遍历,中序和后序也就没什么难度了。

1.前序遍历

前序遍历:访问根结点的操作发生在遍历其左右子树之前

前序遍历图解:

对于上面这棵二叉树:

前序遍历结果:1 2 3 N N N 4 5 N N 6 N N

中序遍历结果:N 3 N 2 N 1 N 5 N 4 N 6 N

后序遍历结果:N N 3 N 2 N N 5 N N 6 4 1

层序遍历结果:1 2 4 3 N 5 6 N N N N N N

代码实现:

打印结点操作在遍历左右子树之前。

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{
  if (root == NULL)return; //遇到NULL结点返回
  printf("%c ", root->_data);
  BinaryTreePrevOrder(root->_left); //递归到左子树
  BinaryTreePrevOrder(root->_right); //递归到右子树
}

2.中序遍历

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

代码实现:

与前序很相似,不过打印结点操作在遍历完左子树之后。

// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
  if (root == NULL)return; //遇到NULL结点返回
  BinaryTreeInOrder(root->_left); //遍历左子树
  printf("%c ", root->_data);
  BinaryTreeInOrder(root->_right); //遍历右子树
}

3.后续遍历

后序遍历:访问根结点的操作发生在遍历其左右子树之后

代码实现:

与前序遍历相似,不过打印结点操作在遍历完左右子树之后。

// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
  if (root == NULL)return; //遇到NULL结点返回
  BinaryTreePostOrder(root->_left); //遍历左子树
  BinaryTreePostOrder(root->_right); //遍历右子树
  printf("%c ", root->_data);
}

4.层序遍历

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

二叉树层序遍历的实现,需要借助之前讲过的一个数据结构——队列

在使用队列之前,需要知道队列中存放的是什么内容,对于二叉树的结点来说,存放的应该是指向二叉树结点的指针:

// 链式结构:表示队列 
typedef BTNode* QDataType;
//队列的一个结点
typedef struct QListNode
{
  struct QListNode* _next;
  QDataType _data;
}QNode;
// 队列的结构 
typedef struct Queue
{
  QNode* _front;
  QNode* _rear;
  int size;//队列元素个数
}Queue;

看一下实现代码,这里直接复用队列的内容:

// 初始化队列 
void QueueInit(Queue* q)
{
  assert(q);
  q->_front = NULL;
  q->_rear = NULL;
  q->size = 0;
}
// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
  assert(q);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL) {
    perror("malloc fail:");
    exit(1);
  }
  newnode->_data = data;
  newnode->_next = NULL;
  if (q->_front == NULL) {
    q->_front = newnode;
    q->_rear = newnode;
  }
  else {
    q->_rear->_next = newnode;
    q->_rear = newnode;
  }
  q->size++;
}
// 队头出队列 
void QueuePop(Queue* q)
{
  assert(q);
  assert(q->_front);
  if (q->size == 1) {
    free(q->_front);
    q->_front = q->_rear = NULL;
  }
  else {
    QNode* pnext = q->_front->_next;
    free(q->_front);
    q->_front = pnext;
  }
  q->size--;
}
// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
  assert(q);
  assert(q->_front);
  return q->_front->_data;
}
// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
  assert(q);
  assert(q->_rear);
  return q->_rear->_data;
}
// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
  assert(q);
  return q->size;
}
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0 
int QueueEmpty(Queue* q)
{
  assert(q);
  return q->size == 0;
}
// 销毁队列 
void QueueDestroy(Queue* q)
{
  assert(q);
  if (q->_front == NULL)return;
  if (q->size == 1) {
    free(q->_front);
  }
  else {
    while (q->_front) {
      QNode* pnext = q->_front->_next;
      free(q->_front);
      q->_front = pnext;
    }
  }
  q->_front = q->_rear = NULL;
  q->size = 0;
}
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
  Queue qu; //创建一个队列
  QueueInit(&qu); //初始化队列
  if (root)QueuePush(&qu, root); //判断树是否为空树
  while (!QueueEmpty(&qu)) { //结束条件:队列为空
    BTNode* front = QueueFront(&qu); //取出队列中首元素
    QueuePop(&qu); //删除队首元素
    printf("%c ", front->_data); //打印遍历到的结点数据
        //将下一层结点放入队列中
    if (front->_left)QueuePush(&qu, front->_left);
    if (front->_right)QueuePush(&qu, front->_right);
  }
  printf("\n");
  QueueDestroy(&qu);//销毁队列
}

层序遍历规则:

  1. 根节点的指针入队列。
  2. 队列非空,队列中首元素出队,将队列下一层元素带入队尾(如果元素为NULL则不入队)。
  3. 如果队列为空,循环停止,遍历结束。

关于结点数和查找

计算二叉树结点个数

把二叉树递归遍历一遍就可以得到结点个数,每层结点递归时都加一。

// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
  if (root == NULL)return 0;
    //return中遍历了整个二叉树,很像递归方式求斐波那契数
  return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
}

计算叶子结点个数

也是需要遍历一遍二叉树,但是需要满足叶子结点条件(左右孩子都为NULL)的时候才会return 1计数。

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
  if (root == NULL)return 0;
  else if (root->_left == NULL && root->_right == NULL)return 1;
  return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}

计算二叉树第k层结点个数

底层逻辑依然是遍历二叉树,这里计算第k层结点个数的关键点是通过控制每层递归传入的k值判断当前结点所在层数

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
  assert(k > 0);
  if (root == NULL)return 0;
  else if (k == 1)return 1;//当k==1时说明此处遍历的结点已经是第k层
  return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1);
}

二叉树查找值为x的结点

查找的逻辑依然是遍历二叉树。

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
  if (root == NULL)return NULL;
  else if (root->_data == x)return root;
  BTNode* ret1 = BinaryTreeFind(root->_left, x);
  if (ret1)return ret1; //如果左子树找到(不为NULL),直接返回,否则返回右子树
  return BinaryTreeFind(root->_right, x);
}

二叉树的创建和销毁

二叉树的创建(前序遍历)

此处讲的二叉树创建,是以一个所给的前序遍历数组为基础(如:"ABD##E#H##CF##G##")创建的。其实创建过程的本质还是递归结构。

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
  assert(*pi <= n);
  if (a[*pi] == '#') {
    (*pi)++;
    return NULL;
  }
    //开辟结点空间
  BTNode* root = (BTNode*)malloc(sizeof(BTNode));
  if (root == NULL) { //判断空间是否开辟成功
    perror("malloc fail:");
    exit(1);
  }
  root->_data = a[(*pi)++];
    //递归构建左右子树
  root->_left = BinaryTreeCreate(a, n, pi);
  root->_right = BinaryTreeCreate(a, n, pi);
  return root;
}

二叉树的销毁

二叉树的销毁更适合基于后序遍历,从下往上依次销毁。这里并不是说前序和中序遍历无法实现销毁这一过程,只是用这两种结构实现会将问题复杂化——前中序遍历在销毁根节点后很难在找到左右孩子结点继续进行递归销毁,而后续遍历却可以规避这个问题:因为在删除根节点之前左右子树及其结点已被释放无需递归删除

// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{
  if (*root == NULL)return;
  BinaryTreeDestory(&((*root)->_left));
  BinaryTreeDestory(&((*root)->_right));
  free(*root);
  *root = NULL;
}

上述代码传递二级指针是为了方便根节点指针置空,传一级指针在函数外部置空也是一种可行的解决方式。

判断二叉树是否为完全二叉树

判断一个二叉树是否为完全二叉树,可以使用之前讲到的层序遍历的思想。

完全二叉树:除了最后一层,其他每一层结点都是完全填满的,且最后一层所有结点都集中在左侧。层序遍历的过程中,如果遇到了一个结点,其无左子树而有右子树,那么这棵树肯定不是完全二叉树;另外,如果遇到了一个结点并非左右子结点都有,那么所有接下来遍历到的结点都必须是叶子节点

我们可以在原有的层序遍历代码上修改:

这里就不再粘贴一遍队列的代码了

// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{
  Queue qu;
  QueueInit(&qu);
  if (root)QueuePush(&qu, root);
  while (!QueueEmpty(&qu)) {
    BTNode* front = QueueFront(&qu);
    QueuePop(&qu);
    if (front == NULL)break;//如果队列中出现空结点跳出循环,进行下一步判断
        //通过push将下一层结点带入队列
    QueuePush(&qu, front->_left);
    QueuePush(&qu, front->_right);
  }
  while (!QueueEmpty(&qu)) {
    BTNode* front = QueueFront(&qu);
    QueuePop(&qu);
        //如果出现非空结点则证明不是完全二叉树
    if (front) {
      QueueDestroy(&qu);
      return false;
    }
  }
  QueueDestroy(&qu);
    //如果正常跳出循环则证明为完全二叉树
  return true;
}

上述代码的主要判断逻辑是,当队列中出现一个空结点时,判断此时队列中剩余结点是否都为空:如果队列中剩余结点都为空则证明是完全二叉树;如果存在非空结点则证明不是完全二叉树

具体代码演示

这里来测试一下之前所写的二叉树的接口函数:

int main()
{
  char arr[] = "ABD##E#H##CF##G##";
  int i = 0;
  BTNode* treeroot = BinaryTreeCreate(arr, sizeof(arr) / sizeof(arr[0]), &i);
  printf("结点个数:%d\n", BinaryTreeSize(treeroot));
  printf("叶子结点个数:%d\n", BinaryTreeLeafSize(treeroot));
  int k;
    printf("输入计算第几层的结点个数:");
  scanf("%d", &k);
  printf("第k层结点个数: % d\n", BinaryTreeLevelKSize(treeroot, k));
  BTNode* node = BinaryTreeFind(treeroot, 'C');
  printf("%c\n", node->_data);
  printf("二叉树前序遍历:");
  BinaryTreePrevOrder(treeroot);
  printf("\n");
  printf("二叉树中序遍历:");
  BinaryTreeInOrder(treeroot);
  printf("\n");
  printf("二叉树后序遍历:");
  BinaryTreePostOrder(treeroot);
  printf("\n");
  printf("二叉树层序遍历:");
  BinaryTreeLevelOrder(treeroot);
  printf("是否为完全二叉树:%d",BinaryTreeComplete(treeroot));
  BinaryTreeDestory(&treeroot);
  return 0;
}

下面是所创建树的结构:

下面是运行结果:

结语

关于二叉树链式结构的内容到这里就结束了。本篇博客围绕二叉树的遍历,结点个数计算以及数值查找等内容展开。关于二叉树更多有趣的内容还远远不止这些,不过再次深入时就会以C++的方式来给大家呈现,如果对后续内容感兴趣的话,还请大家多多关注博主,感谢大家的支持。

相关文章
|
7月前
|
存储 算法 Java
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构,广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型(如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等)及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历,并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力,优化算法设计。
189 10
 算法系列之数据结构-二叉树
|
9月前
|
Java C++
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
185 12
|
9月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
166 10
|
9月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
261 3
|
10月前
|
数据库
数据结构中二叉树,哈希表,顺序表,链表的比较补充
二叉搜索树,哈希表,顺序表,链表的特点的比较
数据结构中二叉树,哈希表,顺序表,链表的比较补充
|
11月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
880 9
|
11月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
223 59
|
4月前
|
编译器 C语言 C++
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因,涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问,修改了变量`i`的值,导致`for`循环条件始终为真,形成死循环。原因是VS2022栈区从低地址到高地址分配内存,`arr`数组与`i`相邻,`arr[15]`恰好覆盖`i`的地址。而在VS2019中,栈区先分配高地址再分配低地址,因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致,需避免数组越界以确保代码健壮性。
52 0
栈区的非法访问导致的死循环(x64)
232.用栈实现队列,225. 用队列实现栈
在232题中,通过两个栈(`stIn`和`stOut`)模拟队列的先入先出(FIFO)行为。`push`操作将元素压入`stIn`,`pop`和`peek`操作则通过将`stIn`的元素转移到`stOut`来实现队列的顺序访问。 225题则是利用单个队列(`que`)模拟栈的后入先出(LIFO)特性。通过多次调整队列头部元素的位置,确保弹出顺序符合栈的要求。`top`操作直接返回队列尾部元素,`empty`判断队列是否为空。 两题均仅使用基础数据结构操作,展示了栈与队列之间的转换逻辑。
|
9月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
334 77