二叉树的基础应用_二叉树应用到实际问题

二叉树

1. 树概念及结构

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）棵互不相交的树的集合称为森林；

注：子树是不相交的，除根结外，每个结点有且仅有一个父节点，一棵N个结点的树有N-1条边。

1. 3树的表示

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间 的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法 等。我们这里就简单的了解其中最常用的孩子兄弟表示法（左孩子右兄弟）

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

1.4树在实际中的应用

文件系统就是树在实际生活中的应用

2.二叉树概念及结构

2.1概念

一棵二叉树是结点的一个有限集合，该集合:

1. 或者为空

2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成

1. 二叉树不存在度大于2的结点

2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

3 特殊的二叉树：

1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是 说，如果一个二叉树的层数为K，且结点总数是 ，则它就是满二叉树。

2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K 的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对 应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树

堆排序—时间复杂度O（N*logN）

Topk---类似点外卖，想吃最好吃的饭，需要在n个里面排序排除最好的。

 

满二叉树就是一个等比数列，从2^0+………+2^(n-1);

等于2^n-1;,

完全二叉树度为1的至多只有1个，高度为h的二叉树，节点范围是2^h-1,(满二叉树可以认为是一个特殊的完全二叉树),高度为h的完全二叉树，节点范围是[2^(h-1),2^h-1]

前h-1的节点个数（前h-1）是满二叉树，计算得2^(h-1)-1,下一层至少有一个节点，所以最小值是2^(h-1)-1+1=2^(h-1);

4 二叉树的性质

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个结点.

2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h-1 .

3. 对任何一棵二叉树, 如果度为0其叶结点个数为 , 度为2的分支结点个数为 ,则有n0 ＝ n2＋1

4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=log2(n+1) . (ps:log2(n+1) 是log以2 为底，n+1为对数)

5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：

1. 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点

2. 若2i+1=n否则无左孩子

3. 若2i+2=n否则无右孩子

5.二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

1. 顺序存储

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空 间的浪费。而现实中使用中只有堆才会使用数组来存储，关于堆我们后面的章节会专门讲解。二叉树顺 序存储在物理上是一个数组，在逻辑上是一颗二叉树。

下标计算父子间的关系：leftchilid=parent*2+1；rightchild=parent*2+2；

Parent=（chilid-1）/2，右孩子是偶数，左孩子是奇数，右孩子减2左孩子减1.对于偶数说-1除2跟-2除2来说得到的结果是相同的,可以看出右孩子-1/2也可以得到，所以把他们的计算形式给统一了一下。

以上的仅时候满二叉树和完全二叉树。非完全二叉树不是不可以拿数组存而是不合适。

2 堆的概念及结构

如果有一个关键码的集合K = { k0，k1 ，k2 ，…，kn-1 }，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足：ki<=k2*i+1  且 ki<=k2*i+2 (ki >=k2*i+1 且 ki>=k2*i+2 ) i = 0，1， 2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆的性质： 堆中某个节点的值总是不大于或不小于其父节点的值；

堆总是一棵完全二叉树。

 

 堆算法的实现

Heap.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int HeapDataType;
typedef struct Heap
{
	HeapDataType* array;
	int size;
	int capicity;
}Heap;
void HeapInit(Heap* p);//初始化
void HeapDestory(Heap* p);//销毁堆
void HeapPush(Heap* p,HeapDataType x);//插入
void HeapPop(Heap* p);//删除
HeapDataType HeapTop(Heap* p);//取堆顶
bool HeapEmpty(Heap* p);//堆是否为空
int HeapSize(Heap* p);//堆的大小
void HeapPrint(Heap* p);//打印堆
 
void AdjustUp(HeapDataType* a, int child);//向上调整
void AdjustDown(HeapDataType* a, int size, int parent);//向下调整
 
void HeapSort(HeapDataType* a, int n);//堆排序
 

Heap.c
#define _CRT_SECURE_NO_WARNINGS  1
#include"Heap.h"
//大堆小堆能做到的是大堆堆顶是最大的，小堆堆顶是最小的，可以用来选数
 
