仅不到五万字轻松了解二叉树和堆 3-阿里云开发者社区

四、二叉树链式结构及实现

💦 前置说明

普通二叉树的增删查改复杂且没有意义，所以我们并不打算学习它的增删查改，主要是学习它的结构
在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。
由于现在对二叉树结构掌握还不够深入，为了降低学习成本，此处手动快速创建一棵简单的二叉树，以此快速进入二叉树操作学习，等二叉树结构了解的差不多时，我们反过头再来研究二叉树真正的创建方式。

⚠ 以下代码并不是创建二叉树的方式，真正创建二叉树方式后序详解重点讲解

❗ 回顾二叉树 ❕

1️⃣ 空树

2️⃣ 非空：根节点，根节点的左子树、根节点的右子树组成

💨 从概念中可以看出，二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的。

typedef int BTDataType;
typedef struct BinaryTreeNode
{
  BTDataType _data;
  struct BinaryTreeNode* _left;
  struct BinaryTreeNode* _right; 
}BTNode; 
BTNode* CreatBinaryTree()
{
  BTNode* node1 = BuyNode('A');
  BTNode* node2 = BuyNode('B');
  BTNode* node3 = BuyNode('C');
  BTNode* node4 = BuyNode('D');
  BTNode* node5 = BuyNode('E');
  BTNode* node6 = BuyNode('F');
  node1->_left = node2;
  node1->_right = node3;
  node2->_left = node4;
  node3->_left = node5;
  node3->_right = node6;
  return node1; 
 }

💦 二叉树的遍历

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

其实这种就是递归的思想，且在现实生活中也经常使用到 —— 比如 1 位校长要统计学校的人数，他不可能亲自去挨个数，一般是通过院长、系主任、辅导员、班长、舍长的层层反馈才得到结果的

1️⃣ 前序遍厉：根左子树右子树

2️⃣ 中序遍厉：左子树根右子树

3️⃣ 后序遍厉：左子树右子树根

4️⃣ 层序遍厉：一层一层的遍

在之前就提到过深度和广度，其实指的就是这个：

1️⃣ 深度优先遍厉：前序遍厉、中序遍厉、后序遍厉，注意有些说法只认同前序遍厉

2️⃣ 广度优先遍厉：层序遍厉

1、前序、中序以及后序遍历

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

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

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

由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

// 二叉树前序遍历
void PreOrder(BTNode* root);
// 二叉树中序遍历
void InOrder(BTNode* root);
// 二叉树后序遍历
void PostOrder(BTNode* root);

❗ 实现 ❕

#include<stdio.h>
#include<stdlib.h>
typedef int BTDataType;
typedef struct BinaryTreeNode
{
  BTDataType _data;
  struct BinaryTreeNode* _left;
  struct BinaryTreeNode* _right; 
}BTNode; 
BTNode* BuyNode(BTDataType x)
{
  BTNode* node = malloc(sizeof(BTNode));
  node->_data = x;
  node->_left = NULL;
  node->_right = NULL;
  return node;
}
BTNode* CreatBinaryTree()
{
  BTNode* node1 = BuyNode('A');
  BTNode* node2 = BuyNode('B');
  BTNode* node3 = BuyNode('C');
  BTNode* node4 = BuyNode('D');
  BTNode* node5 = BuyNode('E');
  BTNode* node6 = BuyNode('F');
  node1->_left = node2;
  node1->_right = node3;
  node2->_left = node4;
  node3->_left = node5;
  node3->_right = node6;
  return node1; 
 }
//二叉树前序遍历
void PreOrder(BTNode* root)
{
  if(root == NULL)
  {
    printf("NULL ");
    return;
  }
  printf("%c ", root->_data);
  PreOrder(root->_left);
  PreOrder(root->_right);
}
//二叉树中序遍历
void InOrder(BTNode* root)
{
  if(root == NULL)
  {
    printf("NULL ");
    return;
  }
  InOrder(root->_left);
  printf("%c ", root->_data);
  InOrder(root->_right);
}
//二叉树后序遍历
void PostOrder(BTNode* root)
{
  if(root == NULL)
  {
    printf("NULL ");
    return;
  }
  PostOrder(root->_left);
  PostOrder(root->_right);
  printf("%c ", root->_data);
}
//构建二叉树
void TestTree()
{
  BTNode* root = CreatBinaryTree();
  PreOrder(root);
}
int main()
{
  TestTree();
  return 0;
}

