数据结构：二叉树

目录

树

二叉树

堆

以大堆为例代码实现

 功能预览

初始化

销毁

打印

插入数据

删除数据 

建堆

获取栈顶元素

获取数组中的元素个数

判空

堆排序

TopK问题

二叉树链式结构的实现

功能预览

二叉树遍历

求节点的总个数

求叶子节点的个数

求树的深度

求第k层的节点个数

查找二叉树值为x的节点

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

销毁

---

前言

生活中的树您一定非常熟悉：树的主要四部分是树根、树干、树枝、树叶。

 而在数据结构中，把一种结构叫做树是因为它看起来像一棵倒过来的树，根朝上，而叶是朝下的。如图：

树

1、树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。

2、它有一个 特殊的结点，称为 根结点 ，根节点没有前驱结点， 一个树只有一个根节点。

3、除根节点外， 每棵子树的根结点有且只有一个前驱结点，可以有 0 个或多个后继结点。

4、子树间不能有交集，根据这个特性可以得出结论，一个有N个节点的树，有N-1条边。

例如：这样的结构就不是树结构

---

和生活中的树一样，树结构也有很多组成成分！以下图为例给大家介绍下树结构中的一些相关概念：

●节点的度：一个节点含有子树的个数（小张把子树理解成孩子，一个节点有几个孩子，度就是多少），叫做度。如上图：A的度是2。

●树的度：在整个树结构中，其中会有一个节点的度最大，这个度就是这个树的度。上图中节点B的度是整个树结构中最大的，这个树结构的度就是3。

●叶子节点：度为0的节点（没有孩子）。例如上图的：K,J,F,L.......

●分支节点：度不为0的节点（最少有一个孩子）。例如上图中的：B,C,D,E,G........

●子节点（孩子节点）：和父节点对应理解。除了根节点外，有且只有一个父节点。一个节点含有的子树的根节点称为该节点的子节点。如上图：B,C是A的子节点。

●父节点（双亲节点）：一个节点有子节点，这个节点就是其子节点的父节点。如上图：A是B、C的父节点。

●兄弟节点：用相同的父节点。例如上图中的B,C。

●堂兄弟节点：父节点在同一层的节点。例如上图中的F，G。

●节点的层次：从根开始定义起，根为第1层，以此类推！如下图所示：

●树的高度（深度）：树中节点的最大层次； 如上图：高度为5。

●节点的祖先：从根节点到这个节点的父节点所经路径上的所有节点。如上图：A是所有节点的祖先，节点D的祖先有B,A。

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

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

二叉树

什么是二叉树？林子大了什么“树”都有！在树结构中，有一种较为特殊的树----二叉树。

二叉树的概念：由一个根节点加上两棵别称为左子树和右子树的二叉树组成 。也就是说二叉树没有度大于2的节点，二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树。

二叉树中又有两种特殊情况：满二叉树和完全二叉树。 

满二叉树：如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。

思考：深度为H的满二叉树，总结节点N是多少？

结论：N = 2^H - 1；

完全二叉树：在满二叉树的基础上，最后一层没满，但是节点必须是连续的。

 节点总数最多：最后一层满了。

 节点总数最少：最后一层只有一个节点。

所以完全二叉树总节点的区间【2^(H-1),2^H-1】。

 二叉树的性质：

对于任何二叉树，若度为0的叶结点个数为N0 , 度为2的分支结点个数为 N2,则有N0＝N2 ＋1

对于满二叉树而言，如果一直二叉树的深度H，总结点数N = 2^H - 1;

如果已知满二叉树的节点总数N求这个二叉树的深度，H= long2^(N+1);

了解了完全二叉树，下面就要用它实现一个堆。

堆

什么是堆？堆总是一个完全二叉树，并且堆中某个节点的值总是不大于或不小于其父节点的值。通常情况下把堆用顺序结构的数组来存储。

大堆：（根最大）父亲大于等于孩子 。

小堆：（根最小）父亲小于等于孩子。

孩子节点和父节点之间的“血缘”关系：

左孩子（左子节点）：在数组中存储的下标是奇数。并且LeftChild = Parent*2+1;

右孩子（右子节点）：在数组中存储的下标是偶数。并且RightChild = Parent*2 + 2;