void HeapInit(Heap* p)
{
	assert(p);
	p->array = NULL;
	p->capicity = p->size = 0;
}
void HeapDestory(Heap* p)
{
	assert(p);
	free(p->array);
	p->array = NULL;
	p->capicity = p->size = 0;
}
void Swap(HeapDataType* p1, HeapDataType* p2)
{
	HeapDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void AdjustUp(HeapDataType* a, int child)//从孩子的位置向上调整(父亲小于等于孩子)
{
	int parent = (child - 1 )/ 2;
	while (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(Heap* p, HeapDataType x)
{
	assert(p);
	if(p->capicity==p->size)
	{
		int newcapicity = p->capicity == 0 ? 4 : 2 * p->capicity;
		HeapDataType* tmp = (HeapDataType*)realloc(p->array, newcapicity*sizeof(HeapDataType));
		if (tmp == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		p->array = tmp;
		p->capicity = newcapicity;
	}
	p->array[p->size] = x;
	p->size++;
	AdjustUp(p->array, p->size - 1);
}
void HeapPrint(Heap* p)
{
	for (int i = 0; i < p->size; i++)
	{
		printf("%d ", p->array[i]);
	}
	printf("\n");
}
void AdjustDown(HeapDataType*a, int size, int parent)//小堆排序都用的小于号，到时需要大堆排序只需要改成大于号
{
	//至少满足左子树是小堆，右子树是小堆才能向下调整
	//选出左右孩子小的一个
	//小的跟父亲比较，如果比父亲要小则交换，继续向下调整
	//如果比父亲大则调整结束
	//最多调整到叶子节点就结束了
	int child = parent * 2 + 1;
	while (child<size)//默认循环开始child都是左孩子
	{
		//选出左右孩子小的内一个
		//if (child+1<size&&a[child + 1] < a[child])//左孩子存在右孩子不一定存在（小根堆条件）
		if (child + 1 < size && a[child + 1] > a[child])//（大根堆条件）
		{
			++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(Heap* p)//最优的是将首尾调换，将尾删去，删除其他位置的数是没有价值的（只删除堆顶的值）
{
	assert(p);
	assert(p->size > 0);
	Swap(&(p->array[0]), &(p->array[p->size - 1]));
	p->size--;
	AdjustDown(p->array, p->size, 0);//删除的时候parent是0，向下删除，parent不一定是从0开始的，所以保留了这个接口
 
}
HeapDataType HeapTop(Heap* p)
{
	assert(p);
	assert(p->size > 0);
	return p->array[0];
}
bool HeapEmpty(Heap* p)
{
	assert(p);
	return p->size == 0;//等于0就是空，不等于0就不为空
}
int HeapSize(Heap* p)
{
	assert(p);
	return p->size;
}
 
//真正的堆排序不需要堆的数据结构
void HeapSort(int *a,int n)
{
	//{27，15，19，18，28，34，65，49，25，37}；
	//                   27
    //              15        19
    //           18    28   34   65
	//	     49   25  37
 
	//我们将传入的数组看成是二叉树，但是此时并不是堆，因为没有排序。
 
	建堆（向上插入帮助我们建堆）
	相当于第0个位置不动，第一个位置开始插入就行，每次插入都相当于是一次向上调整
	//for (int i = 1; i < n; i++)
	//{
	//	AdjustUp(a, i);
	//}
	相当于一次插入的过程
	
	//建堆
	//向下调整要求左子树是堆，右子树也是堆，但现在排序的数组左右子树不是堆
	//从倒数第一个非叶子节点开始调整，叶子节点不需要调。（也就是从28开始调）
	//孩子比父亲大就换（37跟28比较，将37和28换，49和18调换，65和19，49和15至此左子树就调整完成）
	// //               27
	//          49            65
    //     15       37    34      19
    //  18   25   18
	//28这个位置下标怎么计算：28是最后一个节点的父亲。
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
		//最后一个节点：n-1,算父亲再-1除以2 
	{
		AdjustDown(a, n, i);
	}//这里的i=n-1，这样写也可以，从最后一个数开始调整，只不过比上面多走了几次
	//堆向上向下调整的次数，在完全二叉树下是数的高度，logN
	//两个分别建堆的时间复杂度是：方式1：O（N*logN），方式2：O（N）
	//第二个建堆的方法要更好一些
 
	//升序的话，如果构建小根堆选择最小的，之后还得选择次小的，但是这时的关系全部乱了，需要继续新的建堆
	//每次的时间复杂度是O（N^2）跟遍历一遍数组选出最小的一样，没有体现出堆的特性
	//升序要建大堆，选出最大的数，把最大的数跟末尾的数交换，如同堆删除的思路
	//之前是N个数现在可以看成是N-1个数（不看尾的数）这时不看第一个数，左子树跟右子树依旧是大堆
	//要选出次大的数，向下调整一次就可以，时间复杂度是logN
	//有N-1个数要选择，就要选N*logN次，对比之前建小堆或者直接遍历的O（N^2）比如一千个数，大堆才十次
 
	int end = n - 1;
	while (end>0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);//只有n-1个数选出最大的
		end--;
	}
	//整体的时间复杂度：O（N*logN）
 
}

Test.c
#define _CRT_SECURE_NO_WARNINGS  1
#include"Heap.h"
void TestHeapPush()
{
	Heap hp1;
	HeapInit(&hp1);
	int a[] = { 27,15,19,18,28,34,65,49,25,37 };
	int sz = sizeof(a) / sizeof(a[0]);
	for (int i = 0; i < sz; i++)
	{
		HeapPush(&hp1, a[i]);
	}
	HeapPrint(&hp1);
	HeapPush(&hp1, 10);
	HeapPrint(&hp1);
	
}
void TestHeapPop()
{
	Heap hp1;
	HeapInit(&hp1);
	int a[] = { 27,15,19,18,28,34,65,49,25,37 };
	int sz = sizeof(a) / sizeof(a[0]);
	for (int i = 0; i < sz; i++)
	{
		HeapPush(&hp1, a[i]);
	}
	HeapPrint(&hp1);
	HeapPop(&hp1, 27);
	HeapPrint(&hp1);
	HeapPop(&hp1);
	HeapPrint(&hp1);
}
//这里的堆排序有两个问题
//1.你得先写一个堆的数据结构，反而复杂
//2.有O（n）的空间复杂度
void TestHeapSort()//堆排序
{
	//升序打印
	Heap hp1;
	HeapInit(&hp1);
	int a[] = { 27,15,19,18,28,34,65,49,25,37 };
	int sz = sizeof(a) / sizeof(a[0]);
	for (int i = 0; i < sz; i++)
	{
		HeapPush(&hp1, a[i]);
	}
	while (!HeapEmpty(&hp1))
	{
		printf("%d ", HeapTop(&hp1));
		HeapPop(&hp1);
	}
	
	//每次只取堆顶的，堆顶就是最小的，循环直到结束会得到升序的数
	HeapDestory(&hp1);
}
int main()
{
	//TestHeapPush();
	//TestHeapPop();
	//TestHeapSort();
	int a[] = { 27,15,19,18,28,34,65,49,25,37 };
	HeapSort(a, sizeof(a) / sizeof(int));
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}

向下调整：

越上面的节点少调整次数多，越下面的节点多调整次数少

调整的次数=总节点的个数×这一层调整的次数

T(n)=2^0* (h -1)＋2^1*(h -2)+2^2*(h-3)＋2^3*(h -4)+...+2^(h-3)*2+2^(h-2)* 1①

2*T(n)=2^1* (h -1)＋2^2*(h -2)+2^3*(h-3)＋2^4*(h -4)+...+2^(h-2)*2+2^(h-1)* 1②

因此：建堆的时间复杂度为O(N)

向上调整要最后一层，向下调整不需要最后一层，从倒数第二层开始

最后一层有2^(h-1)个节点，最坏调整h-1次

T(N)=2^1*1+2^2*2+2^3*3+………….+2^(h-2)*(h-2)+2^(h-1)*(h-1)

继续用错位相减

T（N）=N*logN

TOP-K问题（N个数中找最大的/最小的前k个，N是远大于K）

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能 数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

找最大的前k个

1. 堆排序（N*logN）
2. 建N个数的大堆，Top/Pop K次 时间复杂度是O（N+logN*K）（向下建堆是O（N），向上建堆是O（N*logN），选向下） （建立N个数的堆用向下建堆，之后Pop K次，首尾互换，把尾给换掉向下调整，调整logN次，总共调整K次，是logN*K次）
3. 假设N非常大，比如N是100亿，K比较小，K是100，如何求解？

问题是内存存不下这么大的数，所以1跟2方法都不适合，堆无非建立起来。

将k个数当作堆建立起来，K比较小，前k个数建立一个小堆，这里跟堆排序的思路比较类似有点反过来的感觉，排降序用的是小堆。1> 用数据集合中前K个元素来建堆，前k个最大的元素，则建小堆 ；前k个最小的元素，则建大堆

2>用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素

将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

例如排降序：1.前k个数先建立小堆 2.剩下的N-K个依次跟堆顶数据比较，如果比堆顶数据大，则替换堆顶数据进堆，走完之后，堆里面的数就是最大的前K个。如果建大堆只能选最大的那一个数，不能选最大的前k个数。

它的时间复杂度是O（k+(N-k)*logK）这个在时间效率并没有太快于第二个算法的时间，但是在内存空间上，2是需要建立很大的大堆，它的空间复杂度是k只需要开辟k个这么大的空间建堆

//这里的堆排序有两个问题
//1.你得先写一个堆的数据结构，反而复杂
//2.有O（n）的空间复杂度
void TestHeapSort()//堆排序
{
	//升序打印
	Heap hp1;
	HeapInit(&hp1);
	int a[] = { 27,15,19,18,28,34,65,49,25,37 };
	int sz = sizeof(a) / sizeof(a[0]);
	for (int i = 0; i < sz; i++)
	{
		HeapPush(&hp1, a[i]);
	}
	while (!HeapEmpty(&hp1))
	{
		printf("%d ", HeapTop(&hp1));
		HeapPop(&hp1);
	}
	
	//每次只取堆顶的，堆顶就是最小的，循环直到结束会得到升序的数
	HeapDestory(&hp1);
}
 
//不需要用自己堆的数据结构
void PrintTopK(int* a, int n, int k)
{
	int* KMinHeap = malloc(sizeof(int) * k);
	assert(KMinHeap);
	for (int i = 0; i < k; ++i)
	{
		KMinHeap[i] = a[i];
	}
	// 1. 建堆--用a中前k个元素建堆(最后一个非叶子节点的下标开始建堆）
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(KMinHeap, k, i);
	}
	// 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换(遍历剩下的n-k个数)
	for (int j = k; j < n; j++)
	{
		if (a[j] > KMinHeap[0])
		{
			KMinHeap[0] = a[j];
			AdjustDown(KMinHeap, k, 0);
		}
	}
	//最后的堆里面的数就是最大的前k个数
	for (int i = 0; i < k; i++)
	{
		printf("%d ", KMinHeap[i]);
	}
	printf("\n");
}
 
void TestTopk()
{
	int n = 10000;
	int* a = (int*)malloc(sizeof(int) * n);
	srand(time(0));
	for (int i = 0; i < n; ++i)
	{
		a[i] = rand() % 1000000;//每个数都小于100 0000
	}
	//给十个大于100 0000的数
	//最后如果打印出十个下面比100 0000大的数说明程序就ok
	a[5] = 1000000 + 1;
	a[1231] = 1000000 + 2;
	a[531] = 1000000 + 3;
	a[5121] = 1000000 + 4;
	a[115] = 1000000 + 5;
	a[2335] = 1000000 + 6;
	a[9999] = 1000000 + 7;
	a[76] = 1000000 + 8;
	a[423] = 1000000 + 9;
	a[3144] = 1000000 + 10;
	PrintTopK(a, n, 10);//10000个数据里面找10个最大的
}

链式二叉树：

如果是完全二叉树或者满二叉树，用数组的方式可以表示，如果不是完全二叉树或者满二叉树数组无非很好的表示，链式的二叉树是更合适的。链式的这种普通二叉树的增删查改没有意义。存储数据的话不如用顺序表和链表，学习它的意义：1.为我们后续学习更复杂的二叉树打好基础。（搜素二叉树，AVL树，红黑树，B树….）

学习遍历或者控制结构

二叉树的遍历

前序、中序以及后序遍历

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

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

任何一个树都要被分为根 左子树 右子树

1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。 （根 左子树 右子树）

2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。

（左子树 根 右子树）

3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为 根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。（左子树 右子树 根）

#：表示NULL

前序遍历结果：1 2 3 # # # 4 5 # # 6 # #（根 左 右）

中序遍历结果：# 3 # 2 # 1 # 5 # 4 # 6 #（左 根 右）

后序遍历结果：# # 3 # 2 # 5 # # 6 4 1  （左 右 根）

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
	BTDataType data;
 
}BTNode;
BTNode* BuyNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	assert(node);
	node->data = x;
	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;
}
void PreOrder(BTNode*root)//前序
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}
	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
 
}
 
void InOrder(BTNode* root)//中序
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}
	
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}
 
