数据结构初阶：二叉树

二叉树

链表和数组都是线性结构，树是非线性的结构。树是依靠分支关系定义出的一种层次结构。社会亲缘关系和组织结构图都可以用树来形象地表示。

1 树的定义和结构

1.1 树的定义

树是 $n(n\ge 0)$ 个元素的有限集。树是递归定义的，任意一个树都是由一个根结点和多个子树组成，而其中每个子树也是由一个根结点和0个或多个子树组成。

• 根结点：每个树有且仅有的一个根结点，根结点即树中最上面的一个结点，根结点无前驱结点。
• 子树：根结点被分成 $M(M\ge 0)$ 个互不相交的集合，而每个集合都是一个与树结构类似的子树。

如右图所示，

1. 根结点 $A$ 下面有三个子树，这三个子树又分别以结点 $B$，$C$，$D$ 为根结点。
2. $B$ 结点之下又有两个分别以 $E$，$F$ 为根结点的子树。
3. 结点 $F$ 可以看成只有根结点的树，其子树为空。

任何树都可以被分成根和子树。称之为树是因为其结构看起来像一个倒挂的树，根朝上，叶朝下。

1.2 树的相关概念

下面列出树结构的基本概念，各个结点的关系也是用亲缘关系表示。

需要注意的是，兄弟结点不包括堂兄弟，仅同一个父结点的结点才是兄弟结点。结点层次默认根结点为第1层，有时也以第0层表示，但第二种不好表示空树的层次。

1.3 树的表示

定义树的结构的方式有很多种，关键在于如何表示相邻结点之间的关系。

其他表示法

孩子表示法，若已知树的度 $N$，我们可以定义出这样的结构，

struct TreeNode {
    TNDataType data;
    struct Node* subs[N];
};

每个结点存储结点数据和一个数组用以存储其所有子结点的指针。已知树的度故subs[N]足够存储，但不可避免的是一定会浪费空间。

struct TreeNode {
    TNDataType data;
    SeqList sl;//顺序表存储
};
typedef struct TreeNode* SLDataTypde;

针对浪费空间和树的度未知的问题，可以使用线性表替代静态数组存储子结点的指针。但缺点是结构过于复杂。

双亲表示法，结点存自身数据和父结点的下标。用结构体数组存储结点的信息，遍历数组即遍历二叉树。

struct TreeNode {
  	TNDataTypde data;
	  int parenti;
};

孩子兄弟表示法

上面的方式各有优劣，表示树结构的最优方法是左孩子右兄弟表示法。

struct TreeNode {
    //数据域
    TNDataType data; 
    //指针域
    struct TreeNode* firstChild;
    struct TreeNode* nextBrother;
};

结点的指针域只存两个指针

• firstChild指向该结点的第一个子结点，
• nextBrother指向子结点右边的第一个兄弟结点。

第一层，根结点 $A$ ，无兄弟结点。

第二层，结点 $A$ 的第一个子结点为结点 $B$，其兄弟结点为结点 $C$。

第三层，结点 $B$ 的第一个子结点为结点 $D$，其兄弟结点为结点 $E$，$F$。结点 $C$ 的子结点为 $G$。

第四层，结点 $D$ 无子结点，兄弟结点 $E$ 有子结点为结点 $H$，$H$ 的兄弟结点为结点 $I$。结点 $F$，$G$ 无子结点。

只要确定根结点，其余所有的结点都可以从其父结点或兄弟结点的指针处找到，如果没有指针就为空。这种方法不需要确定树的度 $N$，也不需要使用线性表存储，结构不复杂也不浪费空间，不失为树结构的最优表示法。

树在计算机中最经典的应用就是文件管理系统即目录树。当打开文件夹时，弹出的一系列子文件夹，更类似于先找到子结点再找到其兄弟结点。

2 二叉树定义和结构

树结构在计算机中并不常用，仅作了解。用于存储和管理数据，最常见的是二叉树。

2.1 二叉树的定义

二叉树同样是结点的有限集合，该集合可为空，每个结点可无子树或一个子树，但最多有两个子树，分别称为左子树和右子树。如图：

