数据结构--二叉树（二）

链式二叉树

        链式二叉树是链式树集合中的一种，该树的每个根节点最多只有两个孩子节点，我们一般用左右孩子来称呼，在初学链式二叉树时，由于大家对链式二叉树的结构掌握还不够深入，为了降低本章的学习难度及成本，我们先手动创建一棵简易二叉树，快速进入二叉树的操作学习中，等所有基本操作大家都掌握后，我们再来了解如何创建链式二叉树。

        对于链式二叉树的结构代码如下：

typedef char BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;

        接下来是手动创建一棵简易二叉树：

BTNode* BuyNode(BTDataType data)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail!");return NULL;}node->data = data;node->left = node->right = NULL;return node;
}BTNode* CreatBinaryTree()
{BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);BTNode* node6 = BuyNode(6);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;return node1;
}

        构建的二叉树结构如图;

我们先来回顾一下二叉树的概念，二叉树是：

1. 空树。

2. 非空：根结点，根结点的左子树、根结点的右子树组成的。

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

二叉树的遍历

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

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

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 BinaryTreePrevOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}else{printf("%c ", root->data);BinaryTreePrevOrder(root->left);BinaryTreePrevOrder(root->right);}
}

        各位看到代码是否有眼前一亮呢，为何代码如此简单，别急，我们来通过图分析分析：

        前序遍历的要求是先遍历根节点，然后遍历左子树，最后遍历右子树。开始时，根节点的值为1，首先打印到控制台上，随后进入左子树进行遍历，左子树的根节点值为2，打印到控制台上，进入左子树进行遍历， 左子树的根节点值为3，打印到控制台上，进入左子树进行遍历，发现左子树的根节点为空，返回，进入到右子树进行遍历，发现右子树的根节点为空，返回。根节点值为3的函数已经运行结束，返回到根节点值为2的子树进行该子树的右子树遍历，根节点为空，返回。根节点为2的函数运行结束，返回到根节点值为1的二叉树中向下运行，进入右子树遍历，右子树根节点的值为4，打印到控制台上，进入左子树遍历，左子树的根节点值为5，打印到控制台上，进入左子树进行遍历， 左子树的根节点为空，返回，进入右子树遍历，右子树的根节点为空，返回。根节点值为5的函数运行结束，返回到根节点为4的函数中继续向下执行，进入右子树遍历，右子树根节点为6，打印到控制台上，进入左子树遍历，左子树的根节点为空，返回，进入右子树遍历，右子树的根节点为空，返回。根节点为6的函数执行结束，返回，根节点为4的函数执行结束，返回，根节点为1的函数执行结束，返回，函数结束。当然，之前节点为空的再返回之前会打印N字符表示该节点为空。

        聊到这里，我们不妨来了解一下递归函数中栈帧的创建和销毁过程，函数栈帧创建时需要内存提供空间存放栈帧，且存放是由高地址向低地址存放，由esp和ebp来记录函数栈帧两端的地址。通过不同的指令对寄存器进行操作，从而完成了函数栈帧的创建和销毁。

        具体细节各位可以看本篇文章：函数栈帧的创建和销毁（编程底层原理）-CSDN博客

        在这里我想要强调的是，每一个函数栈帧的开辟都需要开辟相应的空间，而函数递归是一种减少代码量，增加思维量和计算机指令的方式，如果递归层数过大可能会导致栈溢出(Stack Overflow)等问题，因此我们在后续解决递归问题时应尽可能的减少递归层次以避免该问题。

        还有一点各位要了解：我们调用的函数栈帧销毁是会将那块空间返还给内存，当进行下一次调用时，我们使用的空间是即是刚销毁的那块空间，也就是说，函数栈帧开辟销毁的空间是可以重复利用的。

        中序遍历

void InOrder(BTNode* root);

        代码如下：

        中序遍历的要求为先遍历左子树，然后遍历根节点，最后遍历右子树。

//中序遍历
void InOrder(BTNode* root)
{//根为空打印N并返回if (root == NULL){printf("N ");return;}//根不为空，先遍历左子树，后打印根节点，再遍历右子树InOrder(root->left);printf("%c ", root->data);InOrder(root->right);
}

         通过前序遍历，我想各位已经对递归函数的过程有了一定的了解，我希望各位可以了解前序遍历的过程后，独立去画一下中序遍历的过程，来加深印象和理解。

        后序遍历

void PostOrder(BTNode* root)；

        代码如下： 