父结点：Parent = (child - 1)/2 ,这个孩子可以是左孩子也可以是有孩子，因为Parent只保留计算结果的整数部分。

以大堆为例代码实现

 功能预览

//初始化
void HeapInit(Hp* php);
//销毁
void HeapDestory(Hp* php);
//打印
void HeapPrint(Hp* php);
//堆的插入
void HeapPush(Hp* php, HpDataType data);
//堆的删除
void HeapPop(Hp* php);
//获取堆顶的元素
HpDataType HeapTop(Hp* php);
//获取数组中元素个数
int HeapSize(Hp* php);
//堆的判空
bool HeapEmpty(Hp* php);
//堆的创建
void HeapCreate(Hp* php,HpDataType* arr,int num);
//向下调整
void AdJustDown(HpDataType* Arr, int sz, int parent);
//堆排序,升序
void HeapSortB(HpDataType* Arr, int num);
//topk
void HeapTopK(HpDataType* Arr, int k, int sz);

堆是用数组来实现的，它的成员和顺序表的成员相同。

typedef int HpDataType;
typedef struct HeapNode
{
	HpDataType* Arr;
	int size;
	int capacity;
}Hp;

初始化、销毁、打印这几个接口在这里就不做过多的介绍了。

初始化

//初始化
void HeapInit(Hp* php)
{
	php->Arr = NULL;
	php->size = 0;
	php->capacity = 0;
}

销毁

void HeapDestroy(Hp* php)
{
	assert(php);
	free(php->Arr);
	php->Arr = NULL;
	php->capacity = 0;
	php->size = 0;
}

打印

void HeapPrint(Hp* php)
{
	for (int i = 0; i < php->size; i++)
	{
		printf("%d ",php->Arr[i]);
	}
	printf("\n");
}

插入数据

堆插入数据的步骤和顺序表相同，数据在数组的尾部插入，需要注意的是，在数据添加后可能破坏堆结构，这就需要做特殊处理，“向上调整”。

向上调整：

大堆的特点是父亲节点总大于等于孩子节点。鉴于这种特性，把插入进来的数据，也就是孩子节点和父节点比较，如果孩子节点更大，那么做两件事情，交换父节点和孩子节点的值，还有就是更新parent和child（下标）。

可以这样理解：你的一个海归儿子学成归来，你们家族是靠实力说话的，在从根节点到你海归儿子这条路径上，只要你儿子的实力比他们强，就可以顶替他们的位置。

代码实现：

数据交换在后面接口的实现中也要用到，为了方便将其封装成一个函数。这里注意要传址调用。

//交换
void Swap(HpDataType* e1, HpDataType* e2)
{
	HpDataType tmp = *e1;
	*e1 = *e2;
	*e2 = tmp;
}

向上调整：判断条件是当child==0的时候结束。你可以这样想，你的海归儿子通过自己的努力已经成为了家族的掌门人（树的根节点），这个时候他也就没有继续上升的空间了。