• 二叉树不存在度大于2的结点，

同样二叉树的度最大为2。度为0时，为空树或只有根结点，度为1时，是线性结构，度为2时，结点可能有两个子树。

• 二叉树中结点的子树有左右之分，且次序不可颠倒。

任意二叉树由以下几种情况复合而成：

特殊二叉树

1. 满二叉树：所有的叶结点都在最后一层，或称所有分支结点都有两个子树，或称每层结点数都到达最大值这样的数就是二叉树。

假设满二叉树的层数 $K$，第 $K$ 层的结点数为 $2^{k-1}$，结点总数是$2^K-1$ 。若已知结点总数为 $N$， 则树的高度为 $lo{g}_2(N+1)$。

2. 完全二叉树：完全二叉树的前 $n-1$ 层为满二叉树，最后一层虽可不满但从左至右连续。

满二叉树是一种特殊的完全二叉树。

二叉树的性质

1. 非空二叉树的第 $i$ 层上最多有 $2^{i-1}$ 个结点。
2. 深度为 $k$ 的二叉树，最大结点数为 $2^h-1$ 。
3. 对于任意的二叉树，假设其叶结点个数总比度为2的分支结点个数大 $1$，即$n_0=n_2+1$。

二叉树的特点就是：每增加一个分支结点，必然会增加一个叶节点。

4. 完全二叉树度为1的结点个数仅有 $0$ 和 $1$ 两种可能。
5. 若满二叉树结点总数为 $N$， 则树的高度为 $h=lo{g}_2(N+1)$。

2.2 二叉树的结构

普通二叉树的增删查改无甚意义，更多是学习对二叉树结构的控制。目的是为后期学习搜索二叉树、AVL树和红黑树夯实基础。

顺序存储结构

顺序存储即用数组存储，从根开始一层一层从左至右有序存入数组。一般数组只适用于表示完全二叉树。

有些缺枝少叶的树存入数组会造成空间的浪费，若不浪费空间便不好规律地表示该树的结构。

更重要的原因是，利用下标可以计算结点的父子结点。如图：

$$\begin{gathered} leftChild=parent\ast 2+1 \\ rightChild=parent\ast 2+2 \end{gathered}$$

$$parent=(child-1)/2$$

1. 已知某结点求其子结点下标，左边子结点下标为该结点下标乘2+1，右边子结点下标为该结点下标乘2+2。
2. 已知某结点求其父结点下标，则是子结点下标-1或-2再除以2。但偶数-1或-2的结果一致。

链式存储结构

使用链表表示二叉树，更加的直观。通常方案有两种一个是二叉链表，一个是三叉链表。二叉链表即存数据域和左右指针域，三叉则多存一个父结点指针。

当前数据结构一般都是二叉链，红黑树等高阶数据结构会用到三叉链。当前仅作了解。

// 二叉链
struct BinaryTreeNode {
    struct BinTreeNode* leftChild;
    struct BinTreeNode* rightChild;
	BTDataType _data; 
};
// 三叉链
struct BinaryTreeNode {
	struct BinTreeNode* parentChild;
	struct BinTreeNode* leftChild;
	struct BinTreeNode* _pRight; 
	BTDataType _data;
};

3 二叉树的顺序结构

3.1 顺序结构

前面已交代，普通二叉树不适于用数组存储，会造成大量的空间浪费。而完全二叉树更适合用数组存储。数据结构中有种结构叫堆，是一种完全二叉树，该结构使用数组存储。

需注意，操作系统层面对于内存进行了划分，将一块内存区域称为堆，它是一块内存区域分段。而数据结构中的堆是一种结构。

3.2 堆的定义和结构

定义一个值的集合$\{k_0,k_1,k_2,...,k_{n-1}\}$，将其以二叉树顺序存储的方式存储于数组中，且满足一定规律：
$$K_i\le K_{2\ast i+1}\&\&K_i\le K_{2\ast i+2}$$

$$K_i\ge K_{2\ast i+1}\&\&K_i\ge K_{2\ast i+2}$$