📝 分析：

以上真正的核心代码是 PreOrder、InOrder、PostOrder 函数的递归调用短短几行代码却执行了如此复杂的计算，这里豌豆太懒了就只画一个展开图：

❗ PreOrder ❕

2、层序遍历

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

// 层序遍历 - 在下面实现
void LevelOrder(BTNode* root);

3、概念选择题 (如何利用已知限有条件构建二叉树)

1.某完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH 。该完全二叉树的前序序列为（）

A. ABDHECFG

B. ABCDEFGH

C. HDBEAFCG

D. HDEBFGCA

📝 分析

所以选择 A 选项

2.二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK; 中序遍历：HFIEJKG; 则二叉树根结点为（）

A. E

B. F

C. G

D. H

📝 分析

根据这棵树的先序遍厉、中序遍厉并不能重建 (其实可以重建的，详情看下题) 这棵树。但是这里并不需要重建，因为先序遍厉是从根开始的。

所以选择 A 选项

–

3.设—课二叉树的中序遍历序列: badce，后序遍历序列: bdeca, 则二叉树前序遍历序列为（）

A. adbce

B. decab

C. debac

D. abcde

📝 分析

这里在没有 # 的情况下，满足以下条件即可构建出二叉树

所以选择 D 选项

4.某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF，则按层次输出 (同一层从左到右) 的序列为（）

A. FEDCBA

B. CBAFED

C. DEFCBA

D. ABCDEF

📝 分析

显然这道题作为选择题来说一眼就能知道答案：根据它的后序遍厉知道根是 F

所以选择 A 选项

❓ 如果知道了前中后序遍历序列，不包括 #(空) ，能否构建一棵二叉树 ❔

不能构建，但满足以下的条件即可构建：

💦 节点个数以及高度等

❓ 实现以下接口 ❔

// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
//二叉树深度/高度
int BinaryTreeDepth(BTNode* root)
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);

❗ 实现代码 ❕

❤ BinaryTreeSize ❤

🔑 核心思想1 ：使用前序 || 中序 || 后序遍历，全局变量记录

❌ 但是以下代码有 Bug ：如果采用前序重复遍历 2 次

✔ 经查，问题出在全局变量上，这里只需要在第 2 次遍历时置 0 即可

⚠ 在以后的知识面更大后，其实你会发现这种操作还有线程安全的问题

🔑 核心思想 2：函数使用带返回值的方式，其内部的递归本质上是一个后序遍厉

❤ BinaryTreeLeafSize ❤

🔑 核心思想：以 left 和 right 为标志，如果都为 NULL，则累加

❤ BinaryTreeLevelKSize ❤

🔑 核心思想：求当前树的第 k 层 = 左子树的第 k - 1 层 +　右子树的第 k - 1 层 (当 k = 1 时，说明此层就是目标层)

❤ BinaryTreeDepth ❤

🔑 核心思想：当前树的深度 = max (左子树的深度，右子树的深度) + 1

❤ BinaryTreeFind ❤

🔑 核心思想：

1、先判断是不是当前节点，是就返回；

2、先去左树找，找到就返回

3、左树没找到，再找右树

#include<stdio.h>
#include<stdlib.h>
typedef int BTDataType;
typedef struct BinaryTreeNode
{
  BTDataType data;
  struct BinaryTreeNode* left;
  struct BinaryTreeNode* right;
}BTNode;
BTNode* BuyNode(BTDataType x)
{
  BTNode* node = malloc(sizeof(BTNode));
  node->data = x;
  node->left = NULL;
  node->right = NULL;
  return node;
}
// 二叉树节点个数
  //1、前序递归遍历