//后序遍历
void PostOrder(BTNode* root)
{//根为空打印N并返回if (root == NULL){printf("N ");return;}//根不为空，先遍历左子树，后遍历右子树，再打印根节点PostOrder(root->left);PostOrder(root->right);printf("%c ", root->data);
}

        后序遍历的要求为先遍历左子树，然后遍历右子树，最后遍历根节点。开始时，根节点的值为1，进入到左子树遍历，左子树根节点的值为2，进入到左子树遍历，左子树的根节点值为3，进入到左子树遍历，根节点为NULL，打印N返回，进入到右子树遍历，根节点为NULL，打印N返回，随后打印值为3的根节点，返回上层函数，进入右子树，为空返回，打印2，返回到根节点为1的函数，进入右子树，根节点为4，进入左子树，根节点为5，进入左子树，为空返回，进入右子树为空返回，打印5，返回到根节点为4的函数，进入右子树，根节点为6，进入左子树，为空返回，进入右子树，为空返回，打印6返回，打印4返回，打印1，结束。

二叉树基本操作

        这样我们的三种遍历方式就结束了，接下来我们先看四个基本操作：

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

        二叉树结点个数

        这道题的思路有很多种，我们来一 一对比这几种方法的优劣：

        法一：全局变量 / (static 局部变量)法

        这两种方法比较相似，我们一起看：

//局部变量计算
int BinarySreeSize(BTNode* root)
{if (root == NULL)return 0;//static修饰局部变量 == 全局变量static int size = 0;size++;BinarySreeSize(root->left);BinarySreeSize(root->right);return size;
}//全局变量计算
int num = 0;
int BinaryTreeSize(BTNode* root)
{if (root == NULL)return 0;num++;BinaryTreeSize(root->left);BinaryTreeSize(root->right);return num;
}

        这两种方式都存在一个很大的弊端，如果我们通过printf多次调用本函数，会发现节点的个数会成倍增加，只有第一次调用函数的结果是对的，因此我不建议各位使用法一去解决此类问题。

        法二： 传参计算法：        

int BinaryTreeSize(BTNode* root, int* pi)
{if (root == NULL)return 0;(*pi)++;BinaryTreeSize(root->left, pi);BinaryTreeSize(root->right, pi);return (*pi);
}

        法二解决了法一中的问题，但是代价为法二多传了一个指针变量，并且，我们需要再调用函数之前将变量赋值为0。这样代码依旧略显冗余，因此就有了法三。

        法三：

        思路为当根节点为空时，返回0。根节点非空就返回根节点(1) + 左子树中的节点数 + 右子树中的节点数，在进行多次递归之后，我们就能得到节点的个数。代码如下： 