满足公式 $(3)$，即每个结点都比其子结点小或等的堆被称为大（根）堆。反之，满足公式 $(4)$ 每个结点都比其子结点大或等的堆被称为小（根）堆。

可以看出，堆是一个完全二叉树，且堆的某个结点的值总是不大或不小于其子结点或是不下不大于其父结点的值。堆并不是有序的，只有满足线性存储二叉树的数组有序，才称二叉树有序。

3.3 堆的实现

可以看出堆的逻辑结构是一个完全二叉树，物理结构是一个数组。也可以说二叉树实际上就是个数组，或着是把数组想象成二叉树。

堆结构体定义

typedef int HPDataType;

typedef strcut heap {
    HPDataType* a;
	int size;
    int capacity;
}heap;

堆的插入

void HeapPush(heap* php, HPDataType x) {
	assert(php);
	if (php->size == php->capacity) {
		int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity);
		if (tmp == NULL) {
			perror("HeapPush::malloc");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newCapacity;
	}
	php->a[php->size] = x;
	php->size++;
	//调整
	AdjustUp(php->a, php->size, php->size - 1);
}

堆插入即在数组的末尾进行插入，等于在二叉树上加一个叶结点。由于插入的数值不一定，此时堆的性质可能被破坏。当然，该结点只会影响该结点到根结点所在路径上的所有结点，便需要顺势向上调整：一直交换结点数值直到满足堆的性质即可。

堆向上调整算法

void AdjustUp(HPDataType* a, int size, int child) {
	assert(a);
	while (child > 0) {
		int parent = (child - 1) / 2;
		//大堆
		if (a[child] > a[parent]) {
			Swap(&a[child], &a[parent]);
			//迭代
			child = parent;
		}
		else {
			break;
		}
	}
}

向上调整算法，从child处一直向上找父结点，满足子结点比父节点大或小的条件就交换，直到调整到根结点或不满足条件为止。

堆的向上调整较为容易，因为结点的父结点只有一个，只需要和父节点比较即可。

堆的删除

void HeapPop(heap* php) {
	assert(php);
	assert(!HeapEmpty(php));
	//删除
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;
	//调整
	AdjustDown(php->a, php->size, 0);
}

删除操作即删除堆顶元素，但不是简单的将堆数组向前挪一位，这样会使二叉树的结构大变，并不能保证所得二叉树是堆。应该将数组尾元素和首元素交换再删除尾元素并向下调整，这就是堆的删除操作。

堆向下调整算法

void AdjustDown(HPDataType* a, int size, int parent) {
	int child = parent * 2 + 1;
	//大根堆
	while (child < size) {
		//选出大小子结点
		if (child + 1 < size && a[child + 1] > a[child]) {
			child++;
		}
		//交换
		if (a[child] > a[parent]) {
			Swap(&a[child], &a[parent]);
			//迭代
			parent = child;
			child = parent * 2 + 1;
		}
		else {
			break;
		}
	}
}

把尾元素换到堆顶，必然会改变堆的性质，但根结点的左右子树还是保持原有的性质。所以，只需要将堆顶元素逐步向下调整：将根结点与其较大（小）的子结点进行交换，只要满足父结点比其二者子结点中任意一个大或小的条件，就让其与子结点进行交换，直到交换到叶结点或不满足条件为止。

与较大的子结点交换即是恢复大堆性质，与较小的子结点即是恢复小堆性质。

其他接口函数

//初始化和销毁
void HeapInit(heap* php) {
	assert(php);
	php->a = NULL;
	php->size = php->capacity = 0;
}
void HeapDestroy(heap* php) {
	assert(php);
	free(php->a);
	php->size = php->capacity = 0;
}
//获取堆顶数据
HPDataType HeapTop(heap* php) {
	assert(php);
	assert(!HeapEmpty(php));
	return php->a[0];
}
//堆的元素个数
int HeapSize(heap* php) {
	assert(php);
	return php->size;
}
//堆的判空 
bool HeapEmpty(heap* php) {
	assert(php);
	return !php->size;
}
//堆的打印
void HeapPrint(heap* php) {
	assert(php);
	for (int i = 0; i < php->size; i++) {
		printf("%d ", php->a[i]);
	}
	printf("\n");
}

