初阶数据结构—二叉树

第一章：树的概念及结构

1.1 树的概念

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

• 有一个特殊的结点，称为根结点，根节点没有前驱结点
• 除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继
• 因此，树是递归定义的。 

注意：树形结构中，子树之间不能有交集，否则就不是树形结构  

1.2 树的相关概念

节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为6

叶节点或终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I...等节点为叶节点

非终端节点或分支节点：度不为0的节点； 如上图：D、E、F、G...等节点为分支节点

双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点

孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点

兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点

树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为6

节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；

树的高度或深度：树中节点的最大层次； 如上图：树的高度为4

堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点

节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先

子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙

森林：由m（m>0）棵互不相交的树的集合称为森林

typedef int DataType;
struct TreeNode
{
 struct TreeNode* _firstChild1; // 第一个孩子结点
 struct TreeNode* _pNextBrother; // 指向其下一个兄弟结点
 DataType _data; // 结点中的数据域
};

第二章：二叉树概念及结构

2.1概念

2.2 特殊的二叉树

1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是2^k - 1 ，则它就是满二叉树。
2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

2.3 二叉树的性质 

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1)个结点。
2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h - 1
3. 对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2 ,则有n0 ＝ n2＋1
4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度h=㏒₂(n+1)
5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：
   1. 若 i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
   2. 若 2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子
   3. 若 2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子

选择题

1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）

A 不存在这样的二叉树
B 200
C 198
D 199

答案：A
解析：n0 = n2 + 1

2. 下列数据结构中，不适合采用顺序存储结构的是（ ）

A 非完全二叉树
B 堆
C 队列
D 栈

答案：A

3. 在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）

A n
B n+1
C n-1
D n/2

答案：A
解析：一个具有n个节点的完全二叉树,其叶子节点的个数n0为: n/2 向上取整，或者(n+1)/2 向下取整

4. 一棵完全二叉树的节点数位为531个，那么这棵树的高度为（ ）

A 11
B 10
C 8
D 12

答案：B
解析：在完全二叉树中，具有n个结点的完全二叉树深度为㏒₂n + 1,其中㏒₂n + 1是向下取整。 满二叉树的深度为k=㏒₂(n+1)

5. 一个具有767个节点的完全二叉树，其叶子节点个数为（）

A 383
B 384
C 385
D 386

答案：B
解析：一个具有n个节点的完全二叉树,其叶子节点的个数n0为: n/2 向上取整，或者(n+1)/2 向下取整

2. 链式存储

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，后面课程学到高阶数据结构如红黑树等会用到三叉链。

第三章：二叉树的顺序结构及实现

3.1 二叉树的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

3.2 堆的概念及结构 

堆的性质： 

• 堆中某个节点的值总是不大于或不小于其父节点的值；
• 堆总是一棵完全二叉树。

选择题

1. 下列关键字序列为堆的是：（）

A 100,60,70,50,32,65
B 60,70,65,50,32,100
C 65,100,70,32,50,60
D 70,65,100,32,50,60
E 32,50,100,70,65,60
F 50,100,70,65,60,32

答案：A

2. 已知小根堆为8,15,10,21,34,16,12，删除关键字 8 之后需重建堆，在此过程中，关键字之间的比较次数是（）。

A 1
B 2
C 3
D 4

答案：C

3. 一组记录排序码为(5 11 7 2 3 17),则利用堆排序方法建立的初始堆为

A(11 5 7 2 3 17)
B(11 5 7 2 17 3)
C(17 11 7 2 3 5)
D(17 11 7 5 3 2)
E(17 7 11 3 5 2)
F(17 7 11 3 2 5)

答案：C

4. 最小堆[0,3,2,5,7,4,6,8],在删除堆顶元素0之后，其结果是（）

A[3，2，5，7，4，6，8]
B[2，3，5，7，4，6，8]
C[2，3，4，5，7，8，6]
D[2，3，4，5，6，7，8]

答案：C

3.3 堆的实现 

3.2.1 堆向下调整算法

现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

int array[] = {27,15,19,18,28,34,65,49,25,37};

3.2.2 堆的创建

下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。

int a[] = {1,5,3,8,7,6};

3.2.3 建堆时间复杂度 

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：

因此：向下调整建堆的时间复杂度为O(N)。 

3.2.4 堆的插入

先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆。

3.2.5 堆的删除 

删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。

3.2.6 堆的代码实现 

Heap.h

#pragma once
 
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <time.h>
 
 
//父亲下标找孩子
//leftchild = parent*2 + 1
//rightchild = parent*2 + 2
 
//孩子找父亲
//parent = (child-1)/2
 
//满二叉树节点：2^h - 1
//完全二叉树节点范围：[2^(h-1), 2^h - 1]
 
//满二叉树高度：h = log2(N+1)
//完全二叉树高度：h = log2(N) + 1 
 
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;
 
 
void Swap(HPDataType* p1, HPDataType* p2);//交换两个数（首尾元素）
void AdjustUp(HPDataType* a, int child);//堆的向上调整
void AdjustDown(HPDataType* a, int n, int parent);//堆的向下调整
void HeapInit(HP* php);//堆的初始化
void HeapDestroy(HP* php);//堆的销毁
void HeapPush(HP* php, HPDataType x);//堆的插入
void HeapPop(HP* php);//堆的删除
HPDataType HeapTop(HP* php);//取堆顶的数据
bool HeapEmpty(HP* php);//堆是否为空
int HeapSize(HP* php);//堆的数据个数

