二叉树详解-阿里云开发者社区

一、二叉树的实现

前面我们已经说过了二叉树的定义与概念，现在我们讨论的是如何实现二叉树。

在二叉树中我们不仅无法确定其具体的孩子数，也无法确定其具体节点数。那该如何实现，那不就是无从下手吗？非也，咱们想不到，自有人会想到，这里，我们实现的思路为：左孩子、右兄弟表示法。即：根左边指向它的左孩子，右边指向它左孩子的兄弟也就是右孩子，这样不就表示出来了。可借助以下代码理解：

1. typedef struct BinaryTreeNode
2. {
3.  BTDataType data;
4.  struct BinaryTreeNode* left;
5.  struct BinaryTreeNode* right;
6. }BTNode;

运用此方法，我们可较为方便的表示出各个节点之间的关系。我们现在能用到这样的方法就是因为：我们是站在巨人的肩膀上。

了解了二叉树的大逻辑后，我们现在要开始研究二叉树的细枝末节了。

1.1 二叉树的前序遍历

我们在用代码实现前，我们要先明白，什么是遍历？什么是前序遍历？

所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。

所谓的前序遍历即：二叉树沿着：根，左子树，右子树的顺序进行遍历。

我们已明白其实现逻辑，现在开始用代码实现吧！

1. void BinaryTreePrevOrder(BTNode* root)
2. {
3.  if (root == NULL)
4.  {
5.    return;//此处也可打印N
6.  }
7.  printf("%d", root->data);//按照前序遍历顺序：根
8.  BinaryTreePrevOrder(root->left);//左子数
9.  BinaryTreePrevOrder(root->right);//右子数
10. }

上面帮助大家理解以下此代码。总之：记住顺序：根，左子树，右子树。

1.2 二叉树的中序遍历

在理解了前序遍历后，中序遍历也可以理解。中序遍历和前序遍历并无本质区别，只是顺序变换了一下，即：左子树，根，右子树。代码实现如下：

1. void BinaryTreeInOrder(BTNode* root)
2. {
3.  if (root == NULL)
4.  {
5.    return;
6.  }
7.  BinaryTreeInOrder(root->left);
8.  printf("%d  ", root->data);
9.  BinaryTreeInOrder(root->right);//无不一样之处，只是交换了顺序
10. }

1.3 二叉树的后续遍历

后续遍历的遍历顺序为：左子树，右子树，根。其余思路还是一致。代码实现如下：

1. void BinaryTreePostOrder(BTNode* root)
2. {
3.  if (root == NULL)
4.  {
5.    return;
6.  }
7.  BinaryTreePostOrder(root->left);
8.  BinaryTreePostOrder(root->right);
9.  printf("%d  ", root->data);
10. }

1.4 二叉树的节点个数

接下来，我们学习如何求二叉树的节点个数。

假如，你们学校有一个校长，两个院长，四个辅导员，八个班长。校长接到通知，要求统计在校师生人数，你觉得，校长会怎么干？是哪一个小本本，一个一个统计：计算机学院多少人，软件学院多少人，还是把他的左膀右臂——两个院长叫过来。答案显然易见，肯定会摇人，院长见校长这么想，肯定也会叫导员，层层外包，最后，班长成苦命的打工人。

统计节点个数的思路与上文类似，都是层层分封然后加上自己即可。代码实现如下：

1. int BinaryTreeSize(BTNode* root)
2. {
3.  if (root == NULL)
4.  {
5.    return 0;
6.  }
7.  return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
8. }

1.5 二叉树叶子节点个数

此问题我们可不可以运用上题的思路解决，当然可以。实现代码如下：

1. int BinaryTreeLeafSize(BTNode* root)
2. {
3.  if (root == NULL)
4.  {
5.    return 0;
6.  }
7.  if (root->left == NULL && root->right == NULL)
8.  {
9.    return 1;
10.   }
11.   return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
12. }

这里的实现思路只不过换成只要是叶节点就放回一。

1.6 二叉树查找值为x的节点