堆的创建

给出数组a，数组逻辑上可以看成完全二叉树，但并不一定是堆。堆的创建即通过算法，将数组调整成堆。利用堆的插入思想将数组a建成堆。

方法1：向上调整

从根结点即数组首元素开始，依次将数组元素“插入”堆，与其说是“插入”不如说是“加入”，利用下标依次遍历数组元素，将被遍历到的元素看成是堆的结点，每插入一个就调整一次。

假设需要将a排成升序，不妨先试试将a数组构建成小堆：

//建堆
void HeapBuild(int* a, int sz) {
    //向上调整
	for (int i = 1; i < sz; i++) {//从第二个结点开始遍历到尾结点
		AdjustUp(a, sz, i);
	}
}

每加入一个元素，就调用AdjustUp从所插结点到跟结点进行向上调整。

这样的方法在思想上其实和接口函数Push是一样的，都是插入一个就调整一次。唯一的区别就是调用接口会创建新的空间以存放堆。

加入一个结点，就从该结点处调整到根，也可以理解为“边建边调”。

方法2：向下调整

同理可得，利用向下调整算法的逻辑和调用堆的接口Pop类似。在调用堆的删除接口的过程中发生首尾互换，此时因为根结点的变动使得堆被破坏，但其左右子树都是满足堆的性质的，因此可以进行向下调整。

而完全二叉树a并不是堆，它其中任意的左右子树也不能保证是堆。故应先从最后一个子树开始向下调整，从后向前倒着遍历。准确的来说因为叶结点所在子树仅有一个结点所以不用调整，应从尾结点的父结点开始遍历到根结点。

//建堆
void HeapBuild(int* a, int sz) {
    //向下调整
	for (int i = (sz - 1 - 1) / 2; i >= 0; i--) {//从最后一个叶结点的父结点开始到根结点
		AdjustDown(a, sz, i);
	}
}	

建堆的两种方式，向上调整和向下调整都是可行的。不管是建大堆还是建小堆，上述代码都是正确的，只需要改动调整算法中的比较符号即可。

从一个完全二叉树的尾结点的父结点开始，从后往前调，也可以看成“建完在调”。

建堆时间复杂度

向上调整算法的时间复杂度为 $O(NlogN)$ 。建堆时更多要配合堆排序使用的是向下调整算法。

向下调整算法的最复杂情况是从当前子树所在的根结点一直调整到叶结点。假设当前树有 $n$ 个结点，树的高度为 $h$ ，可得：

1. 第1层有 $2^0$ 个结点，每个结点最多调整 $h-1$ 次，
2. 第2层有 $2^1$ 个结点，每个结点最多调整 $h-2$ 次，
3. 以此类推，第 $h-1$ 层有 $2^{h-2}$ 个结点，每个结点最多调整 $1$ 次。

则整个向下调整算法移动结点的总步数为 $T(n)$ 为结点个数$\ast$下移层数：

可见 $T(n)$ 为差比数列，利用错位相减法得处$T(n)$关于$h$的表达式，再由 $n=2^h-1,h=lo{g}_2(n+1)$ 将$T(n)$转换成关于的$n$的表达式。

3.4 堆的应用

Top-K问题

Top-K问题，即在 $N$ 个元素中找出前 $K$ 个最值。

在此之前，遍历找最值K次，排序后取出前K个元素，这两种方式也可行，但并不是最好的方法。下面用堆来解决这个问题。

方式1：将 $N$ 个数依次插入建立一个大堆，删除并取堆顶数据 $K$ 次，所得即K个最值。

时间复杂度为 $O(N+Klo{g}_{2}N)$，当然假设$N$非常大有10个亿，存在文件中，则上述的方法全不适用。

方式2：

1. 用前$K$个数建立一个K个元素的堆，求前K个最大值，则建小堆；求后K个最小值，则建大堆。