Heap.c

#define _CRT_SECURE_NO_WARNINGS
 
#include "Heap.h"
 
void HeapInit(HP* php)//堆的初始化
{
	assert(php);
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}
 
 
bool HeapEmpty(HP* php)//堆是否为空
{
	assert(php);
	return php->size == 0;
}
 
 
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
 
 
void AdjustUp(HPDataType* a, int child)//堆的向上调整
{
	//孩子下标找父亲
	//parent = (child-1)/2
	int parent = (child - 1) / 2;
	while (child > 0) //child为0时已经是根节点，不需要再向上调整
	{
		//if (a[child] > a[parent]) {//大堆，如果父节点比子节点小，调整。每个父节点>=子节点
		if (a[child] < a[parent]) { //小堆，如果父节点比子节点大，调整。每个父节点<=子节点
			Swap(&a[child], &a[parent]);
 
			child = parent;
			parent = (child - 1) / 2;
		}
		else //不需调整则跳出循环，否则会造成死循环
			break;
	}
}
void HeapPush(HP* php, HPDataType x)//堆的插入
{
	assert(php);
 
	if (php->size == php->capacity) { //检查空间
		int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;//确定新的容量
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity);//开辟空间
		if (tmp == NULL) {
			perror("realloc HPDataType* tmp fail");
			return;
		}
		php->a = tmp;//数组元素的指针a指向该空间
		php->capacity = newCapacity;//更改容量
	}
	php->a[php->size++] = x;//插入数据，且size++
 
	AdjustUp(php->a, php->size - 1);
}
 
 
void AdjustDown(HPDataType* a, int n, int parent)//堆的向下调整
{
	//父亲下标找孩子
	//leftchild = parent*2 + 1
	//rightchild = parent*2 + 2
 
	//如果是小堆，就找2个子节点中较小那个，因为父节点比小的子节点还小，说明父节点比2个子节点都小。
	//如果是大堆，就找2个子节点中较大那个，因为父节点比大的子节点还大，说明父节点比2个子节点都大。
 
	//这里将堆排序为小堆
	//不用创建左右子节点，再用父节点跟2个子节点比较这种方法。因为代码逻辑是相同的。
	//即如果父节点比左子结点小，调整；如果如果父节点比右子结点小，调整。这样就出现重复代码。
	//所以使用假设法，假设左子结点小，如果不是，换为右子节点
 
	//1.先初始化当前父节点的左子节点
	//2.以大堆为例，在比较父子节点之前选出左右子节点较大那个，
	//3.如果较大子节点比父节点大，那么交换并更新父节点，再找到其子节点
	//4.如果较大子节点比父节点小，说明已经是大堆，直接跳出循环。
	//重复2、3、4步骤直至子节点不存在
 
	int child = parent * 2 + 1;//假设左子结点小
	while (child < n) //子节点下标要在数组内才继续
	{
		//child为左子结点，child+1为右子节点
		//选出左右子节点小的那个（前提是右子节点存在）。如果右子节点小，孩子下标++
		//if (child + 1 < n && a[child + 1] > a[child]) //大堆
		if (child + 1 < n && a[child + 1] < a[child]) //小堆
			child++;
 
		//if (a[child] > a[parent]) { //大堆，如果父节点比子节点小，调整。每个父节点>=子节点
		if (a[child] < a[parent]) { //小堆，如果父节点比子节点大，调整。每个父节点<=子节点
			Swap(&a[child], &a[parent]);//交换父子节点
			parent = child;//父节点下标指向子节点，以该节点作为新的父节点。
			child = parent * 2 + 1;//新的子节点
		}
		else
			break;
	}
}
//删除堆顶的数据
void HeapPop(HP* php)//堆的删除
{
	assert(php);
	assert(!HeapEmpty(php));
 
	Swap(&php->a[0], &php->a[php->size - 1]);//交换数组的首尾元素
	php->size--;//删除尾元素（此时的尾元素就是原首元素）
 
	AdjustDown(php->a, php->size, 0);//重新向下调整堆（要保证左子树和右子树是堆）
}
 
 
HPDataType HeapTop(HP* php)//取堆顶的数据
{
	assert(php);
	assert(!HeapEmpty(php));
 
	return php->a[0];
}
 
 
int HeapSize(HP* php)//堆的数据个数
{
	assert(php);
	return php->size;
}
 
 
void HeapDestroy(HP* php)//堆的销毁
{
	assert(php);
	free(php->a);	
	php->a = NULL;
	php->size = php->capacity = 0;
}

Test.c

#define _CRT_SECURE_NO_WARNINGS
 
#include "Heap.h"
 
int main()
{
	HP hp;
	HeapInit(&hp);
 
	int a[] = { 65,100,70,32,50,60 };
	for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)//将数据插入堆
	{
		HeapPush(&hp, a[i]);
	}
 
 
	while (!HeapEmpty(&hp))
	{
		int top = HeapTop(&hp);
		printf("%d\n", top);
		HeapPop(&hp); //删除堆顶的数据
	}
 
	return 0;
}

3.4 堆的应用

3.4.1 堆排序

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

 1. 建堆

• 升序：建大堆
• 降序：建小堆 

2. 利用堆删除思想来进行排序

