二叉树
1.树的概念及结构
1.1树的概念
树是一种数据结构，它是由n(n≥1)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
特点：
1、有一个特殊的结点，称为根结点，根节点没有前驱结点。
2、除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i<= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。
3、因此，树是递归定义的。
注意：树形结构中，子树之间不能有交集，否则就不是树形结构。
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）棵互不相交的树的集合称为森林。
1.3树的表示
树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。
typedef int DataType;
struct Node
{
struct Node* _firstChild1; // 第一个孩子结点
struct Node* _pNextBrother; // 指向其下一个兄弟结点
DataType _data; // 结点中的数据域
};
2.二叉树概念及结构
2.1概念
二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个结点最多只能有两棵子树，且有左右之分 。
二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点 。
特点：
一棵二叉树是结点的一个有限集合，该集合:
1.或者为空
2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成
从上图可以看出：
1 .二叉树不存在度大于2的结点
2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
注意：对于任意的二叉树都是由以下几种情况复合而成的：
2.2特殊的二叉树
- 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是 ，则它就是满二叉树。
- 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
2.3二叉树的性质
2.4二叉树的存储结构
二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。
- 顺序存储
顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。
- 链式存储
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。
typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
struct BinTreeNode* _pLeft; // 指向当前节点左孩子
struct BinTreeNode* _pRight; // 指向当前节点右孩子
BTDataType _data; // 当前节点值域
}
3.二叉树的顺序结构及实现
3.1二叉树的顺序结构
普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。 现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储。
需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。
3.2堆的概念及结构
堆的性质：
1、堆中某个节点的值总是不大于或不小于其父节点的值；
2、堆总是一棵完全二叉树。
3.3堆的实现
3.3.1堆向下调整算法
现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。
int array[] = {27,15,19,18,28,34,65,49,25,37};
3.3.2堆的创建
下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。
int a[] = {1,5,3,8,7,6};
3.3.3建堆时间复杂度
3.3.4堆的插入
先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆。
3.3.5堆的删除
删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。
3.3.6堆的代码实现
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}HP;
//交换函数
void Swap(int* px, int* py);
//向下调整算法
void AdjustDown(int* a, int n, int parent);
//向上调整算法
void AdjustUp(int* a,int child);
//堆初始化
//void HeapInit(HP* php);
void HeapInit(HP* php,HPDataType* a,int n);
//堆销毁
void HeapDestroy(HP* php);
//堆的插入，插入x，保持它继续是堆
void HeapPush(HP* php, HPDataType x);
//堆的删除，删除堆顶数据，删除后保持它继续是堆
void HeapPop(HP* php);
//获得堆顶数据，也就是最值
HPDataType HeapTop(HP* php);
//堆的判空
bool HeapEmpty(HP* php);
//求堆有多少的元素
int HeapSize(HP* php);
//堆的打印
void HeapPrint(HP* php);
交换函数
void Swap(int* px, int* py)
{
int tmp = *px;
*px = *py;
*py = tmp;
}
向下调整算法
//条件:左右子树都是小堆/大堆
//示例:小堆
void AdjustDown(int* a, int n, int parent)
{
int child = parent * 2 + 1;
while (child<n)
{
//选出左右孩子中小的那个
if (child + 1 < n && a[child + 1] > a[child])//判断是否越界
{
++child;
}
//1.如果小的孩子小于父亲，则交换，继续往下调整。
//2.如果小的孩子大于父亲，则结束。
if (a[child]>a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
向上调整算法
void AdjustUp(int* a,int child)
{
int parent = (child - 1) / 2;
while (child>0)
{
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
堆初始化
void HeapInit(HP* php, HPDataType* a, int n)
{
assert(php);
php->a = (HPDataType*)malloc(sizeof(HPDataType)*n);
if (php->a == NULL)
{
printf("malloc fail\n");
exit(-1);
}
memcpy(php->a, a, sizeof(HPDataType)*n);
//建堆
for (int i = (n - 2) / 2; i >= 0; i--)
{
AdjustDown(php->a, n, i);
}
php->size = n;
php->capacity = n;
}
堆销毁
void HeapDestroy(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->size = php->capacity = 0;
}
堆的插入
//插入x，保持它继续是堆
void HeapPush(HP* php, HPDataType x)
{
assert(php);
if (php->size == php->capacity)
{
HPDataType* tmp = (HPDataType*)realloc(php->a, php->capacity * 2 * sizeof(HPDataType));
if (php->a == NULL)
{
printf("realloc fail\n");
exit(-1);
}
php->capacity *= 2;
}
php->a[php->size] = x;
php->size++;
AdjustUp(php->a, php->size - 1);
}
堆的删除
//删除堆顶数据，删除后保持它继续是堆
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];
}
堆的判空
bool HeapEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
求堆有多少的元素
int HeapSize(HP* php)
{
assert(php);
return php->size;
}
堆的打印
void HeapPrint(HP* php)
{
for (int i = 0; i < php->size; i++)
{
printf("%d ", php->a[i]);
}
printf("\n");
}
3.4堆的应用
3.4.1堆排序
堆排序即利用堆的思想来进行排序，总共分为两个步骤：
- 建堆
升序：建大堆
降序：建小堆
示例：
//堆排序 -> 效率更高
//排升序->大堆
//排降序->小堆
void HeapSort(int* a, int n)
{
//建堆算法
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
//降序
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
end--;
}
}
- 利用堆删除思想来进行排序
建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。
3.4.2TOP-K问题
TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：
- 用数据集合中前K个元素来建堆
(1)前k个最大的元素，则建小堆
(2)前k个最小的元素，则建大堆 - 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
void PrintTopK(int* a, int n, int k)
{
HP hp;
HeapInit(&hp, a, k);
for (int i = k; i < n; ++i)
{
if (a[i] > HeapTop(&hp))
{
HeapPop(&hp);
HeapPush(&hp, a[i]);
}
}
HeapPrint(&hp);
HeapDestroy(&hp);
}
void TestTopk()
{
int n = 100000;
int* a = (int*)malloc(sizeof(int)*n);
srand(time(0));
for (size_t i = 0; i < n; ++i)
{
a[i] = rand() % 1000000;
}
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);
}
4.二叉树链式结构的实现
4.1前置说明
在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入，为了降低大家学习成本，此处手动快速创建一棵简单的二叉树，快速进入二叉树操作学习，等二叉树结构了解的差不多时，我们反过头再来研究二叉树真正的创建方式。
typedef char BTDataType;
typedef struct BinaryTreeNode
{
BTDataType _data;
struct BinaryTreeNode* _left;
struct BinaryTreeNode* _right;
}BTNode;
BTNode* BuyNode(BTDataType x)
{
BTNode* node = malloc(sizeof(BTNode));
node->_data = x;
node->_left = NULL;
node->_right = NULL;
return node;
}
BTNode* CreatBinaryTree()
{
BTNode* node1 = BuyNode('A');
BTNode* node2 = BuyNode('B');
BTNode* node3 = BuyNode('C');
BTNode* node4 = BuyNode('D');
BTNode* node5 = BuyNode('E');
BTNode* node6 = BuyNode('F');
node1->_left = node2;
node1->_right = node3;
node2->_left = node4;
node3->_left = node5;
node3->_right = node6;
return node1;
}
4.2二叉树的遍历
学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。
按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：
- 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
- 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
- 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。
由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
//前序遍历
void PreOrder(BTNode* root) {
if (root == NULL) {
printf("NULL ");
return;
}
printf("%c ", root->_data);
PreOrder(root->_left);
PreOrder(root->_right);
}
//中序遍历
void PreOrder(BTNode* root) {
if (root == NULL) {
printf("NULL ");
return;
}
PreOrder(root->_left);
printf("%c ", root->_data);
PreOrder(root->_right);
}
//后序遍历
void PreOrder(BTNode* root) {
if (root == NULL) {
printf("NULL ");
return;
}
PreOrder(root->_left);
PreOrder(root->_right);
printf("%c ", root->_data);
}
示例：
前序遍历结果：1 2 3 4 5 6
中序遍历结果：3 2 1 5 4 6
后序遍历结果：3 1 5 6 4 1
层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。
//层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)
{
QueuePush(&q, root);
}
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
printf("%c ", front->data);
if (front->left)
{
QueuePush(&q, front->left);
}
if (front->right)
{
QueuePush(&q, front->right);
}
}
printf("\n");
QueueDestory(&q);
}
4.3二叉树的实现
二叉树节点个数
//二叉树节点个数
//1.遍历 -- 全局变量
//int size = 0;
//void BinaryTreeSize(BTNode* root)
//{
// if (root == NULL)
// {
// return;
// }
// else
// {
// size++;
// }
// BinaryTreeSize(root->left);
// BinaryTreeSize(root->right);
//
//}
//1.遍历 -- 局部变量，传地址
//void BinaryTreeSize(BTNode* root,int* psize)
//{
// if (root == NULL)
// {
// return;
// }
// else
// {
// (*psize)++;
// }
// BinaryTreeSize(root->left,psize);
// BinaryTreeSize(root->right,psize);
//
//}
//1.遍历 -- 递归(分而治之)
int BinaryTreeSize(BTNode* root)
{
return root == NULL ? 0 : 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
二叉树叶子节点个数
//二叉树叶子节点个数
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层节点个数
//二叉树第k层节点个数
//核心思路：求当前树的第k层 = 左子树的第k-1层 + 右子树的第k-1层。
int BinaryTreeLevelKSize(BTNode* root, int k)
{
if (root == NULL)
return 0;
if (k == 1)
return 1;
return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
二叉树深度/高度
//二叉树深度/高度
int BinaryTreeDepth(BTNode* root)
{
if (root == NULL)
return 0;
int leftDepth = BinaryTreeDepth(root->left);
int rightDepth = BinaryTreeDepth(root->right);
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
二叉树查找值为x的节点
// 二叉树查找值为x的节点
//先判断是不是当前节点，是就返回；不是先去左树找，找到了就返回；左树没找到，再去右树找。
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
{
return NULL;
}
if (root->data == x)
{
return root;
}
BTNode* retleft = BinaryTreeFind(root->left, x);
if (retleft)
{
return retleft;
}
BTNode* retright = BinaryTreeFind(root->right, x);
if (retright)
{
return retright;
}
return NULL;
}
二叉树销毁
// 二叉树销毁
void BinaryTreeDestory(BTNode* root)
{
if (root == NULL)
{
return;
}
BinaryTreeDestory(root->left);
BinaryTreeDestory(root->right);
free(root);
}
判断二叉树是否是完全二叉树
//判断二叉树是否是完全二叉树
//核心思路：层序遍历，把空也入队列；完全二叉树，非空是连续；不是完全二叉树，非空不是连续。
bool BinaryTreeComplete(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)
{
QueueDestory(&q);
return false;
}
}
QueueDestory(&q);
return true;
}
以上就是有关二叉树的相关知识内容，希望对大家有所帮助；后续会给大家更新以一篇有关二叉树方面的习题，来让大家牛刀小试一下。感谢大家支持！加油！