int sz1 = 0;
void BinaryTreeSize1(BTNode* root)
{
  if (root == NULL)
    return;
  else
    sz1++;
  BinaryTreeSize1(root->left);
  BinaryTreeSize1(root->right);
}
//2、中序递归遍历
int sz2 = 0;
void BinaryTreeSize2(BTNode* root)
{
  if (root == NULL)
    return;
  BinaryTreeSize2(root->left);
  if (root != NULL)
    sz2++;
  BinaryTreeSize2(root->right);
}
//3、后序递归遍历
int sz3 = 0;
void BinaryTreeSize3(BTNode* root)
{
  if (root == NULL)
    return;
  BinaryTreeSize3(root->left);
  BinaryTreeSize3(root->right);
  if (root != NULL)
    sz3++;
}
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
  return root == NULL ? 0 : 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
//二叉树叶子节点个数
int BinaryTreeLeaSize(BTNode* root)
{
  if (root == NULL)
  {
    return 0;
  }
  else if (root->left == NULL && root->right == NULL)
  {
    return 1;
  }
  else
  {
    return BinaryTreeLeaSize(root->left) + BinaryTreeLeaSize(root->right);
  }
}
//二叉树第k层节点个数
int BinaryTreeLeveLKSize(BTNode* root, int k)
{
  if (root == NULL)
  {
    return 0;
  }
  if (k == 1)
  {
    return 1;
  }
  return BinaryTreeLeveLKSize(root->left, k - 1) + BinaryTreeLeveLKSize(root->right, k - 1);
}
//二叉树的深度/高度 
int BinaryTreeDepth(BTNode* root)
{
  if (root == NULL)
  {
    return 0;
  }
  int leftDepth = BinaryTreeDepth(root->left);
  int rightDepth = BinaryTreeDepth(root->right);
  return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
  if (root == NULL)
  {
    return NULL;
  }
  if (root->data == x)
  {
    return root;
  }
  BTNode* retleft = BinaryTreeFind(root->left, x);
  if (retleft)
  {
    return retleft;
  }
  BTNode* retright = BinaryTreeFind(root->right, x);
  if (retright)
  {
    return retright;
  }
  return NULL;
}
BTNode* CreatBinaryTree()
{
  BTNode* node1 = BuyNode('A');
  BTNode* node2 = BuyNode('B');
  BTNode* node3 = BuyNode('C');
  BTNode* node4 = BuyNode('D');
  BTNode* node5 = BuyNode('E');
  BTNode* node6 = BuyNode('F');
  node1->left = node2;
  node1->right = node3;
  node2->left = node4;
  node3->left = node5;
  node3->right = node6;
  return node1;
}
void PreOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("NULL ");
    return;
  }
  printf("%c ", root->data);
  PreOrder(root->left);
  PreOrder(root->right);
}
int main()
{
  BTNode* root = CreatBinaryTree();
  //遍厉前中后序输出二叉树节点的个数
  BinaryTreeSize1(root);
  BinaryTreeSize2(root);
  BinaryTreeSize3(root);
  printf("BinaryTreeSize:%d\n", sz1);
  printf("BinaryTreeSize:%d\n", sz2);
  printf("BinaryTreeSize:%d\n", sz3);
  printf("-----------------cur-----------------\n");
  //优化二叉树节点的个数
  printf("BinaryTreeSize:%d\n", BinaryTreeSize(root));
  printf("-----------------cur-----------------\n");
  //二叉树叶子节点个数
  printf("BinaryTreeLeaSize:%d\n", BinaryTreeLeaSize(root));
  printf("-----------------cur-----------------\n");
  //二叉树第k层节点个数
  printf("BinaryTreeLeveLKSize:%d\n", BinaryTreeLeveLKSize(root, 3));
  printf("-----------------cur-----------------\n");
  //二叉树的深度/高度 
  printf("BinaryTreeDepth:%d\n", BinaryTreeDepth(root));
  printf("-----------------cur-----------------\n");
  // 二叉树查找值为x的节点
  BTNode* ret = BinaryTreeFind(root, 'D');
  if(ret)
  {
    printf("找到了\n");
  }
  else
  {
    printf("没找到\n");
  }
  PreOrder(root);
  return 0;
}