//可行但有2个弊端：
//1.先要建一个堆
//2.空间复杂度+拷贝数据
void HeapSort(int* a, int n)
{
	HP hp;
	HeapInit(&hp);
 
	//时间复杂度：N*logN
	for (int i = 0; i < n; i++)//将数据插入堆
		HeapPush(&hp, a[i]);
	
	//时间复杂度：N*logN 
	int i = 0;
	while (!HeapEmpty(&hp))
	{
		int top = HeapTop(&hp);
		a[i++] = top;
		HeapPop(&hp); //删除堆顶的数据
	}
	HeapDestroy(&hp);
}

void HeapSort(int* a, int n)
{
	//升序 建大堆
	//降序 建小堆
 
	//大堆的堆顶元素最大，小堆的堆顶元素最小。
	//降序如果用大堆来取堆中最大元素，那么可能导致剩余元素的大堆关系不存在，需要重新建堆。
	//所以建小堆，将首尾元素交换，取出最小元素（即堆顶元素也是尾元素）。
	//再调整剩余元素为小堆（此时除了首尾元素，其他部分依然为小堆关系），继续取当前堆中最小元素
	//将每次取出的最小元素从数组尾依次向前排列，最后就得到降序
 
	//建堆 - 向上调整。时间复杂度：F(N)=(N+1)*(log(N+1)-2)+2    O(N*logN)
    //这里是找前k个最大数，所以是降序，小堆。
    //一个数也可以看作是堆，所以从第二个数（下标为1）的开始
	for (int i = 1; i < n; i++)
		AdjustUp(a, i);
 
 
 
	//建堆 - 向下调整。（因为向下调整需要左右子树是堆，所以倒着向下调整）
    //时间复杂度：F(N)=N-log(N+1)    O(N)
    //从倒数第一个非叶子节点（最后节点的父节点）开始调整，直到根节点
    //叶节点（即终端节点，没有子节点的节点）不需要调整
    //孩子找父亲 parent = (child-1)/2。n是元素个数，n-1才是最后节点下标
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
		AdjustDown(a, n, i);
 
	//堆排序    时间复杂度：N*logN
	//1.初始化尾元素下标
	//2.交换首尾元素，即堆顶元素放到数组最后。
	//3.向下调整排序，不包含当前堆中的尾元素
	//4.更新尾元素下标，end--
	//5.end=0结束，一个元素视为有序（重复2~4步）。
	int end = n - 1;
	while (end > 0) //end不用等于0。只剩一个待排序数据时已经有序，不需要在调整。
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);//end是尾元素下标，其数值是n-1，恰好等于去掉最后元素的个数
		end--;
	}
}
 
int main()
{
	int a[] = { 7,8,3,5,1,9,5,4 };
	HeapSort(a, sizeof(a) / sizeof(a[0]));
 
	return 0;
}

//解决思路：
//1. 前K个数建小堆。时间复杂度：K
//2. 后面N-K个数，依次比较。如果比堆顶数据大，就替换堆顶数据进堆（覆盖堆顶值，向下调整）。
//时间复杂度：(N-K)*logK
//3. 最后这个小堆的值就是最大的前K个数
 
void CreateNDate()
{
	// 造数据
	int n = 10000;//生成1万个随机数
	srand((size_t)time(NULL));
	const char* file = "data.txt";//文件名
	FILE* fin = fopen(file, "w");
	if (fin == NULL) {
		perror("fopen FILE* fin error");
		return;
	}
 
	for (int i = 0; i < n; ++i) {
		int x = rand() % 1000000;//每个数在0~100万内
		fprintf(fin, "%d\n", x);//写入到文件中
	}
 
	fclose(fin);
}
 
void PrintTopK(int k)
{
	//1.用【读】的形式打开文件
	const char* file = "data.txt";
	FILE* fout = fopen(file, "r");
	if (fout == NULL) {
		perror("fopen FILE* fout error");
		return;
	}
 
	//2.读取数据前创建数组，因为数据要储存在数组中
	int* kminheap = (int*)malloc(sizeof(int) * k);
	if (kminheap == NULL) {
		perror("malloc int* kminheap fial");
		return;
	}
	//3.读取前k个数据到数组中
	for (int i = 0; i < k; i++)
		fscanf(fout, "%d", &kminheap[i]);
 
	//4.前k个数建小堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
		AdjustDown(kminheap, k, i);
 
	//5.剩余N-K个数跟堆顶数据比较，如果比它大则替换
	int val = 0;
	while (fscanf(fout, "%d", &val) == 1) {
		if (val > kminheap[0]) { //如果读取的数据比堆顶数据大
			kminheap[0] = val;//直接替换堆顶数据
			AdjustDown(kminheap, k, 0);//再从堆顶数据开始向下调整重新成堆
		}
	}
 
	//6.打印前k个数
	for (int i = 0; i < k; i++)
		printf("%d ", kminheap[i]);
}
 
int main()
{
	CreateNDate();
	PrintTopK(5);
	return 0;
}

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;
 
BTNode* BuyNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL) {
		perror("malloc BTNode* node fail");
		return NULL;
	}
	node->data = x;
	node->left = NULL;
	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);
	BTNode* node7 = BuyNode(7);
 
	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
	node2->right = node7;
	return node1;
}

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

4.2 二叉树的遍历 

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

学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(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)//前序遍历
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}

二叉树中序遍历

void InOrder(BTNode* root)//中序遍历
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