// 二叉树结点个数
int BinaryTreeSize(BTNode* root)
{//空节点返回0if (root == NULL)return 0;//非空节点返回：左子树节点个数+右子树节点个数+1return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

        二叉树叶子结点个数      

        这个操作与上面类似，只是之前是根节点存在加1，现在改成了，根节点存在且根节点不存在子树时加1。代码如下：

// 二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root)
{//空节点返回0if (root == NULL)return 0;//非空节点且无孩子节点返回1if (root->left == NULL && root->right == NULL)return 1;return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

        二叉树第k层结点个数

        我们要将操作分为三个过程。

1.根节点为空时，返回0。

2.根节点不为空，如果k为1，直接返回1。

3.根节点不为空，如果k>1，返回该二叉树的左子树第k-1层的节点个数与右子树第k-1层的节点个数。

代码如下： 

// 二叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{//空树返回0if (root == NULL)return 0;//非空树返回，如果k==1，返回1if (k == 1)	//root != NULLreturn 1;//非空树且，k > 1时return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

        二叉树查找值为x的结点

        这个操作在细节上非常容易出问题，我们将操作分为四步：

1. 根节点为空，返回NULL。

2. 根节点不为空，且根节点的值等于要查找的值，返回根节点。

3. 如果上方条件不成立，进入左子树寻找x节点，若找到，返回；没找到进入右子树寻找。

4. 遍历二叉树后，没有找到，返回NULL。

        这里要注意的是，很多人不明白为什么要用指针变量去接收函数的返回值之后再返回，因为我们在开始第三步后，如果找到了想要的节点，就会返回，而如果没有变量接收该节点继续返回上一层函数，就会继续往下执行操作，最终可能返回的依旧是NULL，因此接收返回值的操作至关重要，不仅能在找到节点后迅速返回，还避免了多层嵌套可能导致的栈溢出风险。

代码如下： 

// 二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{//空节点返回空if (root == NULL)return NULL;//非空节点比较数据，相同返回节点if (root->data == x)return root;//不相同继续遍历左、右子树寻找BTNode* ret1 = BinaryTreeFind(root->left, x);if (ret1)return ret1;BTNode* ret2 = BinaryTreeFind(root->right, x);if (ret2)return ret2;//都遍历完还没有，返回NULLreturn NULL;
}

二叉树经典OJ题目 

        下面我们来看一些题目巩固一下所学的知识：

单值二叉树

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

提示：

1. 给定树的节点数范围是 [1, 100]。
2. 每个节点的值都是整数，范围为 [0, 99] 。

解：

        既然要判断是否是单值二叉树，那根节点的值就必然要与它的子节点的值相同，因为我们知道a==b，b==c，则a==c的道理，我们就可以通过递归继续向下比较根与子节点的值，如果不相等就返回false，直到子树的根节点为空，返回true。又因为是整棵树的值都相等是才算单值，因此我们判断左右子树时用到的是&&符号。代码如下：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/bool isUnivalTree(struct TreeNode* root) {if(root == NULL)return true;if(root->left && root->left->val != root->val)return false;if(root->right && root->right->val != root->val)return false;return isUnivalTree(root->left) && isUnivalTree(root->right);
}

检查两棵树是否相同

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

 提示：

• 两棵树上的节点数目都在范围 [0, 100] 内
• -10^4 <= Node.val <= 10^4

解：

         这道题是很经典的一道基础题，在未来很多复杂进阶题目中都会见到它的身影。判断两个树是否相同，首先我们要看的就是根节点问题，如果两个根节点都不存在节点，当然就是相同的，我们返回true；如果只有其中一个的根节点存在，就是不同的，我们返回false；如果有两个根节点都存在，我们就需要去比较两个根节点的值是否相同，如果不同就返回false；如果相同，我们就继续判断他们的左子树和右子树，两个判断之间依旧是&&符号。代码如下：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/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 ， 检查它是否轴对称。

提示：

• 树中节点数目在范围 [1, 1000] 内
• -100 <= Node.val <= 100

解：

         这道题其实是上面判断相同树的一种变形，既然是对称树，那就存在镜像，我们在这个点上下手，问题不攻自破。首先判断根节点是否存在，不存在直接返回 true，随后就是判断相同树的那一套，只是我们将递归函数那边的参数调整了位置，让左子树的左孩子和右子树的右孩子比较，左子树的有孩子与右子树的左孩子比较，进行递归后即可得到结果。这里要注意的是，我们无需再从isSymmetric函数里再去递归。

        本质上就是先判断树的根节点是否存在，不存在就返回；存在就对根节点的左右子树进行镜像树判断。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/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->right) && isSameTree(p->right,q->left);
}bool isSymmetric(struct TreeNode* root) {if(root == NULL)return true;return isSameTree(root->left, root->right);
}

二叉树的前序遍历

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

解：

        因为前、中、后序遍历代码基本一致，这里只讲前序遍历的一道例题。

        题目给出的原函数是preorderTraversal(struct TreeNode* root, int* returnSize)，函数给了一个returnsize用于记录返回数组的长度，我们解题的第一想法通常是，遍历一个节点，++一下returnsize，这样没问题，但是有一种更好的方法，就是在创建数组之前我们遍历一遍树的根节点数，然后在开辟数组空间时就会减少不必要的空间消耗。正好也用到了我们之前的基本操作TreeSize函数，然后通过前序遍历将所有节点的val值放入数组，最后返回数组就可以了。

        这里要注意的一点是我们在给preOrder传参时，i一定要传地址，因为在递归函数中，形参的改变不会影响实参，会影响遍历过程。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
/*** Note: The returned array must be malloced, assume caller calls free().*/int TreeSize(struct TreeNode* root)
{return root == NULL? 0 : TreeSize(root->left)+TreeSize(root->right) + 1;
}void preOrder(struct TreeNode* root, int* a, int* pi)
{if(root == NULL)return;a[(*pi)++] = root->val;preOrder(root->left,a,pi);preOrder(root->right,a,pi);
}int* preorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize = TreeSize(root);int* a = (int*)malloc(sizeof(int)*(*returnSize));int i = 0;preOrder(root,a,&i);return a;
}

另一棵子树的子树

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

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

 提示：

• root 树上的节点数量范围是 [1, 2000]
• subRoot 树上的节点数量范围是 [1, 1000]
• -10^4 <= root.val <= 10^4
• -10^4 <= subRoot.val <= 10^4

 解：

        这道题同样延续了相同树的题型，判断一棵树是不是另一棵树的子树，只需要从根节点开始判断，如果两棵树相等就返回 true， 不相等就继续遍历它的左右子树，直到遍历完所有子树，根节点为空后，如还没有找到相同树，就返回false。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
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);
}