💦 二叉树基础oj练习

1、单值二叉树＜难度系数⭐＞

📝 题述：如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。只有给定的树是单值二叉树时，才返回 true；否则返回 false。

💨 示例 1：

输入：[1,1,1,1,1,null,1]

输出：true

💨 示例 2：

输入：[2,2,2,5,2]

输出：false

⚠ 注意：

1️⃣ 给定树的节点数范围是 [1, 100]。

2️⃣ 每个节点的值都是整数，范围为 [0, 99] 。

🧷 平台：Visual studio 2017 && windows

🔑 核心思想：

在数学中大家都知道等号具有传递性，如 a = b , b = c，那么 a = c 。

那么这里

a == b && a == c

b == d && b == e

… …

在每层栈帧中：如果那个节点为空返回 true；判断左右子树与根，如果不相等返回 false ；相等继续递归

leetcode原题

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int BTDataType;
typedef struct TreeNode 
{
  int val;
  struct TreeNode *left;
  struct TreeNode *right;
}BTNode;
//单值二叉树
bool isUnivalTree(struct TreeNode* root) {
  if (root == NULL)
  {
    return true;
  }
  //左树不为空且左树不等于根val
  if (root->left && root->left->val != root->val)
  {
    return false;   
  }
  //右树不为空且右树不等于根val
  if (root->right && root->right->val != root->val)
  {
    return false;
  }
  //递归
  return isUnivalTree(root->left) && isUnivalTree(root->right);
}
//malloc空间
BTNode* BuyNode(BTDataType x)
{
  BTNode* node = malloc(sizeof(BTNode));
  node->val = x;
  node->left = NULL;
  node->right = NULL;
  return node;
}
//创建树
BTNode* CreatBinaryTree()
{
  BTNode* node1 = BuyNode('A');
  BTNode* node2 = BuyNode('A');
  BTNode* node3 = BuyNode('A');
  BTNode* node4 = BuyNode('A');
  BTNode* node5 = BuyNode('A');
  BTNode* node6 = BuyNode('A');
  node1->left = node2;
  node1->right = node3;
  node2->left = node4;
  node2->right = node5;
  node3->right = node6;
  return node1;
}
int main()
{
  BTNode* root = CreatBinaryTree();
  printf("%d\n", isUnivalTree(root));
  return 0;
}

2、检查两颗树是否相同＜难度系数⭐＞

📝 题述：给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

💨 示例 1：

输入：p = [1,2,3], q = [1,2,3]

输出：true

💨 示例 2：

输入：p = [1,2], q = [1,null,2]

输出：false

💨 示例 3：

输入：p = [1,2,1], q = [1,1,2]

输出：false

⚠ 注意：

1️⃣ 两棵树上的节点数目都在范围 [0, 100] 内

2️⃣ -10⁴ <= Node.val <= 10⁴

🧷 平台：Visual studio 2017 && windows

🔑 核心思想：在递归时每一层函数的栈帧中存在这样的条件：p 为空，q 也为空，返回 true；p 或者 q 只有一个为空，返回 false；p 和 q 的 val 不等，返回 false；否则 p 和 q 的 val 是相等的才递归

leetcode原题

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int BTDataType;
typedef struct TreeNode 
{
  int val;
  struct TreeNode *left;
  struct TreeNode *right;
}BTNode;
//malloc空间
BTNode* BuyNode(BTDataType x)
{
  BTNode* node = malloc(sizeof(BTNode));
  node->val = x;
  node->left = NULL;
  node->right = NULL;
  return node;
}
//创建树1
BTNode* CreatBinaryTree1()
{
  BTNode* node1 = BuyNode(1);
  BTNode* node2 = BuyNode(2);
  BTNode* node3 = BuyNode(3);
  node1->right = node2;
  node2->left = node3;
  return node1;
}
//创建树2
BTNode* CreatBinaryTree2()
{
  BTNode* node1 = BuyNode(1);
  BTNode* node2 = BuyNode(2);
  BTNode* node3 = BuyNode(3);
  node1->right = node2;
  node2->left = node3;
  return node1;
}
//相同的树
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
  //p为空，q也为空
  if (p == NULL && q == NULL)
    return true;
  //p和q只有1个为空
  if (p == NULL || q == NULL)
    return false;
  //p和q的val不等
  if (p->val != q->val)
    return false;
  //相等递归
  return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