void AdJustUp(HpDataType* Arr, int child)
{
	//父节点的位置
	int Parent = (child-1)/2;
	while (child > 0)
	{
		//孩子节点的值大于父节点，向上调整
		if (Arr[child] > Arr[Parent])
		{
			//交换孩子节点和父节点的值
			Swap(&Arr[child] ,&Arr[Parent]);
			//更新孩子节点和父节点的值
			child = Parent;
			Parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
 
	}
}

插入数据

void HeapPush(Hp* php, HpDataType data)
{
	//扩容
	if (php->size == php->capacity)
	{
		int newcacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HpDataType* ret = (HpDataType*)realloc(php->Arr,sizeof(HpDataType)*newcacity);
		if (ret == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		php->Arr = ret;
		php->capacity = newcacity;
	}
	php->Arr[php->size] = data;
	php->size++;
	//插入后可能是堆结构，也可能不是,就需要调整一下
	AdJustUp(php->Arr,php->size-1);
}

删除数据 

思路分析：删掉堆顶的数据，如果直接将元素向前覆盖的话会改变整体的堆结构，本来两个元素是兄弟关系，改变结构以后突然间你的兄弟就变成了你的爸爸，这就不太合适了。所以在删除之前先交换下堆顶和堆底的数据，接着删掉数组末尾（堆底）的数据即可。堆的结构保住了，但是还有一个问题需要解决，就是堆顶的数据不一定是最大的（大堆而言）。

还是打个比方，这次是你有权有势，在你退休的时候动用你的人脉关系将你儿子安排到了一个万人之上的位置。虽然你的儿子现在位高权重，但是机会是留给有准备的人的，下面比你儿子优秀的人就会取代他。这个过程称为“向下调整”。

根节点的数据和它左右孩子中较大的内一个进行比较，如果小于这个孩子节点，就与其进行交换。反之你就留在这个位置上。

代码实现：

void HeapPop(Hp* php)
{
	assert(php);
	assert(php->size > 0);
	Swap(&(php->Arr[0]), &(php->Arr[php->size - 1]));
	php->size--;
	//交换删除完成后，数组中的结构不一定满足堆结构
	//向下调整
	AdJustDown(php->Arr,0,php->size);
}

向下调整：结束条件是child

void AdJustDown(HpDataType* arr, int parent,int sz)
{
	int chlid = parent * 2 + 1;
	while(chlid < sz)
	{
		//确定大孩子
		if (chlid+1<sz && arr[chlid] < arr[chlid + 1])
		{
			chlid = parent * 2 + 2;
		}
		if (arr[chlid] > arr[parent])
		{
			//交换
			Swap(&arr[chlid] , &arr[parent]);
			//迭代
			parent = chlid;
			chlid = parent * 2 + 1;
		}
		else
		{
			break;
		}
 
	}
 
}

小总结：插入和删除数据操作，重要领会向上和向下调整的过程，目的都是为了维护堆结构。写完了大堆，如果要实现小堆非常的简单，，父节点一因为小堆的特性和大堆相反定小于等于孩子节点，堆顶的元素最小。在大堆代码的背景下实现小堆，在孩子和父亲节点的判断上，更改一些判断条件即可，整体的逻辑是一样的。

建堆

有了上面内容的铺垫，为了测试或者完成更多的需求（例如使用堆排序处理一组数据，首先要确保这组数据是堆结构），可以写一个建堆函数，把一些随便的数据放入数组中，通过建堆函数就可以把这个数组调整成一个堆结构。下面采用的是向下调整的方法建堆。

建堆算法的思路：从倒数第一个非叶子节点的子树开始调整，一直调整到根节点。也就是从下到标注的上按照顺序依次向下调整子树。如图序号就是调整的顺序：

 代码实现：

前半部分的代码处理很简单，将要排序的数据拷贝到目标数组中。主要理解建堆算法，从最小孩子的父节点开始向下调整，每调整完一个子树，父节点的位置 - 1，直至根节点。

void HeapCreate(Hp* php, HpDataType* Arr, int sz)
{
	HpDataType* tmp = (HpDataType*)malloc(sizeof(HpDataType)*sz);
	if (tmp == NULL)
	{
		perror("malloc fail:");
		exit(-1);
	}
	php->Arr = Arr;
	php->size = sz;
	php->capacity = sz;
	memcpy(php->Arr,Arr,sz);
 
	//建队算法
	//从倒数第二层开始计算
	for (int i = (sz - 1 - 1) / 2; i >= 0; i--)
	{
		AdJustDown(php->Arr,i,sz);
	}
}

建小堆的时候只需要改变下向下调整的判断条件！！！

这几个接口的功能和代码很好理解：

获取栈顶元素

//获取堆顶的元素
HpDataType HeapTop(Hp* php)
{
	assert(php);
	assert(php->sz>0);
	return php->Arr[0];
}

获取数组中的元素个数

//获取数组中的元素个数
int HeapSize(Hp* php)
{
	assert(php);
	return php->size;
}

判空

//判空
bool HeapEmpty(Hp* php)
{
	assert(php);
	return php->size == 0;
}

看到这里你一定烦死了，这个堆这么麻烦到底能给我们带来什么便利呢？下面就是堆的应用，堆排序和用堆解决TopK问题。 

堆排序

排序在处理一些问题时出现的频率是非常高的，当我们想要使用堆来排序处理一组数据的时候第一步就是创建一个堆，升序建大堆，降序建小堆。建堆算法上面已经介绍过了，这里直接调用。

升序：

思路：大堆的堆顶数据是最大的，将堆顶和堆底的数据交换。向下调整保住堆结构，end--。下次交换找到次大的数据排在第一大的数据后面。

//升序
void HeapRise(Hp*php, int* Arr, int sz) 
{
	//创建一个大堆
	HeapCreate(php,Arr,sz);
 
	//大堆堆排序，堆顶的元素是大的
	int end = sz - 1;
	while(end)
	{
		//交换首尾元素
		Swap(&php->Arr[0],&php->Arr[end]);
		//向下调整
		AdJustDown(php->Arr,0,end);
		end--;
	}
}

降序：

降序建小堆，和上面代码的逻辑类似。注意的是向下调整部分是小堆的判断方法。

---

TopK问题

求一组数据中前K个最大的元素或者最小的元素。

看到这种问题你肯定会想，我不用堆也可解决，嘻嘻，先看代码，堆的好处后面在谈：

获取前k个元素

思路：将一组数据中的前k个数建立一个小堆，遍历剩下的数据一次和堆顶比较，如果比堆顶的数据大，替换它进堆，向下调整。

可以这样理解，在一个公司中每个员工都各司其职，能力也有强有弱。当公司招聘到一个优秀的人才，但公司又没有多余的位置时，就只能和已经在职员工最差的员工比较，确定它有没有进入公司的资格。如果新来的能给公司带来更多的价值，那么将取代老员工的位置，老员工下岗。你以为这就完了吗？当然没有，还要根据这个人的能力给他一个匹配的职位，接下来还要继续和其他员工比较（向下调整）。

代码实现：

void HeapTopK(Hp* php, HpDataType* Arr, int sz,int k)
{
	//建立k个数的小堆
	HeapCreate(php,Arr,k);
 
	//遍历数组
	for (int i = k; i < sz; i++)
	{
		//比堆顶数据大
		if (Arr[i] > php->Arr[0])
		{
			php->Arr[0] = Arr[i];
			//向下调整
			AdJustDown(php->Arr,0,k);
		}
	}
	
}

获取后k个元素

将一组数据中的前k个数建立一个大堆，遍历剩下的数据一次和堆顶比较，如果比堆顶的数据小，替换它进堆，向下调整。

在打个比方，在你们班级内部举办了一个苗条大赛，你是记录数据的统计员。名额只取重量最轻的k个。前k个同学的体重你记在了小本本上，当第六个人的数据给到你时，你就要进行判断，这个人的体重如果比已有数据最大的内个还大，那么它就失去了获奖的资格。反之，替换掉最大的内个数据，在和已有k个数据比较，排到一个合适他的位置（向下调整）。

代码实现：
 

//后topk
void HeapTopK(Hp* php, HpDataType* Arr, int sz,int k)
{
	//建立k个数的大堆
	HeapCreate(php,Arr,k);
 
	//遍历数组
	for (int i = k; i < sz; i++)
	{
		//比堆顶数据小
		if (Arr[i] < php->Arr[0])
		{
			php->Arr[0] = Arr[i];
			//向下调整
			AdJustDown(php->Arr,0,k);
		}
	}
	
}

看过代码后来谈谈为什么要使用这种算法来解决TopK的问题：因为在某种场景下，我们要处理的数据量可能会很大，比如取全球首富排行榜的前k个，取全国高考排名的后k个。数据量太大的时候我们无法动态开辟这么大的空间来解决问题，只能将数据存储在磁盘的文件里。基于这样的场景使用堆，只需要开辟k个空间，将文件中的数依次读取就解决了这个问题。

二叉树链式结构的实现

实现一个结构，首先要知道重点研究那些问题。

功能预览

//申请一个节点
Tree* BuyNode(TreeDataType data);
//构建一个链表
Tree* List();
//前中后序遍历
void PrevOrder(Tree* root);
void InOrder(Tree* root);
void PostOrder(Tree* root);
//求二叉树节点个数
int TreeSize(Tree* root);
//二叉树叶子节点个数
int TreeLeafSize(Tree* root);
//求树的深度
int TreeHight(Tree* root);
//求第k层的节点数
int TreeK(Tree* root, int k);
//查找
Tree* TreeNodeFind(Tree* root, TreeDataType data);
//层序遍历
void Levelorder(Tree* root);
//构建二叉树
Tree* TreeCrear(char* str, int* i);
//判断一个树是不是一个完全二叉树
bool TreeComplete(Tree* root);
//二叉树的销毁
void TreeDestory(Tree* root);

二叉树的概念在上面谈到过，由根节点，根节点的左子树、右子树组成。

typedef int TreeDataType;
typedef struct TreeNode
{
	TreeDataType val;
	struct TreeNode* left;
	struct TreeNode* right;
}Tree;

申请节点

Tree* BuyNode(TreeDataType data)
{
	Tree* newnode = (Tree*)malloc(sizeof(Tree));
	if (newnode == NULL)
	{
		perror("malloc :");
		exit(-1);
	}
	newnode->left = NULL;
	newnode->right = NULL;
	newnode->val = data;
	return newnode;
}

准备工作做好以后，第一项工作就是创建一个二叉树，这里可以手动创建一个二叉树，直接暴力链接。逻辑结构如下图:

//构建一个链表
Tree* List()
{
	Tree* newnode1 = BuyNode(1);
	Tree* newnode2 = BuyNode(2);
	Tree* newnode3 = BuyNode(3);
	Tree* newnode4 = BuyNode(4);
	Tree* newnode5 = BuyNode(5);
	Tree* newnode6 = BuyNode(6);
 
	newnode1->left = newnode2;
	newnode1->right = newnode4;
	newnode2->left = newnode3;
	newnode4->left = newnode5;
	newnode4->right = newnode6;
	return newnode1;
}

创建好一棵二叉树后，可以对它进行一些操作。我们在使用数组的时候经常会对其进行遍历，二叉树的遍历 是按照某种特定的规则，依次对二叉 树中的节点进行相应的操作，并且每个节点只操作一次 。 遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

二叉树遍历

前序遍历：根节点，左子树，右子树

以前序遍历为例进行画图分析：

//先序遍历
void PrevOrder(Tree* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
 
	printf("%d ",root->val);
	PrevOrder(root->left);
	PrevOrder(root->right);
}

中序遍历：左子树，根节点，右子树

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

后序遍历：左子树，右子树，根节点

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

中序和后序遍历的递归展开图和前序是一样的，区别是打印的时机不同。画图理解的时候注意要时刻观察树的逻辑结构图。

层序遍历：层序遍历是一层一层的去找数据。这里用到了队列的知识，根节点入队，访问打印，出队，将他的左右节点入队，

下面提供了队列的部分接口。当然你如果为了方便也可以直接使用数组模拟队列入队出队的过程！！

这里要说明一下，入队入的是二叉树的节点。以前我们写队列的时候可能存的数据是int 或者是char类型的，只不过这次换了数据类型，一定要清醒哦。

typedef Tree* QuDataType;
 
typedef struct QueueNode
{
	QuDataType val;
	struct QueueNode* next;
}QNode;
 
typedef struct Qu
{
	QNode* Head;
	QNode* Tail;
	int sz;
}Qu;

//初始化
void QueuInit(Qu* qu)
{
	assert(qu);
 
	qu->Head = NULL;
	qu->Tail = NULL;
	qu->sz = 0;
}
//销毁
void QueueDestroy(Qu* qu)
{
	assert(qu);
	QNode* cur = qu->Head;
	while (cur)
	{
		QNode* Next = cur->next;
		free(cur);
		cur = Next;
	}
	qu->sz = 0;
	qu->Head = qu->Tail = NULL;
}
//插入数据
void QueuePush(Qu* qu, QuDataType data)
{
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc:");
		exit(-1);
	}
	newnode->val = data;
	newnode->next = NULL;
	if (qu->Head == NULL)
	{
		qu->Head = qu->Tail = newnode;
	}
	else
	{
		qu->Tail->next = newnode;
		qu->Tail = newnode;
		qu->sz++;
	}
}
//删除数据
void QueuePop(Qu* qu)
{
	assert(qu);
	assert(!QueueEmpty(qu));
	if (qu->Head->next == NULL)
	{
		free(qu->Head);
		qu->Head = qu->Tail = NULL;
	}
	else
	{
		//头删
		QNode* del = qu->Head;
		qu->Head = qu->Head->next;
		free(del);
	}
	qu->sz--;
}
 
 
QuDataType QueueFront(Qu* qu)
{
	assert(qu);
	return qu->Head->val;
}
 
bool QueueEmpty(Qu* qu)
{
	assert(qu);
	return qu->Head == NULL && qu->Tail == NULL;
}

层序遍历：

//层序遍历
void Levelorder(Tree* root)
{
	Qu q1;
	QueuInit(&q1);
	if ((&q1) ->Head == NULL)
	{
		QueuePush(&q1,root);
	}
	while (!QueueEmpty(&q1))
	{
		Tree* Node = QueueFront(&q1);
		printf("%d ",Node->val);
		
		QueuePop(&q1);
		if (Node->left)
		{
			QueuePush((&q1), Node->left);
		}
		if (Node->right)
		{
			QueuePush((&q1), Node->right);
		}
	}
	printf("\n");
}

测试结果：

求节点的总个数

分析：二叉树的节点总数，等于左子树的节点个数+右子树的节点个数+根节点。

int TreeSize(Tree* root)
{
	return root == NULL ? 0 : 
	(TreeSize(root->left) + TreeSize(root->right)+1);
}

求叶子节点的个数

叶子节点的度为0,这个时候节点的左右子树都是NULL

int TreeLeafSize(Tree* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

求树的深度

树的深度等于左右子树较大的+1（根节点的高度），需要注意的是计算左右子树高度的时候最好定义个变量记录他们一下，用表达式直接判断的话增加了递归的次数。

//左边子树和右子树比较，较大的深度+1
int TreeHight(Tree* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int HLeft = TreeHight(root->left);
	int HRight = TreeHight(root->right);
 
	return HLeft > HRight ? HLeft + 1
		: HRight + 1;
}

求第k层的节点个数

假设我在排队打饭排在最后，打饭的阿姨就好比在第k层，我和阿姨间的距离是k,而排在我前面的漂亮小姐姐和阿姨间的距离就是k-1,以此类推.........

确定了层数还不行，还要确定下这层到底有多少个节点（阿姨），叶子节点的总数等于这层左右子树节点的个数相加。

//求第k层的节点数
//root的第k层  是左子树的k-1层+右子树的k-1层
 
int TreeK(Tree* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return TreeK(root->left, k - 1) +
		TreeK(root->right, k - 1);
}

查找二叉树值为x的节点

这个接口有一点点的特别，它是有返回值的，在递归找到你要找的节点时，返回是返回给上一层递归，而不是找到了直接返回到外面。

思路分析：

首先处理下root为NULL的情况，其次是找到数据的时候，将这个节点返回。下面是比较核心的步骤，除了继续在左右子树去寻找这个目标节点外还要接收一下返回的节点。如果这个节点不是NULL，说明这就是目标节点了，层层返回。

//查找节点
Tree* TreeNodeFind(Tree* root, TreeDataType data)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->val == data)
	{
		return root;
	}
	Tree* ret1 = TreeNodeFind(root->left,data);
	if (ret1 != NULL)
	{
		return ret1;
	}
	Tree* ret2 = TreeNodeFind(root->right,data);
	if (ret2 != NULL)
	{
		return ret2;
	}
	return NULL;
}

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