2. 剩下$N-K$个元素依次跟堆顶的数据比较，若比堆顶大则替换堆顶元素并向下调整，

3. 遍历结束，最后小堆中的$K$个元素就是最大值。

建立小堆，使得小的在上大的在下，每次都会把最小的删除出堆，而最大的进堆并保持在堆底。

void PrintTopK(int* a, int n, int k) {
	heap hp;
	HeapInit(&hp);
	//创建小堆
	for (int i = 0; i < k; i++) {
		HeapPush(&hp, a[i]);
	}
	//比较
 	for (int i = k; i < n; i++) {
		int ret = HeapTop(&hp);
		if (a[i] > ret) {
			HeapPop(&hp);
			HeapPush(&hp, a[i]);
		}
	}
	HeapPrint(&hp);
}

可以直接修改堆顶数据并向下调整，也可以调用接口先Pop再Push，但最好还是不要破坏堆的结构，利用接口去实现。

堆排序

堆排序，即利用堆的实现思想对现有的数组进行排序。假设有一个数组a={70,56,30,25,15,10,75}，从逻辑结构上看是完全二叉树，但并不一定是堆。所以我们需要先将数组建成堆，然后才能再进行堆排序。

建堆分析

前面已经介绍过堆的创建的两种方式，利用堆的插入思想将数组a建成堆。调用建堆函数即可。

假设要将a排成升序，构建成大堆还是小堆呢？不妨先试试将a数组构建成小堆，取堆顶的数据即数组首元素就是最小的数。若再想选出次小的数，就要删除首元素从第二个元素位置开始重新建堆，也就是破坏堆的结构重新建堆。

重新建堆的复杂度为 $O(N)$，整体复杂度就为 $O(N^2)$，这显然是不可取的。既然排升序建小堆不可取，那试试排升序建大堆。

排序分析

**利用堆的删除思想进行排序。**如果选择排升序，建大堆的话，可以按照如下逻辑：

1. 建大堆，选出最大的数；
2. 首尾元素互换，致使最大的数被移至末尾；
3. 不将尾元素看作堆的结点，从根结点开始向下调整，选出次大的数被移到首位。

再首尾互换，如此循环往复，直到调整到根结点即元素个数减到0。时间复杂度为 $O(logN)$ 。

由此可得，排升序建大堆，排降序建小堆。

//排序
void HeapSort(int* a, int sz) {
	//1. 建堆
	HeapBuild(a, sz);
	//2. 排序
	for (int i = sz - 1; i >= 0; i--) {//元素个数-1
		//首尾互换
		Swap(&a[0], &a[i]);
		//向下调整
		AdjustDown(a, i, 0);
	}
}

可见，排升序建大堆是从尾遍历到头，取出较大值放在数组的后面。不管是排升序还是排降序都是取出应放在后面的数将其放在后面，都是向下调整算法的应用。

选择升序和降序分别建立大堆和小堆，也就是改个比较符号的区别。堆排序的时间复杂度为 $O(NlogN)$ 。

4 二叉树的链式结构

4.1 二叉树的遍历

链式结构

一般二叉树的结构过于复杂，不利于存储数据，所以二叉树的增删查改没有意义。二叉树的价值体现在一些特定的二叉树上，如搜索二叉树，平衡搜索二叉树，AVL树，红黑树，B树等。后期在进阶数据结构中学到。

二叉树的结构的特点在于二叉树及其子树都可以被分成三个组成部分：根结点，左子树，右子树。

如图，任意的二叉树都可以被拆分成根、左子树、右子树，空树是不可再分的最小单位。

前中后序遍历

学习二叉树结构，必然要进行遍历。二叉树遍历即按照某种特定的规则，依次访问并操作二叉树的每个结点，且每个结点仅访问一次。

访问任意一棵二叉树包括其子树都是按照固定的一种方式。三者的区别即是访问根结点操作的顺序不同。

上述二叉树以前序、中序、后序遍历所得结果分别为：
$$ABD000CE00F00$$

$$0D0B0A0E0C0F0$$