二叉树的创建及遍历

        在了解了链式二叉树的一些基本操作和经典OJ题目后，我想各位已经对二叉树有了一定的感觉，下面我们就来看看如何通过数组中存放的数据来创建链式二叉树。我们通过一道题目来给搭建演示：

        编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

输入描述：

        输入包括1行字符串，长度不超过100。

输出描述：

        可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行。

解：

         既然要接收一行字符串，自然要先创建数组。通过scanf接收后，进行前序二叉树的创建，我在创建二叉树函数中传入了一个数组首地址和一个变量的地址，分别用于接收数组和变量 i(作为数组元素的下标使用)，进入函数后，首先判断数组当前下标的元素是否为空(#)，为空的话就++下标并返回，不为空就继续向下执行，申请节点，根节点赋值，递归创建左子树，递归创建右子树，这都是之前见过的，这里不在多说，最后返回根节点。创建好之后，进入中序遍历函数，这里前面有。最后打印节点，结束。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
//创建链式二叉树结构体
typedef char BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;BTNode* BinaryTreeNodeCreate(BTDataType* a, int* pi)
{if(a[*pi] == '#'){(*pi)++;return NULL;}BTNode* root = (BTNode*)malloc(sizeof(BTNode));root->data = a[(*pi)++];root->left = BinaryTreeNodeCreate(a,pi);root->right = BinaryTreeNodeCreate(a,pi);return root;
}void InOrder(BTNode* root)
{if(root == NULL)return;InOrder(root->left);printf("%c ",root->data);InOrder(root->right);
}int main()
{//创建数组，接收字符串BTDataType a[100];scanf("%s",a); //二叉树的创建int i = 0;BTNode* root = BinaryTreeNodeCreate(a,&i);//中序遍历InOrder(root);return 0;
}

二叉树与队列的结合

        层序遍历

        在讲解之前我们需要进行一些队列代码的处理，因为之前我们队列中存储的值是int类型的，但是我们在树中的存放的节点是以链表的形式，因此在不破坏结构为前提下，我们需要将之前定义的QDataType转换为struct BinaryTreeNode*的指针类型，并把队列的头文件包含过去，这样我们就可以进行后续操作了。

        在前面将前、中、后序遍历的时候，我们采用的是递归遍历树节点的方式完成的。但是层序遍历有所不同，我们不能再顺着根节点去遍历，而是遍历完一层之后，才能去遍历下一层节点即广度优先算法。因此我们需要用到队列的功能，首先将根节点入队列，将根节点的值赋值给front之后删除队列中的节点，打印front的值，如果根节点的左孩子存在，入队列，如果根节点的有孩子存在，也入队列，继续上述操作，我们就能将所有的节点按，层序遍历的方式打印出来。代码如下：

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

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

        判断是否为完全二叉树的思路本质上和层序遍历是一样的，区别在于层序遍历找到空节点是跳过(不入队列)的，但是在判断完全二叉树时，我们要讲空节点也入队列，这是我们判断的关键条件，将根节点入队列，接着出队列时带入根节点的两个子节点，当出队列的根节点为空时，跳出循环。进入下一步，遍历队列中剩余的节点，如果都为空节点，说明是完全二叉树，如果存在非空节点，说明不是完全二叉树。

        对于其中的一些常见疑问，大家可以画图去了解，我在这里讲一个常见问题：如果遇到空节点时，还有非空节点没有入队列怎么办，这个担心是对的，但是我们一画图就能看出，这种情况的担心是多余的。

        我们从上图中可以看出，遇到第一个空节点时，即便是最下面的节点也入队列了，所以是完全可以判断的。可能大家还会想到一种情况：

        如果树节点是这样的那最后这个不就入不了队列吗，没错，但是这个节点入不入队列都是无所谓的，因为它的双亲节点能够入队列就已经证明了这棵树是否为完全二叉树，因此我们可以把它忽略不计。 

// 判断二叉树是否是完全二叉树
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){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}

二叉树的销毁

        二叉树的销毁比较简单，通过后序遍历释放根节点即可完成。代码如下：

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

         到此，我们的二叉树的学习就要告一段落了，但是二叉树的内容远不止于此，我们会在之后带大家走入更深层次的二叉树学习，如：AVL树、平衡搜索树、红黑树以及B树系列，敬请期待，我们下期见。