void PostOrder(BTNode* root)//后序
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}
int main()
{
	BTNode* root = CreatBinaryTree();
	PreOrder(root);
	printf("\n");
	InOrder(root);
	printf("\n");
	PostOrder(root);
	printf("\n");
 
	return 0;
}

与上面我们分析结果相同；我们创造了这样一个树

这里用到了分治算法（二分查找也用到了这个算法）

分而治之，把大问题分成类似规模的小问题，这里可以用递归写；

第一次传入是1这个节点的地址（用1代表），1不是NULL，打印1，之后访问左子树，递归1的左子树，往下递归，2不是NULL再向下递归，先访问2这个子树，2继续访问左子树是3，3的左子树是NULL，打印#，并且返回，返回到上一个递归的3调用的函数中应该是右子树，3的右子树为NULL,则继续打印#，回到它调用的地方，是2左调用的，之后回到2访问右子树，2 的右子树是NULL，打印#，回到1，访问1的右树，下来是4，打印4，之后访问左子树是5，5的左子树是NULL，访问5的右子树是NULL，访问6的左子树是NULL最后访问6的右子树为NULL；最后递归结束。从物理上来看是建立栈帧；栈帧结束回到上一层栈帧；

最开始传入的是根，根节点是1，1不是NULL，遇到1 不能访问先递归走它的左子树，遇到2不能访问继续走它的左树，到3，3的左边是NULL打印#，return回去（一个函数调用完无论是return回去还是正常的执行结束都是回到调用的地方）下一个打印3，递归到3的右树，打印#，return回到上一层，上一层的左树已经调用完了直接就到了第二步打印，回到了2，访问2的右树，右树为NULL打印#，回到1，打印1，继续走1的右树，访问4，4不是NULL走4的左……直到访问完到底。

