普通二叉树的操作

  • 1. 前情说明
  • 2. 二叉树的遍历
    • 2.1 前序、中序以及后序遍历
        • 2.1.1 前序遍历
        • 2.1.2 中序遍历、后序遍历
    • 2.2 题目练习
      • 2.2.1 求一棵二叉树的节点个数
      • 2.2.2 求一棵二叉树的叶节点个数
      • 2.2.3 求一棵二叉树第k层节点的个数
      • 2.2.4 求一棵二叉树的深度
      • 2.2.5 在一棵二叉树中查找值为x的节点
      • 2.2.6 销毁一棵二叉树
    • 2.3 二叉树的层序遍历
    • 2.4 题目练习
      • 2.4.1 判断一棵二叉树是否是完全二叉树

1. 前情说明

本文主要是针对二叉树的链式结构操作进行讲解。
对于普通二叉树的学习，已经不能像之前学线性表，堆等数据结构那样，围绕增删查改来进行操作学习。说到底，对于普通二叉树的增删查改是没有意义的。树形结构本身相对线性结构就更复杂，而且普通二叉树对于数据的操作又不能达到一些规律性的性质，种种原因都限制了普通二叉树的增删改查操作。如果非要进行数据的增删改查，不如去选择操作更方便的结构。比如在数据存储上，与普通二叉树复杂的存储结构相比，不如去选择顺序表，链表等更简单的结构进行数据的存储，这类数据结构对数据的维护也会更容易。
既然如此，那我们学习普通二叉树的意义何在呢？

  1. 为学习更复杂更有意义的二叉树做储备。
  2. 很多二叉树的OJ算法题目都是出在普通二叉树上的。
    所以，对于普通二叉树的操作，本文会涉及几道题目的练习，方便大家认识理解。

说到这里，既然不学增删查改，那还学什么呢？
那当然需要学习的是对普通二叉树的遍历和结构控制了。

2. 二叉树的遍历

学习二叉树的结构，最简单的方式就是遍历。所谓二叉树的遍历是指按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。而访问节点所做的操作就依赖于具体的应用问题了。
遍历是二叉树最重要的操作之一，也是在二叉树上进行其它操作的基础。
在进行遍历之前，还是再来看一下二叉树的概念吧。
二叉树是：

  1. 空树
  2. 非空：由根节点，根节点的左子树，根节点的右子树组成

从概念中可以看出，二叉树的定义是递归式的，因此要注意的是，后续各种操作中基本都是按照该递归概念实现的。
同时，据此可以给出二叉树节点的定义如下：

