【数据结构与算法】二叉树（下）-阿里云开发者社区

👉二叉树链式结构的实现👈

前置说明

在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。由于现在大家对二

叉树结构掌握还不够深入，为了降低大家学习成本，此处手动快速创建一棵简单的二叉树，快速进入二叉树

操作学习，等二叉树结构了解的差不多时，我们反过头再来研究二叉树真正的创建方式。

typedef int BTDataType;
typedef struct BinaryTreeNode
{
  BTDataType data;
  struct BinaryTreeNode* left;
  struct BinaryTreeNode* right;
}BTNode;
BTNode* CreateTree()
{
  BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));
  assert(n1);
  BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));
  assert(n2);
  BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));
  assert(n3);
  BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));
  assert(n4);
  BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));
  assert(n5);
  BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));
  assert(n6);
  BTNode* n7 = (BTNode*)malloc(sizeof(BTNode));
  assert(n7);
  n1->data = 1;
  n2->data = 2;
  n3->data = 3;
  n4->data = 4;
  n5->data = 5;
  n6->data = 6;
  n1->left = n2;
  n1->right = n4;
  n2->left = n3;
  n2->right = NULL;
  n3->left = NULL;
  n3->right = NULL;
  n4->left = n5;
  n4->right = n6;
  n5->left = NULL;
  n5->right = NULL;
  n6->left = NULL;
  n6->right = NULL;
  return n1;
}

注意：上述代码并不是创建二叉树的方式，真正创建二叉树方式后序详解重点讲解。看二叉树基本操作前，我们先回顾下二叉树的概念，二叉树是由空树或者根节点、左子树和右子树组成的。

二叉树的遍历

学习二叉树结构，最简单的方式就是遍历。所谓二叉树

遍历 (Traversal) 是按照某种特定的规则，依次对二叉

树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。遍历

是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

按照规则，二叉树的遍历有：前序 / 中序 / 后序的递归结构遍历：

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

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

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

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

根、根的左子树和根的右子树。NLR、LNR 和 LRN分别又称为先根遍历、中根遍历和后根遍历。

1.前序遍历

// 二叉树前序遍历
void PreOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("NULL ");
    return;
  }
  printf("%d ", root->data);
  PreOrder(root->left);
  PreOrder(root->right);
}

前序遍历递归图解

2.中序遍历

// 二叉树中序遍历
void InOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("NULL ");
    return;
  }
  InOrder(root->left);
  printf("%d ", root->data);
  InOrder(root->right);
}

中序遍历递归图解

3.后序遍历

// 二叉树后序遍历
void PostOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("NULL ");
    return;
  }
  PostOrder(root->left);
  PostOrder(root->right);
  printf("%d ", root->data);
}

大家可以尝试画一下后序遍历的递归图解，博主就不画了。二叉树的遍历除了前序遍历、中序遍历和后序遍历，还有层序遍历，层序遍历的内容将会在下面的内容里讲解。

二叉树的节点个数以及高度等

1.二叉树的节点个数

当根为空时，节点个数为 0

当根不为空时，节点个数为左子树节点个数 + 右子树节点个数 + 1

// 二叉树的节点个数
int TreeSize(BTNode* root)
{
  return root == NULL ? 0 :
    TreeSize(root->left) + TreeSize(root->right) + 1;
}

2.二叉树的叶子节点个数

当根为空时，叶子节点的个数为 0

当根不为空且根的左子树和右子树都为空时，叶子节点的个数为 1

当根不为空且根的左子树和右子树至少一个不为空时，叶子节点的个数为左子树叶子节点个数 + 右子树叶子节点个数

// 二叉树的叶子节点个数
int TreeLeafSize(BTNode* root)
{
  if (root == NULL)
    return 0;
  if (root->left == NULL && root->right == NULL)
    return 1;
  return TreeLeafSzie(root->left) 
    + TreeLeafSize(root->right);
}

3.二叉树的高度