相信有一部分人看到此题，说：“简单”。然后写出以下代码：

1. BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
2. {
3.  if (root == NULL)
4.  {
5.    return NULL;
6.  }
7.  if (root->data == x)
8.  {
9.    return root;
10.   }
11.   return BinaryTreeFind(root->left,x);
12.   return BinaryTreeFind(root->right,x);
13. }

这个代码乍一看，大逻辑好像是对的，其实不然，如果，左子树，能够找到，那最好了。但，右子树和部分左子树根本找不到。为啥？一个函数是不是只有一个返回值，结构体可以有多个。既然只有一个，那么注定只能放回一个，其余的哪怕是找到了也会没找到，无法得用。

优化后代码如下：

1. BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
2. {
3.  if (root == NULL)
4.  {
5.    return NULL;
6.  }
7.  if (root->data == x)
8.  {
9.    return root;
10.   }
11.   BTNode*p1 = BinaryTreeFind(root->left,x);
12.   if (p1)
13.   {
14.     return p1;
15.   }
16.   BTNode* p2 = BinaryTreeFind(root->right,x);//分别用指针记录，找到才返回
17.   if (p2)
18.   {
19.     return p2;
20.   }
21.   return NULL;
22. }

1.7 二叉树第k层节点个数

求第k层高度，各位读者有没有思路。这里的难点为：如何找到该层。只要能找到，统计节点，那都会，对吧。

这里提供一种想法，仅供参考：每一次使k--，叫k的值和一比。如果等于一，则到了要找的层，不为一就继续，没有就返回0。代码实现思路如下：

1. int BinaryTreeLevelKSize(BTNode* root, int k)
2. {
3.  if (root == NULL)
4.  {
5.    return 0;
6.  }
7.  if (k == 1)
8.  {
9.    return 1;
10.   }
11.   return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
12. }

1.8 二叉树的高度

我们在这里想，如何求出二叉树的高度呢？是不是可以转换成左子树和右子树谁更高的问题。谁高就加一，对吧。来先看以下代码：

1. int TreeHight(BTNode* root)
2. {
3.  if (root == NULL)
4.  {
5.    return 0;
6.  }
7.  return TreeHight(root->left) > TreeHight(root->right) ?
8.    TreeHight(root->left) + 1 : TreeHight(root->right) + 1;
9. }

这代码，从逻辑和结果上来看，没啥问题。但，复杂度太高。

咱们的想法是运用递归实现，本题中的代码，没有一个记录的，本次用完，别人想用，就忘记了，就要重新调。读者可能认为是2倍的关系。其实不然，我用故事来解释一下：

当班长把统计的人数告诉导员时候，导员说：知道了，你回去吧。走到半路，接到电话，导员说：你在来一下，我给院长汇报时忘记了。班长去汇报，回来。又去为啥：院长统计时又忘记了，又去，又回来，没完没了了，可用下图表示：

从此图可以看出复杂度是很高的，越是底层，干的就越多。所以，我们可做以下优化：

1. int TreeHight(BTNode* root)
2. {
3.  if (root == NULL)
4.  {
5.    return 0;
6.  }
7.  int left = TreeHight(root->left);
8.  int right = TreeHight(root->right);
9.  return left > right ?
10.     left + 1 : right + 1;
11. }

1.9 二叉树的销毁

二叉树的销毁其实传不传二级指针都行，不传的化，只需在调用后，手动置空即可。

1. void TreeDestory(BTNode* root)
2. {
3.  if (root == NULL)
4.    return;
5. 
6.  TreeDestory(root->left);
7.  TreeDestory(root->right);
8.  free(root);
9. }

二、二叉树的层序遍历

以上我们已经明白了二叉树的基本结构的实现。接下来，我们来思考一件事如何实现二叉树的层序遍历。

首先，我们要说一下何为层序遍历？顾名思义，层序遍历即：一层一层的遍历每个节点即可。

