前面所讲到的数据结构比如：顺序表，链表，栈，队列都是属于线性结构，但是到了二叉树这里就是非线性结构了。下面我们先来认识一下什么是树。
树的概念和结构
树的结构
树，就是一些有限个点的集合。
就像这个样子就是一颗树，因为这个结构看起来像是一颗倒挂的树，所以他的结构就叫做树。
树的节点有一个特殊的节点就是**根节点 **在上面的图中就是节点A，除了跟节点每个节点都有一个在他上面的节点。也叫做这个节点的父节点，比如：B节点的祖先就是A节点。
树是递归定义的。比如我们可以将上面那个树看成是根节点和三棵子树B，C，D每颗子树又可以分成根节点和子树。
要注意子树和子树之间是不能链接在一起的。
比如B子树的F节点不能和C子树的G节点链接在一起，否则就不是树而是图了。
树的概念
节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：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）棵互不相交的树的集合称为森林；
还有一个概念就是树的高度，树的高度有两种算法。
1.第一个节点从0开始数（根节点的高度视为0）
2.第一个节点从1开始数（推荐）
一般来说常用的都是从1开始计算树的高度，因为这样，空树的高度就是0，如果从0开始数，那么空树的高度就是-1了。不太合适。
树的表示
树的表示不可以使用之前像是链表节点那样的表示方法来表示树的节点，因为树的节点可能一个节点指向多个节点。
这里的表示方法有三种
1.在每个节点里面放一个顺序表（顺序表的每个元素都是节点的指针）（使用vector会更好可以自动伸缩）
2.左孩子右兄弟表示方法。
每个节点里面有两个指针，左指针指向该节点的从左数第一个孩子。右指针指向兄弟节点。
结构如图：
注意：不同父节点的节点在这不算是兄弟。比如F和G就不算是兄弟。
3.双亲表示法
使用一个数组来保存树的结构，每个节点有一个数据域一个指针域，指针域保存节点的父亲节点的下标。
树的应用
树在Linux里面用作文件存储系统。Windows里用的是森林。
树基本不会用来作为存储数据的结构。
二叉树的概念和结构
二叉树的结构
二叉树就是在树的基础上多了一个限制属性，树的度（也就是子树个数）可以是任意个，但是二叉树的度不能大于2.
二叉树的节点二叉树总共就有如下的几种节点结构
特殊的二叉树
1.满二叉树：
满二叉树就是除了叶子节点，其他节点的度都是2.
2.完全二叉树
完全二叉树就是除了最下面那一层其他层都是满的，最后一层可以不满但是只能从右开始缺节点。
比如：
这个缺了最右边的节点，所以他是完全二叉树。
比如：
这颗树缺少节点就不是从右开始并且连续的。所以这个树就不是完全二叉树。
二叉树的性质
- 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有
个结点.- 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是
（满二叉树）- 对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2 ,则有n0 ＝ n2＋1
- 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=
. (ps：
是log以2为底，n+1为对数)- 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从1开始编号，则对
于序号为i的结点有：
若i > 0，i位置节点的父节点的序号为：(i - 1 )/2；若i为根节点编号1，无父节点
若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子
若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子
二叉树的存储结构方式
二叉树可以使用两种结构来存储，一种是顺序结构，也就是数组。另一种是链式结构，像是链表一样的一个一个节点。
顺序结构：
顺序结构一般只用来保存完全二叉树，因为完全二叉树使用数组保存的时候并不需要空出多个空位，可以在数组中连续存放。
链式存储
链式存储就是像链表一样一个一个节点，通过指针链接在一起，每个节点的存储位置都是随机的。地址不一定连续。
同时链式存储这里的链接结构分为两种，一种是二叉链，就是一个节点只有两个指针域分别是left和right指针。而三叉链，每个节点包含有三个指针，分别是left和right还有parent。所以三叉链的二叉树可以很容易的找到父节点。
下面分别来看一下二叉链和三叉链的节点结构
typedef int BTData;
//二叉链
struct BinaryNode
{
BTData val;
struct BinaryNode* left;
struct BinaryNode* right;
};
//三叉链
struct ThridNode
{
BTData val;
struct ThridNode* left;
struct ThridNode* right;
struct ThridNode* parent;
};
二叉树的顺序结构存储实现
顺序存储结构只适合完全二叉树的存储，下面我们就来实现完全二叉树的顺序结构存储。
其实完全二叉树又叫做堆，堆是完全二叉树的一种特殊情况。
比如大根堆，和小根堆。
大根堆就是每个节点的val值都比左右孩子的val值要大。
小根堆就是每个节点的val值都比左右孩子的val值要小。
堆的逻辑结构和存储结构
逻辑结构就是我们想象出来的形象的结构。实际在内存中并不一定是这个结构。而存储结构就是我们真正存在内存里面的时候这个数据结构真正的结构。
堆的实现
了解了堆的结构，就需要实现堆，堆并不是随便一颗完全二叉树。这棵完全二叉树需要满足堆的性质。大根堆或者小根堆。
首先我们需要将一颗完全二叉树构建成一个堆。
这里假设我们要构建一个小根堆。
1.向上调整算法
将数组中的节点，一个一个的插入堆，一开始是一个，然后是两个以此类推。插入一个节点到数组的尾部的时候在逻辑结构上是插入到了完全二叉树的最底层的最后一个节点右边的位置。然后因为这个二叉树是小堆，所以我们需要向上调整。
向上调整算法的逻辑：将新插入的节点x的val与父节点的val比较，如果比父亲小则交换父亲和x然后再向上调整，直到最后x已经是堆顶，或者父亲比x小则停止。
2.向下调整算法
与向上调整算法不同，向下调整算法有一个前提，那就是必须左右子树都已经是堆了。这里要求建小堆，所以左右子树必须也是小堆才可以进行向下调整算法。
从最后一个节点的父节点开始向下调整。也就是倒数第二层。然后依次向上遍历，将节点向下调整。因为倒数第二层的节点他们的子树只有一个节点所以左右子树已经是小堆了。满足条件。
向下调整算法逻辑：将父节点与左右孩子中更小的那个比较。如果父亲比最小的孩子的val大，那么就将父亲与这个孩子交换，然后继续向下调整。直到左右孩子的下标超过了数组的最大下标，或者是父节点的val已经比左右孩子中最小的那个value还要小就停止。
这里还有一个问题就是我们如何求左右孩子的下标，以及如何通过最后一个节点的下标位置求出来他的父亲的下标呢？
堆常用公式
这里使用left代表左孩子下标，right代表右孩子下标，parent代表父亲的下标
1.left = parent * 2 + 1;
2.right = parent * 2 + 2 = left + 1;
3.parent = (left - 1 ) / 2；
或者是：parent = (right - 1 ) / 2
都是可以的。
构建堆的过程
下面来看一下使用向下调整算法构建大根堆的过程图
两种建堆方式的时间复杂度
第一种采用不断向堆插入节点然后向上调整。
首先向上调整算法因为堆是一个完全二叉树，所以最多向上调整高度次也就是logn次。所以向上调整算法的时间复杂度是logn，n次插入节点每次都是向上调整。所以这种建堆的方式的时间复杂度就是nlogn。
第二种采用自底向上遍历向下调整算法
这种建堆方式的计算就要复杂一些。
经过计算得出这种建堆方式的时间复杂度就是O（n），其实根据计算过程也可以看出，向下调整的时间复杂度肯定要优于向上调整。因为向下调整在节点最多的底层向下调整的次数少。越向上走，节点越少，调整的次数才开始多起来。但是向上调整，在最底层节点最多的时候向上调整的次数也最多。所以时间复杂度就更大。
堆的插入
堆的插入就是在最底层插入一个节点，然后采用向上调整算法，将这个节点调整到合适的位置。
堆的删除
堆删除第一个元素其实很简单，只需要将堆顶的元素与堆的最后一个元素交换位置，然后抛弃最后一个节点，调用向下调整算法进行堆的调整即可。
堆的实现代码
上面都是理论下面就是代码实现
//堆的实现代码
typedef int HPDataType;
typedef struct Heap
{
HPDataType* _a;
int _size;
int _capacity;
}Heap;
// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n);
//向上调整算法
void AdJustUp(Heap* hp,int child);
//向下调整算法
void AdJustDown(Heap* hp,int parent);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);
#define _CRT_SECURE_NO_WARNINGS
#include"BinaryTree_Heap.h"
//排升序，建大堆
void swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
//向上调整算法
void AdJustUp(Heap* hp, int child)
{
assert(hp);
int parent = (child - 1) / 2;
while (child)
{
if (hp->_a[parent] < hp->_a[child])
{
swap(&hp->_a[parent], &hp->_a[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
//向下调整算法
void AdJustDown(Heap* hp, int parent)
{
assert(hp);
int child = parent * 2 + 1;
while (child < hp->_size)
{
if (child + 1 < hp->_size && hp->_a[child + 1] > hp->_a[child])
{
child++;
}
if (hp->_a[parent] < hp->_a[child])
{
swap(&hp->_a[parent], &hp->_a[child]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n)
{
assert(a && hp);
if (n == 0)
{
printf("空树\n");
return;
}
HPDataType* tmp = (HPDataType*)malloc(sizeof(HPDataType) * n);
if (tmp == NULL)
{
perror("malloc file");
exit(-1);
}
for (int i = 0; i < n; i++)
{
tmp[i] = a[i];
}
hp->_a = tmp;
hp->_size = n;
hp->_capacity = n;
for (int end = (n - 1 - 1) / 2; end >= 0; end--)
{
AdJustDown(hp, end);
}
}
// 堆的销毁
void HeapDestory(Heap* hp)
{
assert(hp);
free(hp->_a);
hp->_a = NULL;
hp->_size = hp->_capacity = 0;
}
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
assert(hp);
if (hp->_capacity == hp->_size)
{
HPDataType* tmp = (HPDataType*)realloc(hp->_a, hp->_capacity * 2*sizeof(HPDataType));
if (tmp == NULL)
{
perror("realloc file");
exit(-1);
}
hp->_a = tmp;
hp->_capacity *= 2;
}
hp->_a[hp->_size] = x;
hp->_size++;
AdJustUp(hp,hp->_size - 1);
}
// 堆的删除
void HeapPop(Heap* hp)
{
assert(hp);
swap(&hp->_a[0], &hp->_a[hp->_size - 1]);
hp->_size--;
AdJustDown(hp, 0);
}
// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
assert(hp);
return hp->_a[0];
}
// 堆的数据个数
int HeapSize(Heap* hp)
{
assert(hp);
return hp->_size;
}
// 堆的判空
int HeapEmpty(Heap* hp)
{
assert(hp);
return hp->_size == 0;
}
堆的应用
堆的应用主要有两种，其一就是堆排序。其二就是topk问题。
这两种问题都是利用了堆的向下调整算法效率高。
首先堆排序，如果我们要排升序是要建大堆还是小堆呢？
答案是：大堆。因为建堆后堆顶元素就是最大的，相当于已经从数组中选出来了一个最大的数，只需要将这个数字移动到数字的尾部，然后向下调整再次选出剩下的数中的最大数。因为堆优化了选数的效率所以时间复杂度是O（NlogN）。
如果建小堆，那么堆顶的元素是最小的确实，第一个位置已经排好了，但是剩下的呢？再次建堆的时间复杂度是O（N）那这堆排序和直接选择的时间复杂度就无异了。
堆排序的代码实现
void AdJustDownSort(int* a, int n,int parent)
{
int child = parent * 2 + 1;
while (child < n)
{
if (child + 1 < n && a[child + 1] > a[child])
{
child++;
}
if (a[parent] < a[child])
{
swap(&a[parent], &a[child]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
//堆排序
void HeapSort(int* a, int n)
{
for (int end = (n - 1 - 1) / 2; end >= 0; end--)
{
AdJustDownSort(a, n, end);
}
int i = 1;
while (i < n)
{
swap(&a[0], &a[n - i]);
AdJustDownSort(a, n - i, 0);
i++;
}
}
TOPK问题
TOPK问题就是在N个数字里面选出最大的或者最小的K，一个方法就是现建堆，然后循环k次选出来k个数，这k个数就是最大或者最小的k个数。这个方法时间复杂度是O（N + K * logN）
但是还有一个更优的方法，就是现用前k个数字建小堆，然后遍历剩下的元素，如果比堆顶的元素大那么就替换堆顶的元素然后向下调整，当遍历完剩下的元素的时候这个k个元素的堆里面就是k个最大的值。这个方法的时间复杂度是O（K + （N - K）* logK）对比上个方法当K比较小的时候这两个方法差不多，但是当K很大时候第二个方法显然优于第一个方法，因为K和N接近，那么第二个方法后面logK次调整可忽略了。但是第一个方法就是N+K*logN了。
二叉树链式结构的实现
二叉树的链式结构的实现很简单，这里我们并不需要研究二叉树的增删查改，因为普通二叉树的增删查改是没有意义的，后面的数据结构，比如搜索二叉树，这种结构研究增删查改才具有意义。
二叉树有两种构建方式，一种是简单粗暴，直接malloc节点，然后手动连接起来。方便快速构建一棵树用来测试代码。
另一种方式，因为我们看一颗二叉树可以分为根节点和左右子树，左右子树又可以分为根节点和左右子树。不断递归直到空，所以如果给我们一个前序或者中序的序列也是可以构建出一颗二叉树的。
typedef int BTDataType;
typedef struct BinaryTreeNode
{
BTDataType _data;
struct BinaryTreeNode* _left;
struct BinaryTreeNode* _right;
}BTNode;
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;
}
通过递归方式手动构建二叉树。
KY11 二叉树遍历
#include<stdio.h>
typedef struct BinaryTreeNode
{
char val;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
void Inorder(BTNode* root)
{
if(root == NULL)
return;
Inorder(root->left);
printf("%c ",root->val);
Inorder(root->right);
}
//递归构建，这里i要使用指针或者引用，方便下一层栈帧可以向后增加i
BTNode* CreatTree(char* str,int* pi)
{
if(str[*pi] == '#')
{
return NULL;
}
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
node->val = str[*pi];
(*pi)++;
node->left = CreatTree(str,pi);
(*pi)++;
node->right = CreatTree(str, pi);
return node;
}
int main()
{
char arr[110] = {0};
while(scanf("%s",arr)!=EOF)
{
int i = 0;
BTNode* root = CreatTree(arr,&i);
Inorder(root);
puts("");
}
return 0;
}
二叉树的遍历
二叉树的前序中序和后序遍历
前序遍历就是先访问根节点，然后访问左子树，再访问右子树。
中序遍历就是先访问左子树，然后访问根节点，最后访问右子树。
后序遍历就是先访问左子树，然后访问右子树，最后访问根节点。
前序中序和后序实际就是根节点的访问次序，所以又叫做，前根遍历，中根遍历，后根遍历。
下面是递归展开图，看一下前序遍历的思想。
主要的思想就是分治思想，前序遍历，先访问根节点，然后访问左子树，访问左子树又是先根然后左子树，直到空。就是一个很明显的递归思想，中序和后序也是类似。
//前序遍历
void PreOrder(BTNode* root)
{
if (root == NULL)
return;
printf("%d ", root->val);
PreOrder(root->left);
PreOrder(root->right);
}
//中序
void InOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
InOrder(root->left);
printf("%d ", root->val);
InOrder(root->right);
}
//后序
void AfterOrder(BTNode* root)
{
if (root == NULL)
return;
AfterOrder(root->left);
AfterOrder(root->right);
printf("%d ", root->val);
}
二叉树的层序遍历
二叉树的层序遍历实际很简单一层一层的遍历，每一层都是从左向右依次遍历，遍历完这一层之后才跳转到下一层。
层序遍历可以借助栈或者队列实现，思路差不多，都是借助容器来保存节点指针，注意是节点指针。这里我是用的是队列实现，因为队列的先进先出的特性比较简单。
// 层序遍历
void LevelOrder(BTNode* root)
{
if (root == NULL)
return;
queue<BTNode*> qe;
qe.push(root);
while (!qe.empty())
{
BTNode* front = qe.front();
qe.pop();
printf("%d ", front->val);
if (front->left)
qe.push(front->left);
if (front->right)
qe.push(front->right);
}
}
二叉树的节点函数
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
下面是实现代码
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
if (root == NULL)
return 0;
return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
if (root == NULL)
return 0;
if (root->left == NULL && root->right == NULL)
return 1;
return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
int floor_size = 1;
int count = 0;
queue<BTNode*> que;
que.push(root);
while (!que.empty())
{
if (k == 1)
{
count = floor_size;
break;
}
BTNode* node = que.front();
que.pop();
floor_size--;
if (node->left)
que.push(node->left);
if (node->right)
que.push(node->right);
if (floor_size == 0)
{
floor_size = que.size();
k--;
}
}
return count;
}
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
return NULL;
if (root->val == x)
return root;
BTNode* fl = BinaryTreeFind(root->left, x);
return fl == NULL ? BinaryTreeFind(root->right,x) : fl;
}
求二叉树的节点数和叶子节点的个数都是分治思想，二叉树的节点数就是左子树的节点数加右子树的节点数在加上根节点的1，就可以了。
叶子节点的个数就是左子树叶子节点的个数加上右子树叶子节点的个数。
求第k层节点数，这里的思想是利用层序遍历，层序遍历使用一个size记录第一层的节点个数，每次取出一个节点size–。如果size等于0，这时候就是当前层已经全部取完了。下一层的节点也已经全部进去了。所以更新size为队列里面的元素个数。这时候同样也跟着–k，代表进入下一层，当k等于1的时候说明到了我们要求的这一层的节点个数，所以这一层的节点数就是等于size。直接返回即可。
查找的思想很简单，就是遍历二叉树然后比对查找，先比根节点是不是，再去左子树查找如果左子树没找到，就将右子树的查找结果返回。
二叉树的销毁
// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{
if (*root == NULL)
return;
BinaryTreeDestory(&(*root)->left);
BinaryTreeDestory(&(*root)->right);
free(*root);
*root = NULL;
}
二叉树的销毁使用的也是递归销毁，先销毁左右子树然后销毁根节点。
判断二叉树是否为完全二叉树
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{
queue<BTNode*> que;
que.push(root);
while (!que.empty())
{
BTNode* node = que.front();
que.pop();
if (node == NULL)
break;
que.push(node->left);
que.push(node->right);
}
while (!que.empty())
{
BTNode* node = que.front();
que.pop();
if (node != NULL)
return false;
}
return true;
}
思想是层序遍历的思想，不同的是，向队列内入节点的时候不需要判断，将NULL也入进去。当取出来的节点为NULL时，跳出第一层循环，这时候如果时完全二叉树那么队列内剩下的元素都是NULL。如果不是完全二叉树，那么剩下的元素内肯定存在不为NULL的节点。