后序跟前面相同；

下面是计算二叉树存了多少个数

//遍历的思路

int count=0 ;
int TreeSize(BTNode*root)//求二叉树中存了多少个数据
{
	//这里的计数不能像链表里面的计数一样放在函数里面
	//链表的计数是迭代，这里的递归不能这样，每个栈帧都有一个计数的count
	//int count=0；
	if (root == NULL)
	{
		return;
	}
	++count;
	TreeSize(root->left);
	TreeSize(root->right);
}
注意在每次调用的时候要把count=0；（局部变量）置空一下；
这里如果多线程的时候可能同时用这个函数，同时计数可能会混，这个count会多个一起计数，全局可见的
//分治的思路
int TreeSize2(BTNode* root)
{
	return root == NULL ? 0 : TreeSize2(root->left) + TreeSize2(root->right)+1;
	//+1是因为我们计数的时候把数分成3部分，左子树 自己 右子树
}
这样调用多次也不需要每次把count置成0；
 
int TreeLeafSize(BTNode* root)//求叶子结点（根为0的才是叶子）
{
	if (root == NULL)
	{
		return 0;
	}
	if ((root->left == NULL) && (root->right == NULL))
	{
		return 1;
	}
	//是NULL返回0个，是叶子返回1个，不是NULL也不是叶子结点转换左子树叶子节点+右子树叶子节点
 
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}
 
 
//继续用分治的想法把大问题分成小问题；
//换成子问题：求第k层，看成是求左子树的第k-1层+求右子树的第k-1层
int TreeKLevel(BTNode* root, int k)//求第k层的节点
{
	assert(k >= 1);
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return TreeKLevel(root->right, k - 1) + TreeKLevel(root->left, k - 1);
 
}
 
//二叉树查找值为x的结点
BTNode* TreeFind(BTNode* root ,BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	BTNode* ret1 = TreeFind(root->left, x);
	if (ret1)
	{
		return ret1; 
	}
	BTNode* ret2 = TreeFind(root->right, x);
	if (ret2)
	{
		return ret2;
	}
	return NULL;
}