明白了我们要做的事情，那我们应该如何去完成？大家可能第一时间想到的是递归，毕竟二叉树就是递归实现的。那么？层序遍历用递归可行吗？好像有点不太可行。因为你要顺序的访问每一个节点，递归实现好像有点困难。那我们能否转变思路，这个要求的是层序遍历，那么？我们能否借助数组或链表一个一个把它们放入到该结构中。在我们学习中，符合该结构又符合先进先出的只有那一种结构了——队列！

那，我们能否借助队列实现，当然可以。实现思路如下：

队列该数据结构特点为：先进先出。我们可以先把根节点放入，我们把它放入后这时叫他出队，出队的同时把它的左右护法放入，对每个节点都进行该操作，直到节点为空。

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
  Queue q;
  QueueInit(&q);
  if (root)
  {
    QueuePush(&q, root);
  }
  while (!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q);
    QueuePop(&q);
    if (front->left)
    {
      QueueFront(front->left);
    }
    if (front->right)
    {
      QueueFront(front->right);
    }
  }
}

这时，读者可能会有以下问题：这里pop掉q，那front能找到它的左右护法吗？大家想一想。答案是：不影响。就好比：你们抓鲁迅管我周树人什么事？（bushi）你们看咱们只是改变q此时的指向，二叉树的节点全放在队列里面，队列里面pop并不影响你这个二叉树的结构。原来的关系没有改变，故可以找到。

那有人可能要问了？那它们不是指向同一块地址吗？这种思维有点不太正确。队列中存储的是树节点的指针，而不是节点本身。当从队列中弹出一个节点时，只是移除了节点指针在队列中的位置，不会影响树结构或树中的节点

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

学习完如何遍历了，我们现在来学习如何判断二叉树是否为完全二叉树。

我们对其有何实现思路。递归？然后用节点范围来判断？听起来似乎可行，但又不可行。为何？

如图的二叉树就无法用此方法来判断。现在似乎陷入了僵局，该如何处理？我们可否参考上图的结构，每一个入队列，遇到空截止。然后再继续层序遍历，遇到不为空的返回false，一直为空返回true。思路上是可行的，如果上图的二叉树再接一个节点会进队列吗？答案很明显：不会。但是，影响吗？不影响？因为我们通过以上就可以判断出它不为完全二叉树了，那最后一个进不进又区别吗？所以，我们代码实现思路不就出来了？代码实现如下：

bool BinaryTreeComplete(BTNode* root)
{
  Queue q;
  QueueInit(&q);
  if (root)
  {
    QueueFront(&q);
  }
  while (!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q);
    QueuePop(&q);
    if (front == NULL)
    {
      break;
    }
    if (front->left)
    {
      QueueFront(front->left);
    }
    if (front->right)
    {
      QueueFront(front->right);
    }
  }
  while (!QueueEmpty(&q))
  {
    QNode* front = QueueFront(&q);
    QueuePop(&q);
    if (front != NULL)
    {
      return false;
    }
  }
  return true;
}

四、代码展示

BTNode.h

1. #pragma once
#include<stdio.h>
 
typedef char BTDataType;
 
typedef struct BinaryTreeNode
{
  BTDataType data;
  struct BinaryTreeNode* left;
  struct BinaryTreeNode* right;
}BTNode;
 
 
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
//求二叉树高度
int TreeHight(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);

BTNode.c

1.#include"BTNode.h"
 