typedef int BTDataType;typedef struct BinaryTreeNode{struct BinaryTreeNode* left;//存放左子树的根节点地址struct BinaryTreeNode* right;//存放右子树的根节点地址BTDataType data;//根节点的数据域}BTNode;

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

按照规则，二叉树的遍历有三种递归结构的遍历：

  1. 前序遍历(也叫先序遍历，先根遍历) —— 访问根节点的操作发生在遍历其左右子树之前。
  2. 中序遍历(也叫中根遍历) —— 访问根节点的操作发生在遍历其左右子树之中(间)。
  3. 后序遍历(也叫后根遍历) —— 访问根节点的操作发生在遍历其左右子树之后。

2.1.1 前序遍历

根据先根节点，再左子树，再右子树的顺序走一遍，大致可以得到如下图所示的遍历轨迹。

先从根节点1开始遍历，根节点1遍历之后，就开始遍历左子树，
再从左子树的根节点2开始遍历，根节点2遍历之后，又开始遍历根节点2的左子树，
再从左子树的根节点3开始遍历，跟节点3遍历之后，又开始遍历跟节点3的左子树，
但是根节点3的左子树为空，于是路线直接返回到根节点3，开始遍历根节点3的右子树，
但是根节点3的右子树为空，于是路线直接返回到根节点3，此时根节点3所在的子树前序遍历已经完成，所以路线直接返回到根节点2，开始遍历跟节点2的右子树，
但是根节点2的右子树为空，于是路线直接返回到根节点2，此时根节点2所在的子树前序遍历已经完成，所以路线直接返回到根节点1，开始遍历跟节点1的右子树，
再从右子树的根节点4开始遍历，根节点4遍历之后，又开始遍历根节点4的左子树，
再从左子树的根节点5开始遍历，根节点5遍历之后，又开始遍历根节点5的左子树，
但是根节点5的左子树为空，于是路线直接返回到根节点5，开始遍历根节点5的右子树，
但是根节点5的右子树为空，于是路线直接返回到根节点5，此时根节点5所在的子树前序遍历已经完成，所以路线直接返回到根节点4，开始遍历跟节点4的右子树，
再从右子树的根节点6开始遍历，根节点6遍历之后，又开始遍历根节点6的左子树，
但是根节点6的左子树为空，于是路线直接返回到根节点6，开始遍历根节点6的右子树，
但是根节点6的右子树为空，于是路线直接返回到根节点6，此时根节点6所在的子树前序遍历已经完成，所以路线直接返回到根节点4，此时根节点4所在的子树前序遍历已经完成，所以路线直接返回到根节点1，此时根节点1所在的子树前序遍历已经完成，也就是整棵树的前序遍历已经完成了。
根据上述遍历过程，当遍历时遇到空时，过程会返回；子树的前序遍历完成之后，过程会返回。根据此思路，将其实现可得如下递归代码：

void PreOrderTraversal(BTNode* root){if (NULL == root){printf("# ");//打印“#”代表节点为空return;}printf("%d ", root->data);PreOrderTraversal(root->left);PreOrderTraversal(root->right);}

根据函数调用的次序过程，尝试画出其调用路线如下(红色代表递归调用，绿色代表调用返回，“#”代表子树为空)：

2.1.2 中序遍历、后序遍历

同理，
根据中序遍历：先左子树，再根节点，再右子树
和后序遍历：先左子树，再右子树，在根节点
的遍历过程(不再赘述文字)，
将其实现可分别得到如下递归代码和调用路线图：

//中序遍历void InOrderTraversal(BTNode* root){if (NULL == root){printf("# ");return;}InOrderTraversal(root->left);//先左子树printf("%d ", root->data);//再根节点InOrderTraversal(root->right);//再右子树}

//后序遍历void PostOrderTraversal(BTNode* root){if (NULL == root){printf("# ");return;}PostOrderTraversal(root->left);//先左子树PostOrderTraversal(root->right);//再右子树printf("%d ", root->data);//再根节点}


根据以上对于前中后序的递归遍历，我们可以打印出遍历结果分别如下：

前序遍历：1 2 3 # # # 4 5 # # 6 # #
中序遍历：# 3 # 2 # 1 # 5 # 4 # 6 #
后序遍历：# # 3 # 2 # # 5 # # 6 4 1

这里可以告诉大家一种取巧的方法来判断给定一棵树的前中后序遍历结果：

如图所示，
先画图将空节点补全，再从根节点左边开始沿着树的结构画出如图所示的蓝色路线图。
前序遍历的结果就是沿着路线图标记的红色结果，每一个标记都在节点的左边；
中序遍历的结果就是沿着路线图标记的绿色结果，每一个标记都在节点的下边；
前序遍历的结果就是沿着路线图标记的黄色结果，每一个标记都在节点的右边。

2.2 题目练习

了解了这些遍历方式之后，我们可以来看几个题。

2.2.1 求一棵二叉树的节点个数

首先要从二叉树的概念入手。要求一棵二叉树的节点个数，无非就是求二叉树的根节点个数+左子树的节点个数+右子树的节点个数。如果遇到空树，就不是真的节点，返回0即可。但是根节点的话，不能直接返回，要先求出左子树的节点个数+右子树的节点个数，然后再加上根节点的一个数量一齐返回才行。所以可以考虑到用后序遍历完成。
参考代码如下：

int TreeSize(BTNode* root){return NULL == root " />
 广度优先搜索一般都会借助队列数据结构来完成，这里下面也是使用队列来完成操作的。
 但因为这里使用的是C语言，所以还需要自己写一个队列做准备(如果使用的语言本身有符合队列性质的结构可以忽略)，需要的小伙伴也可以从阿顺的这篇博文链式队列(C语言实现)获取。
 好了，既然有了队列，该如何利用队列的各种性质操作来完成层序遍历呢？
 我们可以利用队列先进先出的性质来完成层序遍历的过程。
 首先，当树的根节点存在时，层序遍历第一个遍历的肯定是根节点。将根节点的数据进行入队，此时，根节点的数据就入队完成了。
 
 接下来该入树的第二层的数据了，也就是2和4。那该如何将他们入队呢？
 可以知道的是，他们是根节点的左右子树中的根节点，所以根节点1中的左右指针域存放的有它们的地址，可以通过根节点找到它们。然后将他们进行入队。但是要遵循先左子树后右子树的顺序进行入队。
 
 
到第三层的数据入队了，它们分别来自节点2为根的子节点和结点4为根的子节点。同样是通过上一层的节点中的指针域来找到它们进行入队，并且要遵循先左子树后右子树的顺序。
 
 好了，到此树中的所有数据都入队了，再将他们顺序出队，就得到了层序遍历的结果了。
 根据此思想，可以给出如下参考代码：
 
void LevelOrderTraversal(BTNode* root){Queue q;QueueInit(&q);//初始化队列//根节点存在，就直接入队列//入的是结点的地址，因为这样才能在后续通过指针域将其它节点入队if (NULL != root){QueuePush(&q, root);}while (!QueueEmpty(&q)){//如果队列不为空，执行以下操作//取队头元素BTNode* front = QueueFront(&q);//这里将队头元素交给front后，直接出队头数据了，和上面的图画的有出入//真实的过程在下图中QueuePop(&q);printf("%d ", front->data);if (NULL != front->left){QueuePush(&q, front->left);}if (NULL != front->right){QueuePush(&q, front->right);}}printf("\n");QueueDestroy(&q);}

 在理解了上述层序遍历的过程，下面趁热打铁就来看一道题。
2.4 题目练习
2.4.1 判断一棵二叉树是否是完全二叉树
是返回true，不是返回false。
 完全二叉树的概念这里就不在赘述，需要的小伙伴可以参考阿顺的这篇博文
 完全二叉树入队：
 
普通二叉树入队：
 
 可以发现完全二叉树入队后，树的非空节点和空节点是“泾渭分明”的，而普通二叉树的非空节点和空节点是“鱼龙混杂”的。
 这就为我们判断一棵二叉树是完全二叉树还是普通二叉树提供了思路。
bool TreeComplete(BTNode* root){Queue q;QueueInit(&q);if (NULL != root){QueuePush(&q, root);}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front != NULL){QueuePush(&q, front->left);QueuePush(&q, front->right);}else//fornt==NULL，循环结束{break;}}while (!QueueEmpty(&q)){//如果NULL后面还有非空节点，就返回falseif (QueueFront(&q) != NULL){//队列销毁，防止内存泄漏QueueDestroy(&q);return false;}QueuePop(&q);}//NULL后面不存在非空节点，返回trueQueueDestroy(&q);return true;}
好了，本文对于普通二叉树的讲解算是完结了。虽然费劲心机想写得大家能一遍看懂，但感觉还是很难，真的是写得有些精疲力尽了，但最后还是希望能对大家的学习有一点点帮助吧。