数据结构与算法（十）——二叉树初探
之前都是介绍的逻辑结构中的线性结构，今天介绍一种非线性结构——树结构。
一、树的基本认识以及相关概念
1，树的结构
树是具有N（N>=0）个节点的有限集。树中可以没有任何节点（空树），也可以只有一个根节点（如上图左侧），也可以有多个节点（如上图右侧）。
2，节点、度、叶子节点
如上图所示，A、B、C、D等就是节点，节点中包含了数据，也包含了各种指向关系。
度，指的是节点所拥有的子树个数。比如，A节点的度是3，B节点的度是2，D节点的度是3。
叶子节点，又称为终端节点，指的是度为0的节点。比如，上图中的叶子节点是K、J、F、G、M、I、J。
非叶子节点，又称为非终端节点，指的是度不为0的节点。比如，上图中的非终端节点是A、B、C、D、E、H。
3，双亲结点、兄弟节点
在树中，双亲结点指的是一个节点。比如，B节点的双亲结点是A节点，E节点的双亲结点是B节点。
兄弟节点指的是，同属于一个双亲结点的子节点。比如，E、F互相称为兄弟节点，H、I、J互相称为兄弟节点。
4，节点的高度、深度、层数
节点的高度，指的是该节点到叶子节点的最长路径（边数）。
节点的深度，指的是根节点到该节点所经历的边的个数。
节点的层数，一棵树的根节点为第一层，往下依次递增。
树的高度，指的是根节点的高度。
A节点的高度是3，B节点的高度是2，C节点的高度是1，H节点的高度是1，I节点的高度是0。
A节点的深度是0，B节点的深度是1，C节点的深度是1，H节点的深度是2，I节点的深度是2。
二、二叉树的基本认识以及相关概念
1，基本认识
二叉树上的每个节点最多只有两个子节点，也就是说，节点的度 <= 2。
二叉树的子树有左右之分的，左子树和右子树都有其特殊的意义，不能随意颠倒。如下图所示，A节点下面只有一个B节点，但是树1的B节点是左节点，树2的B节点是右节点，因此树1和树2是两个不同的树。
2，满二叉树、完全二叉树
在一棵二叉树里面，如果所有的非叶子节点都具备左右两个节点，并且所有的叶子节点都在同一层，这样的二叉树称为满二叉树。如下图所示：
一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。
如下图所示，就是一个完全二叉树：
如下图所示，少了一个节点10，那么它就不是完全二叉树：
如下图所示，少了一个节点6、7，也不是完全二叉树：
如下图所示，少了节点10、11，所以也不是完全二叉树：
三、二叉树的顺序存储
我们是使用数组来实现二叉树的线性存储，各个节点信息依次有序存入数组的对应位置。
对于一个一般的二叉树，顺序存储的方式是会造成很大的空间浪费的。如下图所示，该树中只有四个节点，但是却需要开辟15个空间。
一般而言，对于完全二叉树，我们才会考虑去使用顺序存储的方式，因为顺序存储相对于链式存储要简单，而完全二叉树又不会造成很大的空间浪费。
而对于一般的二叉树，最好是使用链式存储的方式。
1，二叉树的初始化
核心思路：将每一个节点遍历置空
代码如下：
#include <stdio.h>
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"
#include <stdbool.h>
#define Tree_Size 100 // 二叉树的大小
// 操作的状态
typedef enum : int {
Success,
Error,
} Status;
// 空节点
#define Nil 0
// 节点类型
typedef int ElementType;
// 定义二叉树类型
typedef ElementType BinaryTree[Tree_Size];
// 1，二叉树的初始化（初始化为空树）
Status initBinaryTree(BinaryTree binaryTree) {
for (int i = 0; i < Tree_Size; i++) {
// 将二叉树的所有节点都置空
binaryTree[i] = Nil;
}
return Success;
}2，二叉树的创建
核心思路：
（1）遍历二叉树所有节点，将输入的初始节点值依次赋值到指定位置，余下的位置均置空
（2）在遍历插入的时候，如果一个节点非空，但是其双亲节点为空，此时需要报错
代码如下：
// 2，二叉树的创建
Status createBinaryTree(BinaryTree tree, ElementType *nodeValues, int nodeValuesLength) {
for (int i = 0; i < Tree_Size; i++) {
// 当前节点的值(超出输入数组的范围之后直接取Nil值)
ElementType currentNodeValue = i < nodeValuesLength ? nodeValues[i] : Nil;
// 双亲结点为空的时候，不可赋有效值
int parentsIndex = (i - 1) / 2;
if (currentNodeValue != Nil && tree[parentsIndex] == Nil) {
printf("输入的节点值有误，在父节点为空的情况下，子节点竟然有值!\n");
return Error;
}
// 给节点赋值（能通过输入的数组）
tree[i] = currentNodeValue;
}
return Success;
}3，二叉树的清空
核心思路如下：
1，遍历二叉树的每一个节点，然后给每个节点置空
2，二叉树的清空逻辑和二叉树的初始化逻辑都是一样的，因此可以直接复用
代码如下：
// 3，二叉树的清空
/*
二叉树的清空跟二叉树的初始化逻辑是完全一样的，都是将各个节点置空。
此时只需要重新定义一个函数来复用原来初始化函数的逻辑即可
*/
#define initBinaryTree clearBinaryTree4，二叉树的判空
核心思路：如果二叉树的根节点为空，那么该二叉树就是一个空树。
代码如下：
// 4，二叉树判空
/*
只要根节点为空，那么该二叉树就是一个空树
*/
bool isBinaryTreeEmpty(BinaryTree tree) {
return tree[0] == Nil;
}5，二叉树的深度
核心思路如下：
（1）二叉树的深度就是该树中所有节点的深度最大的那一个；
（2）因此，找到最后一个节点，然后计算其深度即可
（3）函数powl(2, n)表示2^n
代码如下：
// 5，获取二叉树深度
/*
二叉树的深度是就是该数里面所有节点的深度最大的那一个
所以找到最后那个非空节点，然后计算其深度即可
*/
int depthOfBinaryTree(BinaryTree tree) {
// 找到最后那个非空节点的下标
int finalNodeIndex;
for (finalNodeIndex = Tree_Size - 1; finalNodeIndex >= 0; finalNodeIndex--) {
if (tree[finalNodeIndex] != Nil) {
break;
}
}
// 计算深度
int depth = 0; // 声明一个临时变量记录深度
while (powl(2, depth) - 1 <= finalNodeIndex) { // powl函数的作用是计算次幂
depth++;
}
return depth;
}6，获取指定位置上面的节点值
核心思路如下：
（1）通过两个元素来只是某个节点的位置
①level，层
②order，在当前层中的序号
代码如下：
// 6，获取指定位置上面的节点值
/*
level：节点的层
order：节点在所在层上的顺序值
*/
ElementType elementOfPosition(BinaryTree tree, int level, int order) {
return tree[(int)powl(2, level-1) + order - 2];
}7，获取根节点的值
核心思路：
所谓根节点，指的就是排在首位的节点
代码如下：
// 7，获取根节点的值
ElementType roorNode(BinaryTree tree) {
return tree[0];
}8，给指定位置的节点赋值
核心思路如下：
（1）首先根据层序找到对应的位置
（2）然后找到该位置的双亲结点
（3）如果双亲结点为空，并且当前节点值为非空，则报错
（4）如果当前节点值为空，并且其子节点非空，则报错
代码如下：
// 8，给指定位置的节点赋值
Status setValue(BinaryTree tree, int level, int order, ElementType element) {
// 找到节点的位置坐标
int index = (int)powl(2, level - 1) + order - 2;
// 如果该值非空但是双亲节点为空，则报错
if (element != Nil && tree[(index - 1) / 2] == Nil) {
return Error;
}
// 如果该值为空，但其子节点非空，则报错
if (element == Nil && (tree[2*index+1]!=Nil || tree[2*index+2]!=Nil)) {
return Error;
}
// 赋值
tree[index] = element;
return Success;
}9，获取某节点的双亲结点
核心思路如下：
（1）如果是空树，则报错
（2）如果当前节点是根节点或者未找到当前节点，则报错
代码如下：
// 9，获取某节点的双亲结点
ElementType parentNode(BinaryTree tree, ElementType node) {
// 如果是空树，则直接返回Nil
if (tree[0] == Nil) {
return Nil;
}
// 遍历找到对应节点
int index;
for (index = 0; index < Tree_Size; index++) {
if (tree[index] == node) {
break;
}
}
// 如果给定的节点不存在，则返回Nil
if (index == Tree_Size) {
return Nil;
}
// 找到双亲节点
int parentsNodeIndex = (index - 1) / 2;
return tree[parentsNodeIndex];
}10，获取节点的左孩子
核心思路：
（1）如果是空树，则报错
（2）找到对应节点，如果没找到该节点或者节点为空，则报错
（3）需要判断子节点的底标是否超限，如果超限则报错
代码如下：
// 10，获取节点的左孩子
ElementType leftChild(BinaryTree tree, ElementType element) {
// 如果给定节点为空
if (element == Nil) {
return Nil;
}
// 获取到当前节点
int index;
for (index = 0; index < Tree_Size; index++) {
if (tree[index] == element) {
break;
}
}
// 如果指定节点不存在
if (index == Tree_Size) {
return Nil;
}
// 获取子节点
int leftChildIndex = index*2+1;
if (leftChildIndex < Tree_Size) {
return tree[leftChildIndex];
} else {
return Nil;
}
}11，获取节点的右孩子
核心思路：
（1）判断当前节点是否为空，如果为空则报错
（2）寻找当前节点，如果未找到则报错
（3）计算右子节点坐标，如果超限则报错
代码如下：
// 11，获取节点的右孩子
ElementType rightChild(BinaryTree tree, ElementType element) {
// 如果是空树
if (tree[0] == Nil) {
return Nil;
}
// 如果当前节点为空
if (element == Nil) {
return Nil;
}
// 寻找当前节点
int index;
for (index = 0; index < Tree_Size; index++) {
if (tree[index] == element) {
break;
}
}
// 如果对应节点不存在
if (index == Tree_Size) {
return Nil;
}
// 寻找右节点
int rightIndex = index * 2 + 2;
if (rightIndex < Tree_Size) {
return tree[rightIndex];
} else {
return Nil;
}
}12，获取节点的左兄弟
核心思路如下：
（1）如果节点为空，则直接报错
（2）寻找当前节点，如果当前节点未找到，则报错
（3）如果当前节点是根节点，则报错
（4）如果当前节点是左节点，则报错
代码如下：
// 12，获取节点的左兄弟
ElementType leftBrother(BinaryTree tree, ElementType element) {
// 如果是空树
if (tree[0] == Nil) {
return Nil;
}
// 如果该节点为空
if (element == Nil) {
return Nil;
}
// 寻找对应节点
int index;
for (index = 0; index < Tree_Size; index++) {
if (tree[index] == element) {
break;;
}
}
// 如果对应节点不存在
if (index == Tree_Size) {
return Nil;
}
// 如果是根节点
if (index == 0) {
return Nil;
}
// 如果是左节点
if (index % 2 == 1) {
return Nil;
}
// 获取节点的左兄弟
return tree[index - 1];
}13，获取节点的右兄弟
核心思路：
（1）如果是空树，则报错
（2）如果节点为空，则报错
（3）自第二层开始遍历树的每一个节点，如果匹配成功了，并且是左节点，并且右兄弟底标未超限，则返回右兄弟
代码如下：
// 13，获取节点的右兄弟
ElementType rightBrother(BinaryTree tree, ElementType element) {
// 如果是空树，或者给定元素为空
if (tree[0] == Nil || element == Nil) {
return Nil;
}
// 寻找对应元素
for (int index = 1; index < Tree_Size; index++) {
if (tree[index] == element && index % 2 == 1) {
return tree[index+1];
}
}
return Nil;
}四、顺序二叉树的遍历
二叉树的遍历是一个很常见的问题。二叉树的遍历方式主要有前序遍历、中序遍历、后序遍历和层序遍历四种。
前序、中序和后序，指的都是双亲结点被访问的次序。如果在遍历过程中，双亲结点先于它的子节点被访问，则为前序遍历；父节点被访问的次序位于左右孩子节点中间，则为中序遍历；访问完左右子孩子节点之后再访问双亲结点，则为后序遍历。不管是前序、中序还是后序遍历，左右孩子节点的相对访问次序是不变的，都是先访问左子节点，再访问右子节点。
层序遍历是按照自上而下、自左到右的次序来访问二叉树的每个节点。
如下图所示：
1，层序遍历
核心思路：
（1）二叉树的顺序存储就是按照完全二叉树的形式自上而下、自左到右来存的，因此层序遍历就直接按照节点数组的顺序依次进行遍历即可
（2）遍历的时候注意筛选空节点
代码如下：
// 打印节点信息
void printNode(ElementType element) {
printf("%d ", element);
}
// 1，层序遍历
void levelOrderTraverse(BinaryTree tree) {
int index;
for (index = 0; index < Tree_Size; index++) {
if (tree[index] != Nil) {
printNode(tree[index]);
}
}
printf("\n");
}2，前序遍历
核心思路：先找到双亲结点，然后找到左节点，然后找到右节点
代码如下：
// 2，前序遍历
void preTraverse(BinaryTree tree, int nodeIndex) {
// 打印当前节点
printNode(tree[nodeIndex]);
// 处理左子节点
if (2*nodeIndex+1 < Tree_Size && tree[2*nodeIndex+1] != Nil) {
preTraverse(tree, 2*nodeIndex+1);
}
// 处理右子节点
if (2*nodeIndex+2 < Tree_Size && tree[2*nodeIndex+2] != Nil) {
preTraverse(tree, 2*nodeIndex+2);
}
}
void preorderTraverse(BinaryTree tree) {
// 如果是空树
if (tree[0] == Nil) {
printf("该二叉树为空");
return;
}
preTraverse(tree, 0);
}3，中序遍历
核心思路：先找到左子节点，然后双亲结点，然后右子节点
代码如下：
// 3，中序遍历
void inTraverse(BinaryTree tree, int index) {
// 处理左子节点
if (2*index+1 < Tree_Size && tree[2*index+1] != Nil) {
inTraverse(tree, 2*index+1);
}
// 打印当前节点
printNode(tree[index]);
// 处理右子节点
if (2*index+2 < Tree_Size && tree[2*index+2] != Nil) {
inTraverse(tree, 2*index+2);
}
}
void inorderTraverse(BinaryTree tree) {
// 如果是空树
if (tree[0] == Nil) {
printf("该二叉树为空树");
}
inTraverse(tree, 0);
}4，后序遍历
核心思路如下：先找到左子节点，然后找到右子节点，最后双亲结点
代码如下：
// 4，后序遍历
void postTraverse(BinaryTree tree, int index) {
// 处理左子节点
if (2*index+1 < Tree_Size && tree[2*index+1] != Nil) {
postTraverse(tree, 2*index+1);
}
// 处理右子节点
if (2*index+2 < Tree_Size && tree[2*index+2] != Nil) {
postTraverse(tree, 2*index+2);
}
// 打印当前节点
printNode(tree[index]);
}
void postorderTraverse(BinaryTree tree) {
// 如果是空树
if (tree[0] == Nil) {
printf("该二叉树是空树");
}
postTraverse(tree, 0);
}五、二叉树的链式存储
上面讲了二叉树的顺序存储，其最大的弊端就是浪费空间，所以我们一般是用它来实现完全二叉树；如果是一般的二叉树的话，我们基本都是通过链式存储的方式来实现的。
二叉树的链式结构设计如下：
#include <stdio.h>
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"
#include <stdbool.h>
// 操作的状态
typedef enum : int {
Success,
Error,
} Status;
// 节点值类型
typedef char ElementType;
#define Nil ' ' // 定义空值
// 节点类型
typedef struct BinaryTreeNode {
ElementType data; // 数值域
struct BinaryTreeNode *leftChildNode; // 左子节点
struct BinaryTreeNode *rightChildNode; // 右子节点
} BinaryTreeNode;
// 二叉树类型
typedef struct BinaryTreeNode * BinaryTree;1，二叉树的初始化
思路如下：将根节点指向NUll即可。
代码如下：
// 1，二叉树的初始化
/*
初始化二叉树的时候，只需要将二叉树指针指向NULL即可，不需要进行其他节点的销毁工作
*/
Status initBinaryTree(BinaryTree *tree) {
*tree = NULL;
return Success;
}2，二叉树的创建
思路如下：
（1）创建二叉树的时候需要输入一个字符串，该字符串是前序排列的，并且字符#代表是一个空节点
（2）由于字符串是前序排列的，所以通过前序遍历的方式对二叉树各个节点进行递归创建
代码如下：
// 2，二叉树的创建
/*
（1）空节点的值赋为”#“
（2）按照前序依次对各个节点进行递归赋值
*/
char *originalString = "abcdefghijklmn";
int stringIndex = 0;
Status createBinaryTree(BinaryTree *tree) {
// 递归结束的条件之一——字符串已经遍历完了
if (stringIndex >= strlen(originalString)) {
return Success;
}
ElementType currentChar = originalString[stringIndex++];
if (currentChar == '#') {
// #表示空节点
*tree = NULL;
} else {
// 新建节点
*tree = malloc(sizeof(BinaryTreeNode));
(*tree)->data = currentChar; // 给当前节点赋值
createBinaryTree(&(*tree)->leftChildNode); // 左子节点
createBinaryTree(&(*tree)->rightChildNode); // 右子节点
}
return Success;
}3，二叉树的销毁
思路如下：
（1）递归遍历，依次寻找左右子节点
（2）最后销毁节点的内存空间，并且将指针置空
（3）递归的结束条件是当前遍历到的节点为空
代码如下：
// 3，二叉树的销毁
/*
（1）递归操作各个子树
*/
Status destroyBinaryTree(BinaryTree *tree) {
// 递归结束条件
if (!(*tree)) {
return Success;
}
// 销毁左子树
destroyBinaryTree(&(*tree)->leftChildNode);
// 销毁右子树
destroyBinaryTree(&(*tree)->rightChildNode);
// 销毁当前节点
free(*tree);
*tree = NULL;
return Success;
}4，二叉树的判空
思路如下：
当根节点为NUll的时候，该树为空。
代码如下：
// 4，二叉树的判空
bool isBinaryTreeEmpty(BinaryTree tree) {
return tree == NULL;
}5，二叉树的深度
思路如下：
（1）采用递归的思想
（2）一个节点的深度分为左子树的深度和右子树的深度，取较大值，然后加1，最后返回
（3）递归退出的条件是，当前遍历到的节点为空
代码如下：
// 5，二叉树的深度
/*
（1）递归实现
*/
int binaryTreeDepth(BinaryTree tree) {
// 如果是空树
if (!tree) {
return 0;
}
int leftChildDepth, rightChildDepth; // 声明左右子树的深度
// 左子树深度取值
leftChildDepth = tree->leftChildNode ? binaryTreeDepth(tree->leftChildNode) : 0;
// 右子树深度取值
rightChildDepth = tree->rightChildNode ? binaryTreeDepth(tree->rightChildNode) : 0;
// 返回较大的
return leftChildDepth > rightChildDepth ? leftChildDepth + 1 : rightChildDepth + 1;
}6，二叉树的根节点的值
思路：当二叉树的根节点为空的时候返回Nil，根节点不为空的时候直接返回根节点的值。
代码如下：
// 6，二叉树的根节点的值
ElementType rootNodeValue(BinaryTree tree) {
return tree ? tree->data : Nil;
}六、链式二叉树的遍历
1，前序遍历
顺序：双亲结点->左子节点->右子节点
思路：
（1）使用递归
（2）如果当前节点为空，则直接返回，结束递归
（3）如果当前节点不为空，则打印当前节点信息，并依次递归处理左右子节点
代码如下：
// 1，前序遍历
void preorderTraverse(BinaryTree tree) {
// 递归退出的条件
if (!tree) {
return;
}
// 打印当前节点
printf("%c", tree->data);
// 处理左子节点
preorderTraverse(tree->leftChildNode);
// 处理右子节点
preorderTraverse(tree->rightChildNode);
}2，中序遍历
顺序：左子节点->双亲结点->右子节点
思路：
（1）使用递归
（2）如果当前节点为空，则直接返回，结束递归
（3）如果当前节点不为空，则先递归处理左侧子节点，然后打印当前节点信息，最后递归处理右子节点
代码如下：
// 2，中序遍历
void inorderTraverse(BinaryTree tree) {
// 递归结束的条件
if (!tree) {
return;
}
// 处理左子节点
inorderTraverse(tree->leftChildNode);
// 打印当前节点
printf("%c", tree->data);
// 处理右子节点
inorderTraverse(tree->rightChildNode);
}3，后序遍历
顺序：左子节点->右子节点->双亲结点
思路：
（1）使用递归
（2）如果当前节点为空，则直接返回，结束递归
（3）如果当前节点不为空，则先递归处理左、右侧子节点，最后打印当前节点信息
代码如下：
// 3，后序遍历
void postorderTraverse(BinaryTree tree) {
// 递归退出的条件
if (!tree) {
return;
}
// 处理左子节点
postorderTraverse(tree->leftChildNode);
// 处理右子节点
postorderTraverse(tree->rightChildNode);
// 打印当前节点
printf("%c", tree->data);
}以上。