二叉树后序遍历

void PostOrder(BTNode* root)//后序遍历
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

4.2.2 层序遍历

层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

层序遍历需要用到队列，所以引用前面章节的队列代码

Queue.h

//这里注意不能重命名BTNode，因为BTNode是后方重命名的，这里找不到
typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNode //队列节点
{
	struct QueueNode* next;
	QDataType data;//相当于struct BinaryTreeNode* data
}QNode;
 
typedef struct Queue //储存队列节点头尾指针及节点个数的结构体
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;
 
void QueueInit(Queue* pq);//队列初始化
void QueueDestroy(Queue* pq);//队列释放
void QueuePush(Queue* pq, QDataType x);//队列插入
void QueuePop(Queue* pq);//队列删除
QDataType QueueFront(Queue* pq);//取队头数据
bool QueueEmpty(Queue* pq);//队列是否为空

Test.c

typedef int BTDataType;
typedef struct BinaryTreeNode {
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;
 
void LevelOrder(BTNode* root)//层序遍历
{
	//QDataType是struct BinaryTreeNode*的重命名
	//struct BinaryTreeNode*指向struct BinaryTreeNode结构体
	//struct BinaryTreeNode结构体被重名为BTNode
	//所以BTNode*相当于struct BinaryTreeNode* ， 相当于QDataType
 
	//思路：
	//使用队列（链表结构）。创建并初始化队列。
	//1.根节点不为空则入队列。
	//2.队列不为空取队头数据（即遍历），
	//3.然后视队头数据为根节点，将其不为空的左右子节点入队列。重复2、3步骤直到队列为空。
	Queue q;
	QueueInit(&q);
 
	if (root)
		QueuePush(&q, root);
 
	while (!QueueEmpty(&q)) {
		BTNode* front = QueueFront(&q);//用front指针记录队头数据
		QueuePop(&q);
 
		printf("%d ", front->data);
 
		if (front->left)
			QueuePush(&q, front->left);
 
		if (front->right)
			QueuePush(&q, front->right);
	}
	printf("\n");
	QueueDestroy(&q);
}

选择题

1. 某完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH 。该完全二叉树的前序序列为（ ）

A ABDHECFG
B ABCDEFGH
C HDBEAFCG
D HDEBFGCA

答案：A

2. 二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK;中序遍历：HFIEJKG.则二叉树根结点为（）

A E
B F
C G
D H

答案：A

3. 设一课二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树前序遍历序列为____。

A adbce
B decab
C debac
D abcde

答案：D

4. 某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出（同一层从左到右）的序列为

A FEDCBA 
B CBAFED
C DEFCBA
D ABCDEF

答案：A

4.3 节点个数以及高度等

二叉树节点个数

//不建议使用静态局部变量和全局变量
//静态局部变量：
//不方便获取(返回)；
//该静态局部变量一直保存数据，一直++，且无法置为0
//全局变量：每次调用该函数前要重置为0，否则数据一直保存一直++
int BTreeSize(BTNode* root)//求节点个数
{
	//1.如果当前节点是 NULL，返回 0。
	//2.如果当前节点不为空，则节点总数等于左子树的节点数加上右子树的节点数再加上当前节点。
	
    //版本一
    if (root == NULL)
		return 0;
	else
		return BTreeSize(root->left) + BTreeSize(root->right) + 1;
 
    //版本二
	return root == NULL ? 0 : BTreeSize(root->left) + BTreeSize(root->right) + 1;
}

二叉树叶子节点个数

int BTreeLeafSize(BTNode* root)//求叶节点个数
{
	//1.如果当前节点是 NULL，返回 0。
	//2.如果当前节点是叶节点（即左子节点和右子节点都为 NULL），返回 1。
	//3.否则，递归计算左子树和右子树的叶节点数，并将它们相加，返回总和。
 
	if (root == NULL)
		return 0;
 
	if (root->left == NULL && root->right == NULL)
		return 1;
 
	return BTreeLeafSize(root->left) + BTreeLeafSize(root->right);
}

求二叉树高度

int  BTreeHeight(BTNode* root)//求二叉树高度
{
	//1.如果当前节点是 NULL，返回 0。
	//2.如果当前节点不为空，分别计算其左子树和右子树的高度。
	//3.树的高度等于左子树高度和右子树高度中的较大者加 1（加 1 是因为要包括当前节点）。
	if (root == NULL)
		return 0;
 
	int leftHeight = BTreeHeight(root->left);
	int rightHeight = BTreeHeight(root->right);
	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

二叉树第k层节点个数

int BTreeLevelKSize(BTNode* root, int k)//二叉树第k层节点个数
{
	//如果 root 为空，返回 0。
	//如果 k 等于 1，返回 1。
	//每次递归调用时，参数 k 的值减少 1，这实际上是在向二叉树的下一层级深度前进。
    //当 k 减少到 1 时，表示已经到达了目标层级，即当前节点就是目标深度的节点。。
	assert(k > 0);
	if (root == NULL)
		return 0;
 
	if (k == 1)
		return 1;
	else
		return BTreeLevelKSize(root->left, k - 1)
		+ BTreeLevelKSize(root->right, k - 1);
}

二叉树查找值为x的节点

//空树和空节点返回空
//当前节点等于x时返回该节点
//否则，递归的查找左右子树。但需要记录左右子树节点，当找到时方便返回。
//左右子树都没找到，返回空。
BTNode* BinaryTreeFind(BTNode* root, BTDataType x) {
	//版本一
    if (root == NULL)//如果节点为空，返回空
		return NULL;
 
	if (root->data == x)//如果该节点值相等，返回该节点
		return root;
	
	BTNode* ret1 = BTreeFind(root->left, x);//记录左子节点
	if (ret1)//不为空
		return ret1;//返回左子节点
 
	BTNode* ret2 = BTreeFind(root->right, x);//记录右子节点
	if (ret2)//不为空
		return ret2;//返回右子节点
 
	return NULL;//左右子节点都为空，返回空
 
 
    //版本二
    if (root == NULL || root->data == x) //如果当前节点为空，或者data等于x，直接返回当前节点
		return root;
 
	BTNode* leftResult = BinaryTreeFind(root->left, x);//记录左子节点
	if (leftResult != NULL) //左子节点不为空，说明找到了
		return leftResult;
 
	return BinaryTreeFind(root->right, x);//左子树没找到，找右子树
}

4.4 二叉树基础oj练习

1. 检查两颗树是否相同

100. 相同的树 - 力扣（LeetCode）

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;
 
	//递归地检查 p 和 q 的左子树和右子树是否相同
	return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

2. 单值二叉树

965. 单值二叉树 - 力扣（LeetCode）

//思路：父节点和左右子节点的值不相等返回False
bool isUnivalTree(struct TreeNode* root) {
	if (root == NULL)//空树不违反规则，所以返回ture
		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);
}

3. 对称二叉树

对称二叉树

bool _isSymmetric(struct TreeNode* leftRoot, struct TreeNode* rightRoot) {
	if (leftRoot == NULL && rightRoot == NULL)//根节点左右子节点为空
		return true;
 
	if (leftRoot == NULL || rightRoot == NULL)//根节点左右子节点一个为空，另一个不为空
		return false;
 
	// 都不为空
	if (leftRoot->val != rightRoot->val)//左子节点值不等于右子节点
		return false;
 
	return _isSymmetric(leftRoot->left, rightRoot->right)
		&& _isSymmetric(leftRoot->right, rightRoot->left);
 
}
bool isSymmetric(struct TreeNode* root) {
	// 节点数目最少为1，所以没有空树
	return _isSymmetric(root->left, root->right);
} 

4. 二叉树的前序遍历

144. 二叉树的前序遍历 - 力扣（LeetCode）

// 将遍历的值存入数组，数组要malloc开辟
// int* returnSize是要返回的数组大小
// 1.首先确定要开辟数组的大小，所以创建新递归函数TreeSize遍历二叉树，求节点个数
// 2.因原函数开辟数组，所以不能再原函数中递归，否则每次否开辟数组。
// 3.创建新递归函数_preorder遍历二叉树，并将节点数值存入数组中
// 所以该函数需要二叉树根节点、数组首元素地址、数组大小
int TreeSize(struct TreeNode* root) {
	//版本一
	if (!root)
		return 0;
 
	return TreeSize(root->left) + TreeSize(root->right) + 1;
 
	//版本二
	return !root ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
 
//错误版本
void _preorder(struct TreeNode* root, int* a, int i) {
	if (!root)
		return;
 
	//此写法错误，每个栈帧（即每次递归）都有一个下标i，所以在递和归的过程中，i就混乱了。
	a[i++] = root->val;
	_preorder(root->left, a, i);
	_preorder(root->right, a, i);
}
 
//正确版本
void _preorder(struct TreeNode* root, int* a, int* pi) {
	if (!root)
		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(*returnSize * sizeof(int));
 
	int i = 0;
	// _preorder(root, a, i);//错误版本
	_preorder(root, a, &i);//正确版本
	return a;
}

5. 二叉树的中序遍历

94. 二叉树的中序遍历 - 力扣（LeetCode）

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

6. 二叉树的后序遍历

145. 二叉树的后序遍历 - 力扣（LeetCode）

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

7. 平衡二叉树

110. 平衡二叉树 - 力扣（LeetCode）

int BTreeHeight(struct TreeNode* root) // 求二叉树高度
{
    if (root == NULL)
        return 0;
 
    int leftHeight = BTreeHeight(root->left);
    int rightHeight = BTreeHeight(root->right);
    return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
 
//平衡二叉树的性质：对于树中的每个节点，它的两棵子树的高度差不超过1。
//对于每个节点，首先计算其左右子树的高度，然后判断它们的高度差是否超过1。
//如果任何节点不满足平衡条件，直接返回 false；否则，继续递归检查其左右子树。
bool isBalanced(struct TreeNode* root) {
    if (!root)
        return true;
 
    int leftHeight = BTreeHeight(root->left);
    int rightHeight = BTreeHeight(root->right);
 
    if (abs(leftHeight - rightHeight) > 1) {
        return false;
    }
 
    return isBalanced(root->left) && isBalanced(root->right);
}

8. 翻转二叉树

226. 翻转二叉树 - 力扣（LeetCode）

//如果当前节点为空，直接返回 NULL。
//否则，交换左右子树，然后分别递归调用 invertTree 函数。
//返回翻转后的根节点。
struct TreeNode* invertTree(struct TreeNode* root) {
    if (!root)
        return NULL;
 
    struct TreeNode* left = invertTree(root->left);
    struct TreeNode* right = invertTree(root->right);
 
    root->left = right;
    root->right = left;
 
    return root;
}

4.5 二叉树的创建和销毁

二叉树的构建及遍历

二叉树遍历_牛客题霸_牛客网 (nowcoder.com)

//思路：
//1.创建字符数组，100个元素。并用scanf逐个读取字符串中的字符
//2.将字符数组和下标传给CreatTree函数
//3.CreatTree函数中遍历数组，并用前序创建二叉树。如果字符是#，下标++。如果不是#，创建二叉树节点，下标++。最后返回根节点
//4.用中序遍历打印
 
#include <stdio.h>
#include <stdlib.h>
 
typedef char BTDataType;
typedef struct BinaryTreeNode {
    BTDataType data;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
} BTNode;
 
BTNode* BuyNode(BTDataType x) {
    BTNode* node = (BTNode*)malloc(sizeof(BTNode));
    if (node == NULL) {
        perror("malloc BTNode* node fail");
        return NULL;
    }
    node->data = x;
    node->left = NULL;
    node->right = NULL;
    return node;
}
 
BTNode* CreateTree(char* a, int* pi) {
    if (a[*pi] == '#') { //数组中的#代表二叉树空节点，所以下标继续向后移动
        (*pi)++;
        return NULL;
    }
 
    BTNode* root = BuyNode(a[*pi]); //数组中不为#的元素，用来创建节点
    (*pi)++;
    root->left = CreateTree(a, pi);
    root->right = CreateTree(a, pi);
 
    return root;
}
 
void InOrder(BTNode* root) { //中序遍历
    if (root == NULL)
        return;
    
    InOrder(root->left);
    printf("%c ", root->data);
    InOrder(root->right);
}
 
int main() {
    char a[100];
    scanf("%s", a);
    int i = 0;
    BTNode* root = CreateTree(a, &i);
    InOrder(root);
 
    return 0;
}

二叉树销毁

void BTreeDestory(BTNode* root)// 二叉树销毁
{
	//1.检查当前节点是否为NULL，如果是，直接返回。
	//2.递归销毁左子树和右子树。
	//3.最后销毁当前节点。
	if (root == NULL)
		return;
 
	BTreeDestory(root->left);
	BTreeDestory(root->right);
	free(root);
}

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

bool BTreeComplete(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;
}

作业

树和二叉树

1. 下列关于树的叙述正确的是（ ）

A.树中可以有环
B.树的度是指所有结点中度最小的结点的度
C.树的深度指的是结点数最多的那一层的深度
D.树的根结点是所有结点的祖先结点

答案：D
解析：
A: 树中的节点不能相交
B: 树的度为所有节点中度最大的节点的度
C: 树的深度为根节点到叶子节点的最大深度

2. 在用树表示的目录结构中，从根目录到任何数据文件，有（ ）通道

A.唯一一条
B.二条
C.三条
D.不一定

答案：A
解析：树的特点是不相交，所以不可能有多个路径同时到达一个点。

3. 下列关于二叉树的叙述错误的是（   ）

A.二叉树指的是深度为 2 的树
B.一个 n 个结点的二叉树将拥有 n-1 条边
C.一颗深度为 h 的满二叉树拥有 2^h-1 个结点（根结点深度为1）
D.二叉树有二叉链和三叉链两种表示方式

答案：A
解析：
A错误: 二叉树指最大孩子个数为2，即树的度为二的树。深度描述的为树的层数。
B正确: 对于任意的树都满足：边的条数比节点个数少1，因为每个节点都有双亲，但是根节点没有
C正确: 正确，二叉树性质
D正确: 二叉链一般指孩子表示法，三叉连指孩子双亲表示法，这两种方式是二叉树最常见的表示方式，虽然还有孩子兄弟表示法，该中表示方式本质也是二叉链

4. 一颗拥有1000个结点的树度为4，则它的最小深度是（ ）

A.5
B.6
C.7
D.8

答案：B
解析：如果这棵树每一层都是满的，则它的深度最小，假设它为一个四叉树，高度为h，则这个数的节点个数为(4^h - 1) / 3，当h = 5, 最大节点数为341， 当h = 6, 最大节点数为1365，所以最小深度应该为6。

5. 在一颗度为3的树中，度为3的结点有2个，度为2的结点有1个，度为1的结点有2个，则叶子结点有（ ）个

A.4
B.5
C.6
D.7

答案：C
解析：
设度为i的节点个数为ni, 该树总共有n个节点,则n=n0+n1+n2+n3. 
有n个节点的树的总边数为n-1条.
根据度的定义,总边数与度之间的关系为：n-1=0*n0+1*n1+2*n2+3*n3.
联立两个方程求解,可以得到n0 = n2 + 2n3 + 1,  n0=6

6. 一颗完全二叉树有1001个结点，其叶子结点的个数是（ ）

A.251
B.500
C.501
D.不能确定

答案：C
解析：
该题需要用到二叉树性质：在任意二叉树中，度为0的节点都比度为2的节点多1个，即 n0 = n2 + 1
另外，在完全二叉树中，如果节点总个数为奇数，则没有度为1的节点，如果节点总个数为偶数，只有一个度为1的节点
因此：n0 + n1 + n2 = 1001  节点总数为奇数，没有度为1的节点
n0 + 0 + n2 = 2*n0-1 = 1001  n0 = 501

7. 在一颗完全二叉树中，某一个结点没有其左孩子，则该结点一定（ ）

A.是根结点
B.是叶结点
C.是分支结点
D.在倒数第二层

答案：B
解析：完全二叉树中如果一个节点没有左孩子，则一定没有右孩子，必定为一个叶子节点，最后一层一定为叶子节点，但是倒数第二层也可能存在叶子节点。

8. 设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为（ ）个

A.11
B.12​
C.13
D.14

答案：C
解析：
设Ni表示度为i的节点个数，则节点总数 N = N0 + N1 + N2
节点个数于节点边的关系： N个节点的树有N-1个边
边与度的关系：N - 1 = N1 + 2 * N2
故：N0 + N1 + N2 - 1 = N1 + 2 * N2
因此，得：N0 = N2 + 1
回到原题，N0 = 3，N1 = 8，可得N2 = 2。
因此答案是 3 + 8 + 2 = 13。

9. 有n个元素的完全二叉树的深度是（   ）

A.nlogn
B.nlogn+1
C.logn
D.logn+1

答案：D
解析：参考课件完全二叉树的特性，高度h = log(n)向上取整  注意：底数是2，故选择D

10. 已知某二叉树的前序遍历序列为5 7 4 9 6 2 1，中序遍历序列为4 7 5 6 9 1 2，则其后序遍历序列为（ ）

A.4 2 5 7 6 9 1
B.4 2 7 5 6 9 1
C.4 7 6 1 2 9 5
D.4 7 2 9 5 6 1

答案：C

解析：
通过前序遍历找到子树的根，在中序遍历中找到根的位置，然后确定根左右子树的区间，即根的左侧为左子树中所有节点，根的右侧为右子树中所有节点。
故：根为： 5
5的左子树：4 7；5的右子树：6 9 1 2
5的左子树的根为：7；5的右子树的根为：9
7的左子树：4；7的右：空。9的左子树：6；9的右子树：2

11. 已知某二叉树的中序遍历序列为JGDHKBAELIMCF，后序遍历序列为JGKHDBLMIEFCA，则其前序遍历序列为（ ）

A.ABDGHJKCEFILM
B.ABDGJHKCEILMF
C.ABDHKGJCEILMF
D.ABDGJHKCEIMLF

答案：B
解析：
由后序遍历确定子树的根，后序遍历从后向前看，最后一个元素为根，和前序遍历刚好相反，从后向前看后序遍历，应该是根，右，左，根据中序遍历确定子树的左右区间
故：根为: A
A的左子树：JGDHKB       A的右子树：ELIMCF
A的左子树的根：B        A的右子树的根：C
B的左子树：JGDHK  B的右子树：空  C的左子树：ELIM C的右子树：F
B的左子树的根：D         C的左子树根：E
D的左子树的根：G D的右子树的根：H  E的右子树的根:I

12. 已知某二叉树的前序遍历序列为ABDEC，中序遍历序列为BDEAC，则该二叉树（ ）

A.是满二叉树
B.是完全二叉树，不是满二叉树
C.不是完全二叉树
D.是所有的结点都没有右子树的二叉树

答案：C
解析：前序确定根，中序找到根确定根的左右子树，最后还原二叉树为：
前： ABDEC        中：BDEAC
所以既不是满二叉树，也不是完全二叉树

13. 一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ）

A.所有的结点均无左孩子
B.所有的结点均无右孩子
C.只有一个叶子结点
D.至多只有一个结点

答案：C
解析：
前序遍历：根 左 右
后序遍历：左 右 根
从二叉树 前序 和 后序遍历结果规则中可以看出，如果树中每个节点只有一个孩子时，遍历结果肯定是反的

14. 设某种二叉树有如下特点：每个结点要么是叶子结点，要么有2棵子树。假如一棵这样的二叉树中有m（m>0）个叶子结点，那么该二叉树上的结点总数为（ ）

A.2m+1
B.2(m-1)
C.2m-1
D.2m

答案：C
解析：
根据二叉树的性质，在任意的二叉树中，度为0的节点比度为2的节点多了1个----见课件
现在叶子节点为m个，即度为0的节点有m个，那度为2的节点个数就为m-1个
而题目说该二叉树中只有度为2和度为0的节点 ，因此总的节点数就为：m+m-1 = 2m-1
故选择C

15. 设根结点的深度为1，则一个拥有n个结点的二叉树的深度一定在（   ）区间内

A.[log(n + 1)，n]
B.[logn，n]
C.[log(n + 1)，n - 1]
D.[log(n + 1)，n + 1]

答案：A
解析：
最大深度： 即每次只有一个节点，次数二叉树的高度为n，为最高的高度
最小深度： 此树为完全二叉树， 如果是完全二叉树
根据二叉树性质，完全二叉树的高低为 h = log(n+1)向上取整
 

16. 对任意一颗二叉树，设N0、N1、N2分别是度为0、1、2的结点数，则下列式子中一定正确的是（ ）

A.N0 = N2 + 1
B.N1 = N0 + 1
C.N2 = N0 + 1
D.N2 = N1 + 1

答案：A
解析：
节点总数N： N = N0 + N1 + N2
度和边的关系： N - 1 = 0 * N0 + 1 * N1 + 2 * N2
上面两个式子可以推出： N0 + N1 + N2 - 1 = N1 + 2 * N2
可得： N0 = N2 + 1

17. 二叉树的后序非递归遍历中，需要的额外空间包括（ ）

A.一个栈
B.一个队列
C.一个栈和一个记录标记的顺序表
D.一个队列和一个记录标记的顺序表

答案：C
解析：需要一个栈模拟递归的过程， 一个顺序表保存节点。

18. 二叉树的( )遍历相当于广度优先遍历，( )遍历相当于深度优先遍历

A.前序 中序
B.中序 前序
C.层序 后序
D.层序 前序

答案：D

解析：
广度优先需要把下一步所有可能的位置全部遍历完，才会进行更深层次的遍历，层序遍历就是一种广度优先遍历。
深度优先是先遍历完一条完整的路径（从根到叶子的完整路径），才会向上层折返，再去遍历下一个路径，前序遍历就是一种深度优先遍历。

19. 如果一颗二叉树的前序遍历的结果是ABCD，则满足条件的不同的二叉树有（ ）种

A.13
B.14
C.15
D.16

答案：B
解析：
首先这棵二叉树的高度一定在3~4层之间:
三层：
A(B(C,D),()), A((),B(C,D)), A(B(C,()),D), A(B((),C),D),
A(B,C(D,())), A(B,C((),D))
四层：
如果为四层，就是单边树，每一层只有一个节点，除过根节点，其他节点都有两种选择，在上层节点的左边还是右边，所以2*2*2共8种
总共为14种。

20.  2-3树是一种特殊的树，它满足两个条件：
(1) 每个内部结点有两个或三个子结点
(2) 所有的叶结点到根的距离相同
如果一颗2-3树有10个结点，那么它有(      )个叶结点。

A.7
B.8
C.7 或 8
D.6

答案：D
解析：
根据题目意思，每一个非叶子节点至少有两个孩子节点，并且叶子节点都在同一层，所以，假设树的高度为h， 则二三树种最小的节点个数为满二叉树的个数：2^h - 1, 最大个数： (3^h - 1) / 2。所以 2^h - 1 < 10 < (3^h - 1) / 2, h为3，结构是1(3(2,2,2))。所以叶节点个数为6

堆

1. 将一个顺序表利用向下调整的方式整理成堆的时间复杂度为（   ）

A.O(nlogn)
B.O(logn)
C.O(1)
D.O(n)

答案：D

解析：
题目说了是利用向下调整的方式建堆， 正确的证明方法应当如下：
A.具有n个元素的平衡二叉树，树高为㏒n，我们设这个变量为h。
B.最下层非叶节点的元素，只需做一次线性运算便可以确定大根，而这一层具有2^(h-1)个元素，我们假定O(1)=1，那么这一层元素所需时间为2^(h-1) × 1。
C.由于是bottom-top建立堆，因此在调整上层元素的时候，并不需要同下层所有元素做比较，只需要同其中之一分支作比较，而作比较次数则是树的高度减去当前节点的高度。因此，第x层元素的计算量为2^(x) × (h-x)。
D.又以上通项公式可得知，构造树高为h的二叉堆的精确时间复杂度为： 
S = 2^(h-1) × 1 + 2^(h-2) × 2 + …… +1 × (h-1) ①
E.通过观察第四步得出的公式可知，该求和公式为等差数列和等比数列的乘积，因此用错位相减法求解，给公式左右两侧同时乘以2，可知： 
2S = 2^h × 1 + 2^(h-1) × 2+ …… +2 × (h-1) ②
用②减去①可知： S =2^h × 1 - h +1 ③
将h = ㏒n 带入③，得出如下结论：
S = n - ㏒n +1 = O(n)

2. 在一个堆中，根节点从0开始编号，下标为 i（i > 0） 的结点的左右孩子结点及父结点的下标分别是（   ）

A.2 i、2 i + 1、i /2
B.2i、2i + 1、(i - 1)/2
C.2i + 1、2i + 2、(i - 1)/2
D.2i + 1、2i + 2、i/2-1

答案：C
解析：对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：
1. 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
2. 若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子
3. 若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子

3. 下列关于向下调整算法的说法正确的是（ ）

A.构建堆的时候要对每个结点都执行一次
B.删除操作时要执行一次
C.插入操作时要执行一次
D.以上说法都不正确

答案：B
解析：
A: 建堆时，从每一个非叶子节点开始，倒着一直到根节点，都要执行一次向下调整算法。
B: 删除元素时，首先交换堆顶元素与堆中最后一个元素，对中有效元素个数减1，即删除了堆中最后一个元素，最后将堆顶元素向下调整
C: 插入操作需要执行向上调整算法。

4. 下列关键字序列中，序列（ ）是堆。

A.{16，72，31，23，94，53}
B.{94，23，31，72，16，53}
C.{16，53，23，94，31，72}
D.{16，23，53，31，94，72}

答案：D

5. 下列关于堆的叙述错误的是（ ）

A.堆是一种完全二叉树
B.堆通常使用顺序表存储
C.小堆指的是左右孩子结点都比根结点小的堆
D.堆的删除是将尾部结点放到队顶后执行向下调整算法

答案：C
解析：
堆是在完全二叉树的基础上进行了条件的限制，即：每个节点都比其孩子节点大，则为大堆；每个节点都比其孩子节点小则为小堆
完全二叉树比较适合使用顺序结构存储。
堆删除：删的是堆顶元素，常见操作是将堆顶元素与堆中最后一个元素交换，然后对中元素个数减少一个，重新将堆顶元素往下调整
故C错误