int main()
{
  BTNode* root1 = CreatBinaryTree1();
  BTNode* root2 = CreatBinaryTree2();
  printf("%d\n", isSameTree(root1, root2));
  return 0;
}

3、对称二叉树＜难度系数⭐＞

📝 题述：给定一个二叉树，检查它是否是镜像对称的。

💨 示例 1：

[1,2,2,3,4,4,3] 是镜像对称的

💨 示例 2：

[1,2,2,null,3,null,3] 则不是镜像对称的

🧷 平台：Visual studio 2017 && windows

🔑 核心思想：在递归时每一层函数的栈帧中存在这样的条件：root1 和 root2 同时为空，返回 true；root1 和 root2 只有一个为空返回 false；root1 和 root2 的 val 不等，返回 false；否则 root1 和 root2 是相等的继续递归。

leetcode原题

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int BTDataType;
typedef struct TreeNode 
{
  int val;
  struct TreeNode *left;
  struct TreeNode *right;
}BTNode;
//malloc空间
BTNode* BuyNode(BTDataType x)
{
  BTNode* node = malloc(sizeof(BTNode));
  node->val = x;
  node->left = NULL;
  node->right = NULL;
  return node;
}
//创建树
BTNode* CreatBinaryTree()
{
  BTNode* node1 = BuyNode(1);
  BTNode* node2 = BuyNode(2);
  BTNode* node3 = BuyNode(2);
  BTNode* node4 = BuyNode(3);
  BTNode* node5 = BuyNode(4);
  BTNode* node6 = BuyNode(4);
  BTNode* node7 = BuyNode(3);
  node1->left = node2;
  node1->right = node3;
  node2->left = node4;
  node2->right = node5;
  node3->left = node6;
  node3->right = node7;
  return node1;
}
//实现递归的子函数
bool _isSymmetric(struct TreeNode* root1, struct TreeNode* root2) {
  //root1和root2同时为空
  if (root1 == NULL && root2 == NULL)
    return true;
  //root1和root2只有一个为空
  if (root1 == NULL || root2 == NULL)
    return false;
  //root1和root2的val不等
  if (root1->val != root2->val)
    return false;
  //相等继续递归
  return _isSymmetric(root1->left, root2->right) && _isSymmetric(root1->right, root2->left);
}
//对称二叉树
bool isSymmetric(struct TreeNode* root) {
  //空树就返回true
  if (root == NULL)
    return true;
  //否则调用子函数判断左右子树
  return _isSymmetric(root->left, root->right);
}
int main()
{
  BTNode* root = CreatBinaryTree();
  printf("%d\n", isSymmetric(root));
  return 0;
}

仅不到五万字轻松了解二叉树和堆 3

四、二叉树链式结构及实现

💦 前置说明

💦 二叉树的遍历

1、前序、中序以及后序遍历

2、层序遍历

3、概念选择题 (如何利用已知限有条件构建二叉树)

💦 节点个数以及高度等

💦 二叉树基础oj练习

1、单值二叉树＜难度系数⭐＞

2、检查两颗树是否相同＜难度系数⭐＞

3、对称二叉树＜难度系数⭐＞

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

仅不到五万字轻松了解二叉树和堆 3

四、二叉树链式结构及实现

💦 前置说明

💦 二叉树的遍历

1、前序、中序以及后序遍历

2、层序遍历

3、概念选择题 (如何利用已知限有条件构建二叉树)

💦 节点个数以及高度等

💦 二叉树基础oj练习

1、单值二叉树＜难度系数⭐＞

2、检查两颗树是否相同＜难度系数⭐＞

3、对称二叉树＜难度系数⭐＞

热门文章

最新文章

相关电子书