二叉树的高度 = 左、右子树的高度较大值 + 1

// 二叉树的高度
int TreeHeight(BTNode* root)
{
  if (root == NULL)
    return 0;
  int leftHeight = TreeHeight(root->left); // 左子树高度
  int rightHeight = TreeHeight(root->right); // 右子树高度
  return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

4.二叉树第K层节点个数

求第K层节点个数转换成求子树第K-1层节点个数

// 第K层节点个数
int TreeKLevel(BTNode* root, int k)
{
  assert(k > 0);
  if (root == NULL)
  {
    return 0;
  }
  if (k == 1)
  {
    return 1;
  }
  // 转换成求子树的第K-1层
  return TreeKLevel(root->left, k - 1)
    + TreeKLevel(root->right, k - 1);
}

5.二叉树查找值为 x 的节点

根节点为空时，返回空指针NULL

当根节点的数据等于x时，返回根节点的地址

如果根节点没有找到，先去左子树找

左子树没找到，再到右子树找

左右子树都没找到，返回空指针NULL

// 二叉树查找值为x的节点
BTNode* TreeFind(BTNode* root, BTDataType x)
{
  if (root == NULL)
    return NULL;
  if (root->data == x)
    return root;
  // 先去左子树找
  BTNode* leftRet = TreeFind(root->left, x);
  if (leftRet)
    return leftRet;
  //左子树没找到，再到右子树找
  BTNode* rightRet = TreeFind(root->right, x);
  if (rightRet)
    return rightRet;
  //左右子树都没有找到
  return NULL;
}

👉二叉树基础 OJ 练习👈

单值二叉树

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

思路：当根为空时，返回true。当根不为空时，如果左子树不为空且左子树的值不等于根的值，返回false；如果右子树不为空，且右子树的值不等于根的值，返回false。最后转换成子问题，继续判断左右子树是否为单值二叉树。

bool isUnivalTree(struct TreeNode* root)
{
    if(root == NULL)
        return true;
    // 左子树不为空且左子树的值不等于根的值
    if(root->left && root->val != root->left->val)
        return false;
    // 右子树不为空，且右子树的值不等于根的值
    if(root->right && root->val != root->right->val)
        return false;
    //继续判断左右子树是否为单值二叉树
    return isUnivalTree(root->left) && isUnivalTree(root->right);
}

相同的树

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

思路：当两个根都为空时，返回true；当一个根为空，另一个根不为空时，返回false；当两个根不为空且两个根的值不相等是，返回false。最后转换成子问题，继续判断左右子树是否是相同的树。

bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
    // 两个根都为空
    if(p == NULL && q == NULL)
        return true;
    // 一个根为空，另一个根不为空
    if(p == NULL || q == NULL)
        return false;
    // 两个根的值不相等
    if(p->val != q->val)
        return false;
    // 判断左右子树是否是相同的树
    return isSameTree(p->left, q->left)
        && isSameTree(p->right, q->right);
}

另一棵树的子树

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

思路：当根为空时，返回false；当根不为空，判断整棵树和二叉树 subRoot 是否为相同的树。如果是，返回true；如果不是，转换成左右子树和二叉树 subRoot 是否为相同的树。

bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
    // 两个根都为空
    if(p == NULL && q == NULL)
        return true;
    // 一个根为空，另一个根不为空
    if(p == NULL || q == NULL)
        return false;
    // 两个根的值不相等
    if(p->val != q->val)
        return false;
    // 判断左右子树是否是相同的树
    return isSameTree(p->left, q->left)
        && isSameTree(p->right, q->right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{
    if(root == NULL)
        return false;
    if(isSameTree(root, subRoot))
        return true;
    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

对称二叉树

给你一个二叉树的根节点 root ，检查它是否轴对称。

思路：写一个赋值判断是否为对称二叉树的函数judgeSymmetric，然后在isSymmetric函数中调用该函数判断。judgeSymmetric的实现：当左右子树都为空时，返回true；当左右子树其中一个为空，另一个不为空时，返回false；当左右子树都不为空且左右子树的值不相等时，返回false。最后转换成子问题，判断左子树的左和右子树的右以及左子树的右和右子树的左是否相同。

bool judgeSymmetric(struct TreeNode* left, struct TreeNode* right)
{
    if(left == NULL && right == NULL)
    {
        return true;
    }
    if(left == NULL || right == NULL)
    {
        return false;
    }
    if(left->val != right->val)
    {
        return false;
    }
    return judgeSymmetric(left->left, right->right) && judgeSymmetric(left->right, right->left);
}
bool isSymmetric(struct TreeNode* root)
{
    if(root == NULL)
        return true;
    return judgeSymmetric(root->left, root->right);
}

平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 。

思路：判断一颗树是否为平衡二叉树的关键就是左右子树的高度差绝对值是否小于 1 并且左右子树是否也为平衡二叉树。

//求一个数的绝对值
int my_abs(int num)
{
    return num > 0 ? num : -num;
}
//求二叉树的高度
int TreeHeight(struct TreeNode* root)
{
    if(root == NULL)
        return 0;
    int leftHeight = TreeHeight(root->left);
    int rightHeight = TreeHeight(root->right);
    return leftHeight > rightHeight ?
        leftHeight + 1 : rightHeight + 1;
}
bool isBalanced(struct TreeNode* root)
{
    if(root == NULL)
        return true;
    //my_abs(height(root->left)-height(root->right)) <= 1
    //看二叉树中每个节点的左右两个子树的高度差的绝对值是否超过1
    //isBalanced(root->left) isBalanced(root->right)看左右子树是否为平衡二叉树
    return (my_abs(TreeHeight(root->left)-TreeHeight(root->right)) <= 1) &&
           isBalanced(root->left) &&
           isBalanced(root->right);
}

翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

思路：这道题有点像在双向链表的某个节点前后插入新的节点，只需要改变指针的指向就行了。

struct TreeNode* invertTree(struct TreeNode* root)
{
    if(root == NULL)
        return NULL;
    struct TreeNode* tmp = root->left;
    root->left = root->right;
    root->right = tmp;
    invertTree(root->left);//对左子树进行翻转
    invertTree(root->right);//对右子树进行翻转
    return root;
}

二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的前序遍历。

在上面的内容里，我们已经学到了二叉树的前序打印。但是本道题目是要求把前序遍历的结果放到一个数组中，所以我们要先求出二叉树节点的个数，然后通过前序遍历将数据依次放到数组中。下面的中序遍历和后序遍历同理。

// 二叉树的节点个数
int TreeSize(struct TreeNode* root)
{
    if(root == NULL)
        return 0;
    else
        return TreeSize(root->left) + TreeSize(root->right) + 1;
}
// 前序遍历
void PreOrder(struct TreeNode* root, int* a, int* pi)
{
    if(root == NULL)
        return;
    a[*pi] = root->val;
    (*pi)++;
    PreOrder(root->left, a, pi);
    PreOrder(root->right, a, pi);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
    int n = TreeSize(root);
    int* ret = (int*)malloc(sizeof(int)*n);
    int i = 0;
    PreOrder(root, ret, &i);
    *returnSize = n;
    return ret;
}

二叉树的中序遍历

给定一个二叉树的根节点 root ，返回它的中序遍历。

// 二叉树的节点个数
int TreeSize(struct TreeNode* root)
{
    if(root == NULL)    
        return 0;
    else
        return TreeSize(root->left) + TreeSize(root->right) + 1;
}
// 中序遍历
void InOrder(struct TreeNode* root, int* a, int* pi)
{
    if(root == NULL)
        return;
    InOrder(root->left, a, pi);
    a[*pi] = root->val;
    (*pi)++;
    InOrder(root->right, a, pi);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize)
{
    int n = TreeSize(root);
    *returnSize = n;
    int* ret = (int*)malloc(sizeof(int)*n);
    int i = 0;
    InOrder(root, ret, &i);
    return ret;
}

二叉树的后序遍历

给定一个二叉树的根节点 root ，返回它的中序遍历。

// 二叉树的节点个数
int TreeSize(struct TreeNode* root)
{
    if(root == NULL)
        return 0;
    else
        return TreeSize(root->left) + TreeSize(root->right) + 1; 
}
// 后序遍历
void PosOrder(struct TreeNode* root, int* a, int* pi)
{
    if(root == NULL)
        return;
    PosOrder(root->left, a, pi);
    PosOrder(root->right, a, pi);
    a[*pi] = root->val;
    (*pi)++;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize)
{
    int n = TreeSize(root);
    *returnSize = n;
    int* ret = (int*)malloc(sizeof(int)*n);
    int i = 0;
    PosOrder(root, ret, &i);
    return ret;
}

👉二叉树的构建、销毁和层序遍历👈

二叉树的构建

思路：构建二叉树是先构建根，然后构建左子树和右子树，那么这个顺序就是前序遍历的顺序，那么我们可以采取前序遍历递归的方式来构建二叉树。

当a[*pi] == '#'时，(*pi)++并返回空指针return NULL

当a[*pi] != '#'时，申请节点构建根root->data = a[*pi]并且(*pi)++

根构建完成后，构建左子树root->left = BinaryTreeCreate(a, pi)和构建右子树root->right = BinaryTreeCreate(a, pi)

如果大家不太理解这个过程的话，可以画一下递归图解来帮助自己理解上面的过程。

#include <stdio.h>
#include <stdlib.h>
typedef char BTDataType;
typedef struct BinaryTreeNode
{
  BTDataType data;
  struct BinaryTreeNode* left;
  struct BinaryTreeNode* right;
}BTNode;
// 前序遍历构建树
BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
{
    if(a[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
    BTNode* root = (BTNode*)malloc(sizeof(BTNode));
    if(root == NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    //构建根
    root->data = a[*pi];
    (*pi)++;
    // 递归构建左右子树
    root->left = BinaryTreeCreate(a, pi);
    root->right = BinaryTreeCreate(a, pi);
    return root;
}
// 中序遍历
void InOrder(BTNode* root)
{
  if (root == NULL)
  {
    return;
  }
  InOrder(root->left);
  printf("%c ", root->data);
  InOrder(root->right);
}
int main()
{
    char str[100];
    scanf("%s",str);
    int i = 0;
    BTNode* root = BinaryTreeCreate(str, &i);
    InOrder(root);
    return 0;
}

二叉树的销毁

因为根和左右子树有链接关系，所以我们不能先销毁根。如果先销毁根我们就找不到左右子树了，所以我们采取后序遍历销毁二叉树。

// 二叉树销毁
void BinaryTreeDestroy(BTNode* root)
{
  if (root == NULL)
    return;
  BinaryTreeDestroy(root->left);
  BinaryTreeDestroy(root->right);
  free(root);
}

二叉树的层序遍历

层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在

层数为 1，层序遍历就是从所在二叉树的根节点出发，首先访问第 1 层的树根节点，然后从左到右访问第 2 层

上的节点，接着是第 3 层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int BTDataType;
typedef struct BinaryTreeNode
{
  BTDataType data;
  struct BinaryTreeNode* left;
  struct BinaryTreeNode* right;
}BTNode;
typedef BTNode* QDataType;
typedef struct QueueNode
{
  QDataType data;
  struct QueueNode* next;
}QNode;
typedef struct Queue
{
  QNode* head; // 头指针
  QNode* tail; // 尾指针
  int size;    // 节点的个数
}Queue;
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);
void QueueInit(Queue* pq)
{
  assert(pq);
  pq->head = pq->tail = NULL;
  pq->size = 0;
}
void QueueDestroy(Queue* pq)
{
  assert(pq);
  QNode* cur = pq->head;
  while (cur)
  {
    QNode* del = cur;
    cur = cur->next;
    free(del);
  }
  pq->head = pq->tail = NULL;
}
void QueuePush(Queue* pq, QDataType x)
{
  assert(pq);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  else
  {
    newnode->data = x;
    newnode->next = NULL;
  }
  // 队列中没有节点
  if (pq->tail == NULL)
  {
    pq->head = pq->tail = newnode;
  }
  else
  {
    pq->tail->next = newnode;
    pq->tail = newnode;
  }
  pq->size++;
}
void QueuePop(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  // 队列中只有一个节点
  if (pq->head->next == NULL)
  {
    free(pq->head);
    pq->head = pq->tail = NULL;
  }
  else
  {
    QNode* del = pq->head;
    pq->head = pq->head->next;
    free(del);
    //del = NULL;
  }
  pq->size--;
}
QDataType QueueFront(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->head->data;
}
QDataType QueueBack(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->tail->data;
}
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->size == 0;
  //return pq->head == NULL && pq->tail == NULL;
}
int QueueSize(Queue* pq)
{
  assert(pq);
  return pq->size;
}
// 手动构建二叉树
BTNode* CreateTree()
{
  BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));
  assert(n1);
  BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));
  assert(n2);
  BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));
  assert(n3);
  BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));
  assert(n4);
  BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));
  assert(n5);
  BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));
  assert(n6);
  n1->data = 1;
  n2->data = 2;
  n3->data = 3;
  n4->data = 4;
  n5->data = 5;
  n6->data = 6;
  n1->left = n2;
  n1->right = n4;
  n2->left = n3;
  n2->right = NULL;
  n3->left = NULL;
  n3->right = NULL;
  n4->left = n5;
  n4->right = n6;
  n5->left = NULL;
  n5->right = NULL;
  n6->left = NULL;
  n6->right = NULL;
  return n1;
}
// 二叉树的层序遍历
void TreeLevelOrder(BTNode* root)
{
  Queue q;
  QueueInit(&q);
  // 根不为空，则入队列
  if (root)
    QueuePush(&q, root);
  while (!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q);
    QueuePop(&q);
    printf("%d ", front->data);
    // 下一层入队列
    if (front->left)
      QueuePush(&q, front->left);
    if (front->right)
      QueuePush(&q, front->right);
  }
  printf("\n");
  QueueDestroy(&q);
}
int main()
{
  BTNode* root = CreateTree();
  // 层序遍历
  TreeLevelOrder(root);
  // 销毁二叉树
  BinaryTreeDestroy(root);
  root = NULL;
  return 0;
}

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

因为层序遍历是一层一层遍历的，所以我们可以利用层序遍历来判断二叉树是否为完全二叉树。一层一层走，遇到空以后，后续的层序遍历不能有非空，有非空就不是完全二叉树。

// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
  Queue q;
  QueueInit(&q);
  // 根不为空，则入队列
  if (root)
    QueuePush(&q, root);
  while (!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q);
    QueuePop(&q);
    if (front == NULL)
    {
      break;
    }
    // 下一层入队列
    QueuePush(&q, front->left);
    QueuePush(&q, front->right);
  }
  // 遇到空以后，后面全是空，则为完全二叉树
  // 遇到空以后，后面存在空，则不为为完全二叉树
  while (!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q);
    QueuePop(&q);
    if (front != NULL)
    {
      QueueDestroy(&q);
      return false;
    }
  }
  QueueDestroy(&q);
  return true;
}

👉总结👈

本篇博客主要讲解了二叉树的前序、中序、后序以及层序遍历，如何求二叉树的节点个数以及高度等，如何构建二叉树以及如何销毁二叉树。以上就是本篇博客的全部内容了，如果大家觉得有收获的话，可以点个三连支持一下！谢谢大家啦！💖💝❣️

【数据结构与算法】二叉树（下）