$$00D0B00E00FCA$$

将空树写出来才反映出遍历的真正的方式，将空树去掉就是最后的结果。

用代码将树的遍历思想表示出来就是递归：

//前序遍历
void PreOrder(BTNode* root) {
	if (root == NULL) {
		printf("\\0 ");
		return;
	}
	printf("%c ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}
//中序遍历
void InOrder(BTNode* root) {
	if (root == NULL) {
		printf("\\0 ");
		return;
	}
	InOrder(root->left);
	printf("%c ", root->data);
	InOrder(root->right);
}
//后序遍历
void PostOrder(BTNode* root) {
	if (root == NULL) {
		printf("\\0 ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%c ", root->data);
}

前序遍历递归代码递归具体情况如图所示：

三种遍历方式递归的调用逻辑完全相同，只是打印数值的时机不同，所以结果不同，但访问结点的顺序是相同的。

层序遍历

层序遍历即从上往下一层一层遍历，层序遍历用队列实现。

void levelOrder(BTNode* root) {
    if (root == NULL) {
        return;
    }
	Queue q;
	QueueInit(&q);
    //1. 头结点入队
	QueuePush(&q, root);
	while (!QueueEmpty(&q)) {
		BTNode* front = QueueFront(&q);
		printf("%d ", front->data);
		//2. 队头出队
        QueuePop(&q);
        //3. 子结点入队
		if (front->left) {
			QueuePush(&q, front->left);
		}
		if (front->right) {
			QueuePush(&q, front->right);
		}
	}
	QueueDestroy(&q);
}

1. 创建一个队列，先入根结点，

2. 出队头结点，再入队头的子结点。这样一层结束会把下一层全带进队。

3. 队列为空时，遍历结束。

保持队列不为空的情况下循环往复，最后一层遍历完子结点全为空才会导致队列元素越来越少最终队列为空。

4.2 二叉树基本练习

递归也就是分治思想，分而治之——大事化小，小事化了。接下来的几个二叉树基础练习全部采用递归的策略实现。

二叉树结点个数

//1. 
void BinaryTreeSize(BTNode* root, int* pcount) {
	if (root == NULL) {
		return;
	}
	(*pcount)++;
	BinaryTreeSize(root->left, pcount);
	BinaryTreeSize(root->right, pcount);
}
//2. 
int BinaryTreeSize(BTNode* root) 
{
    /*if (root == NULL) {
		return 0;        
    }
    else {
        return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
    }*/
	return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

使用计数器的话，要像OJ一样传入主函数中变量的地址。

用递归分治的思想的话，求任意树的结点个数都可以看成一类相同的问题，即左子树结点个数+右子树结点个数+1，然后再去大事化小：

1. 求A树结点个数即A的左子树结点个数+右子树结点个数+1，
2. A的左子树即B树，B树的结点个数即B左子树结点个数+B右子树结点个数+1，
3. 以此类推，……，直到遇到空树是不可再分的临界条件，返回0。

二叉树叶结点个数

int BinaryTreeLeafSize(BTNode* root) {
    //为空
	if (root == NULL) {
		return 0;
	}
    //为叶
	else if (root->left == NULL && root->right == NULL) {
		return 1;
	}
    //非空y
    else {
    	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
    }
}

求叶结点同样是递归的分治思想，相同逻辑是任何树的叶结点个数都是其左子树的叶结点个数+右子树的叶结点个数。临界条件是找到叶结点特征是左右子结点都为空。利用相同逻辑开始递归：

1. 求A树的叶结点个数即A的左子树叶结点个数+右子树叶结点个数，
2. A的左子树为B树，B树的叶结点个数为B的左子树叶结点个数+右子树叶结点个数，A的右子树为C树，C的叶结点个数为其左右子树叶结点个数之和。往下递归，……，直到结点的左右子树为空，返回1。

二叉树任意层结点个数

int BinaryTreeLevelkSize(BTNode* root, int k) {
	if (root == NULL) {
		return 0;
	}
	if (k == 1) {
		return 1;
	}
	else {
		return BinaryTreeLevelkSize(root->left, k - 1) + BinaryTreeLevelkSize(root->right, k - 1);
	}
}

1. 求A树的第$k$层结点个数，可以转化成就其左右子树，即B树的第$k-1$层结点个数+C树的第$k-1$层结点个数。
2. 求B树的第$k-1$层结点个数，即D树的第$k-2$层结点个数+null树的第$k-2$层结点个数。
3. 以此类推，空树结点个数为0，当k=1即遍历到第k层的结点。非空k也不等于0则转换成求左右子树的结点个数。

二叉树高度

int BinaryTreeDepth(BTNode* root) {
	if (root == NULL) {
		return 0;
	}
	else {
        int leftDepth = BinaryTreeDepth(root->left);
		int rightDepth = BinaryTreeDepth(root->right);
		return leftDepth > rightDepth ? leftDepth : rightDepth + 1;
	}
}

求高度的问题可以转化成找空结点的问题。不为空就+1，直到为空+0。再利用递归的思想，求A树的高度即求A树左右子树的高度最大值+1，B树的高度即B树的左右子树的高度+1，C树的高度即C树的左右子树的高度+1，直到遇到空树。

当然本题要避免写出return TreeDepth(left)>TreeDepth(right)?TreeDepth(left):TreeDepth(right)+1;的代码，这样会造频繁调用，比较算一次，返回值又算一次。

求树的结点总数和求树的高度都是经典的后序遍历问题，都是先遍历左右树再访问根结点。

二叉树查找结点

BTNode* BinaryTreeFind(BTNode* root, BTDataType x) {
	if (root == NULL) {
		return NULL;
	}
	if (root->data == x) {
		return root;
	}
	BTNode* leftRet = BinaryTreeFind(root->left, x);
	if (leftRet) {
		return leftRet;
	}
	BTNode* rightRet = BinaryTreeFind(root->right, x);
	if (rightRet) {
		return rightRet;
	}
	return NULL;
}

二叉树查找结点时典型的前序遍历。A不是就到A的左右子树中去找。第三种情况下，必须加以判断，不为空时才返回不然无法遍历右子树。

4.3 二叉树基础面试题

Example 1 单值二叉树

单值二叉树

bool isUnivalTree(struct TreeNode* root) {
	if (root == NULL) {
		return true;
	}	
    if (root->left && (root->val != root->left->val)) {
		return false;
	}
	if (root->right && (root->val != root->right->val)) {
		return false;
	}
	return isUnivalTree(root->left) && isUnivalTree(root->right);
}

一类相同的子问题即每三个结点为一组，结点和其左右子结点的值是否相等，临界条件为遇空返回真。依次向下递归。

Example 2 相同二叉树

相同二叉树

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
	// 都为空
    if (!p && !q) {
        return true;
    }
    // 仅有一个为空
    if (!p || !q) {
		return false;
	}
    // 都不为空
    if (p->val != q->val) {
		return false;
	}
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

从结构和值的角度把握，先比较根然后再顺着左右子树向下递归。要么都为空，要么仅有一个为空，要么都不为空但值不等，当值相等时其左右子结点为空递归到下一层返回真，上面三个条件包含了所有情况，接下来直接递归即可。

Example 3 对称二叉树

对称二叉树

bool _isSymmetric(struct TreeNode* l, struct TreeNode* r) {
    if (!l && !r) {
        return true;
    }
    if (!l || !r) {
        return false;
    }
    if (l->val != r->val) {
        return false;
    }
    return _isSymmetric(l->left,r->right) && _isSymmetric(l->right, r->left);
}
bool isSymmetric(struct TreeNode* root) {
    if (root == NULL) {
        return true;
    }
    return _isSymmetric(root->left, root->right);

}

将根结点之下的左右子树交给子函数，用子函数去递归。递归情况判断和上一题一样，一个传左一个传右，再反着判断一边。

Example 4 前序遍历，中序遍历，后序遍历

前序遍历，中序遍历，后序遍历

int TreeSize(struct TreeNode* root) {
    return root == NULL ? 0 : TreeSize(root->left)+TreeSize(root->right) + 1;
}
void _preorderTraversal(struct TreeNode* root, int* a, int* pi) {
    if (root == NULL) {
        return;
    }
    //1.
    a[(*pi)++] = root->val;
    _preorderTraversal(root->left, a, pi);
    //2.
    a[(*pi)++] = root->val;
    _preorderTraversal(root->right, a, pi);
    //3.
    a[(*pi)++] = root->val;
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int size = TreeSize(root);
    int* a = (int*)malloc(size*sizeof(int));
    int i = 0;
    _preorderTraversal(root, a, &i);
    *returnSize = size;
    return a;
}

前中后序遍历仍然是递归，不同的是不是把结点的值打印出来而是放到动态开辟的数组里。值得注意的是，递归中创建新的下标变量，往下走还行往回返时就出了问题，所以应该传变量的地址。

Example 5 另一棵树的子树

另一棵树的子树

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
    if (!root) {
        return false;    
    }
    if (isSameTree(root, subRoot)) {
        return true;
    }
    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

将root的所有子树和subRoot比较，为真就返回，没找到就到左右子树中递归，由于返回的是布尔值，且左边没找到还要到右边找，故可以用||将两个返回值或起来。

假设root有n个结点，该递归算法最好情况是root与subRoot完全相等，比较第一次就成功，时间复杂度为 $O(n)$。最坏情况是二者只有最后一个结点值不相等，每个结点都被比较且isSameTree同样递归到最后一个结点，时间复杂度为 $O(n^2)$。

4.4 二叉树的创建和销毁

二叉树销毁

void BinaryTreeDestroy(BTNode* root) {
	if (!root) {
		return;
	}
	BinaryTreeDestroy(root->left);
	BinaryTreeDestroy(root->right);	
	free(root);
}

释放了结点就找不到它的子结点了，所以采用后序遍历的方式。

判断是否为完全二叉树

bool isBinaryTreeComplete(BTNode* root) {
    if (root == NULL) {
        return true;
    }
    Queue q;
    QueueInit(&q);
    QueuePush(&q, root);
    // 1. 找到第一个空结点
    while (!QueueEmpty(&q)) { 
    	BTNode* front = QueueFront(&q);
        QueuePop(&q);
        if (front == NULL) {
			break;
        }
        else {
            QueuePush(&q, front->left);        
	        QueuePush(&q, front->right);
    	}
    }
    // 2. 检查队列中剩余结点是否有非空结点
    while (!QueueEmpty(&q)) {
    	BTNode* front = QueueFront(&q);
        QueuePop(&q);
        if (front) {
        	return false;
        }
    }
    QueueDestroy(&q);
    return true;
}

完全二叉树与非完全二叉树的区别就在于非完全二叉树中有空结点，只要在空结点之后有非空结点就代表该二叉树不是完全二叉树。

1. 入头结点，出队头，再入队头的子结点
2. 队头为空则跳出循环，再检查队列中所有结点是否为空，有非空结点代表不是完全二叉树。

Example 6 遍历创建树

遍历创建树

#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
    struct TreeNode* left;
    struct TreeNode* right;
    char val;
};
struct TreeNode* CreateTree(char* str, int* pi) {
    if (str[*pi] == '#') {
        (*pi)++;
        return NULL;
    }
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = str[(*pi)++];
    root->left = CreateTree(str, pi);
    root->right = CreateTree(str, pi);
    return root;
}
void Inorder(struct TreeNode* root) {
    if (!root) {
        return;
    }
    Inorder(root->left);
    printf("%c ", root->val);
    Inorder(root->right);
}
int main()
{
    char str[100] = {0};
    scanf("%s", str);
    int i = 0;
    struct TreeNode* root = CreateTree(str, &i);
    Inorder(root);
    
    return 0;
}

字符串ABC##DE#G##F###代表树的前序遍历序列。根据该字符串可以确定的是a一定是根结点，之后一整个字符串的是左子树和右子树。按照前序遍历的规则，创建二叉树即可。