思路：完全二叉树的定义是前H-1层是满的，最后一层没满，但是节点是连续的。运用层序遍历的过程，入队时将NULL也当做节点入队。出队的时候出到第一个NULL后判断后面的是否全为NULL,如果有不为NULL的节点，说明不是完全二叉树。

//判断是不是完全二叉树
bool TreeComplete(Tree* root)
{
	assert(root);
	//
	Qu q1;
	QueuInit(&q1);
	if ((&q1)->Head == NULL)
	{
		QueuePush(&q1, root);
	}
	while (!QueueEmpty(&q1))
	{
		Tree* Node = QueueFront(&q1);
		QueuePop(&q1);
 
		if (Node == NULL)
		{
			break;
		}
		else
		{
			//左右节点入队，包括NULL
			QueuePush((&q1), Node->left);
			QueuePush((&q1), Node->right);
		}
	}
	while (!QueueEmpty(&q1))
	{
		Tree* Node = QueueFront(&q1);
		QueuePop(&q1);
 
		if (Node != NULL)
		{
			QueueDestroy(&q1);
 
			return false;
		}
	}
	QueueDestroy(&q1);
	return true;
}

销毁

void TreeDestory(Tree* root)
{
	if (root == NULL)
	{
		return;
	}
	TreeDestory(root->left);
	TreeDestory(root->right);
	free(root);
}