//二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root)
{
  if (root == NULL)
  {
    return;//此处也可打印N
  }
  printf("%d", root->data);//按照前序遍历顺序：根
  BinaryTreePrevOrder(root->left);//左子数
  BinaryTreePrevOrder(root->right);//右子数
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
  if (root == NULL)
  {
    return;
  }
  BinaryTreeInOrder(root->left);
  printf("%d  ", root->data);
  BinaryTreeInOrder(root->right);//无不一样之处，只是交换了顺序
}
//二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
  if (root == NULL)
  {
    return;
  }
  BinaryTreePostOrder(root->left);
  BinaryTreePostOrder(root->right);
  printf("%d  ", root->data);
}
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
  if (root == NULL)
  {
    return 0;
  }
  return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
  if (root == NULL)
  {
    return 0;
  }
  if (root->left == NULL && root->right == NULL)
  {
    return 1;
  }
  return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(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);
}
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
  if (root == NULL)
  {
    return NULL;
  }
  if (root->data == x)
  {
    return root;
  }
  BTNode*p1 = BinaryTreeFind(root->left,x);
  if (p1)
  {
    return p1;
  }
  BTNode* p2 = BinaryTreeFind(root->right,x);//分别用指针记录，找到才返回
  if (p2)
  {
    return p2;
  }
  return NULL;
}
//求二叉树高度
int TreeHight(BTNode* root)
{
  if (root == NULL)
  {
    return 0;
  }
  int left = TreeHight(root->left);
  int right = TreeHight(root->right);
  return left > right ?
    left + 1 : right + 1;
}
// 二叉树销毁
void TreeDestory(BTNode* root)
{
  if (root == NULL)
    return;
 
  TreeDestory(root->left);
  TreeDestory(root->right);
  free(root);
}
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
  Queue q;
  QueueInit(&q);
  if (root)
  {
    QueuePush(&q, root);
  }
  while (!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q);
    QueuePop(&q);
    if (front->left)
    {
      QueueFront(front->left);
    }
    if (front->right)
    {
      QueueFront(front->right);
    }
  }
}
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
  Queue q;
  QueueInit(&q);
  if (root)
  {
    QueueFront(&q);
  }
  while (!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q);
    QueuePop(&q);
    if (front == NULL)
    {
      break;
    }
    if (front->left)
    {
      QueueFront(front->left);
    }
    if (front->right)
    {
      QueueFront(front->right);
    }
  }
  while (!QueueEmpty(&q))
  {
    QNode* front = QueueFront(&q);
    QueuePop(&q);
    if (front != NULL)
    {
      return false;
    }
  }
  return true;
}

Queue.h

#pragma once
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>
 
typedef struct BinaryTreeNode* QDataType;
// 链式结构：表示队列 
typedef struct QListNode
{
  struct QListNode* next;
  QDataType data;
}QNode;
 
// 队列的结构 
typedef struct Queue
{
  QNode* phead;
  QNode* ptatil;
  int size;
}Queue;
 
// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);

Queue.c

#include"Queue.h"
 
// 初始化队列 
void QueueInit(Queue* q)
{
  assert(q);
  q->phead = q->ptatil = NULL;
  q->size = 0;
}
// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
  assert(q);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return;
  }
  newnode->data = data;
  newnode->next = NULL;
  if (q->phead == NULL)
  {
    q->phead = q->ptatil = newnode;
  }
  else
  {
    q->ptatil->next = newnode;
    q->ptatil = newnode;
  }
  q->size++;
}
// 队头出队列 
void QueuePop(Queue* q)
{
  assert(q);
  assert(q->size > 0);
  if (q->phead->next == NULL)
  {
    q->phead = q->ptatil = NULL;
  }
  else
  {
    QNode* tmp = q->phead->next;
    free(q->phead);
    q->phead = tmp;
  }
  q->size--;
}
// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
  assert(q);
  assert(q->phead);
  return q->phead->data;
}
// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
  assert(q);
  assert(q->ptatil);
  return q->ptatil->data;
}
// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
  assert(q);
  return q->size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q)
{
  assert(q);
  return q->size == 0;
}
// 销毁队列 
void QueueDestroy(Queue* q)
{
  assert(q);
  QNode* tmp = q->phead;
  while (tmp)
  {
    QNode* next = tmp->next;
    free(tmp);
    tmp = next;
  }
}

最后

以上，便是我所有说的二叉树的大部分内容了，剩下的部分会在明天我为大家准备的练习题中进行讲解。如果今天讲出来，不太利于大家的理解。希望大家能把今天讲的知识拿去练习，好好理解巩固一下，我们明天再会！

完！

二叉树详解