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

一、二叉树的实现

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

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

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;
  }
}

最后

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

完！

二叉树详解

一、二叉树的实现

1.1 二叉树的前序遍历

1.2 二叉树的中序遍历

1.3 二叉树的后续遍历

1.4 二叉树的节点个数

1.5 二叉树叶子节点个数

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

1.7 二叉树第k层节点个数

1.8 二叉树的高度

1.9 二叉树的销毁

二、二叉树的层序遍历

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

四、代码展示

BTNode.h

BTNode.c

Queue.h

Queue.c

最后

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

二叉树详解

一、二叉树的实现

1.1 二叉树的前序遍历

1.2 二叉树的中序遍历

1.3 二叉树的后续遍历

1.4 二叉树的节点个数

1.5 二叉树叶子节点个数

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

1.7 二叉树第k层节点个数

1.8 二叉树的高度

1.9 二叉树的销毁

二、二叉树的层序遍历

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

四、代码展示

BTNode.h

BTNode.c

Queue.h

Queue.c

最后

热门文章

最新文章

相关电子书