1.树

树是一种非线性的数据结构，是由m(m>0)个有限节点组成的有层次关系的结合，树的结构中，子树之间是不能有交集的否则就是图，树是递归定义的。

常见树的相关术语：

⽗结点：若⼀个结点含有⼦结点，则这个结点称为其⼦结点的⽗结点；

⼦结点：⼀个结点含有的⼦树的根结点称为该结点的⼦结点；

结点的度：⼀个结点有⼏个孩⼦，他的度就是多少；

树的度：⼀棵树中，最⼤的结点的度称为树的度；

叶⼦结点：度为 0的结点称为叶结点；

兄弟结点：具有相同⽗结点的结点互称为兄弟结点

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

树的⾼度或深度：树中结点的最⼤层次；

树的表示方法，对于不规则的普通二叉树通常采用孩子-兄弟表示法(二叉链表)。

struct TreeNode { struct Node* child; // 左边开始的第⼀个孩⼦结点 struct Node* brother; // 指向其右边的下⼀个兄弟结点 int data; // 结点中的数据域 };

2.二叉树_堆

二叉树不存在度大于2的节点，且二叉树有左右之分不能颠倒，因此二叉树又是有序树，何为有序？即一个节点最多有两个分支，这两个分支被严格定义为左指针和右指针，左右不可互换。

如图，这两棵树是完全不同的树，一个是左子树一个是右子树，其内存结构与遍历结果都是不一样，这就是所谓的有序树。一种特殊的二叉树->满二叉树，即每一层的节点个数都达到了最大，假设有k层，则节点总个数为（2的k次方减1）

2.1 完全二叉树

假设二叉树层次为k，除了第k层外，每层节点的个数达到最大节点数，第k层节点数不一定达到最大，这就是完全二叉树。完全二叉树节点的顺序是从左到右，中间不能有空缺，满二叉树是一种特殊的完全二叉树。

在提到完全二叉树的顺序存储，不得不提到堆这种特殊的完全二叉树，简单理解：堆 = 完全二叉树 + 最大、最小堆，而堆通常用顺序结构而不用链式结构。

小堆：堆中的某个节点的值总是不小于其父节点。

大堆：堆中的某个节点的值总是不大于其父节点。

对于堆有以下性质：

另一类是链式结构：即用链表来表示数的结构，一般由三个部分组成：左右指针域，数据域。左指针指向左孩子的链结点的存储地址，右指针指向右孩子的链结点的存储地址，链式结构分为二叉链和三叉链，三叉链比如高阶数据结构的红黑树，这里简单介绍二叉链。

3.堆的实现

堆的底层是用数组实现的，所以固定结构为：

typedef int HPDataType; typedef struct Heap { HPDataType* arr; int size;//有效的数据个数 int capacity;//有效的空间大小 }HP;

将实现堆用到的自定义函数写在头文件中：

//默认初始化堆 void HPInit(HP* php); //堆的销毁 void HPDestroy(HP* php); //堆的插⼊ void HPPush(HP* php, HPDataType x); //堆的删除 HPDataType HPTop(HP* php); // 删除堆顶的数据 void HPPop(HP* php); // 判空 bool HPEmpty(HP* php); //求size int HPSize(HP* php); //向上调整算法 void AdjustUp(HPDataType* a, int child); //向下调整算法 void AdjustDown(HPDataType* a, int n, int parent);

堆的初始化、销毁其实就是对数组的初始化、销毁：

void HPInit(HP*php) { assert(php); php->arr = NULL; php->capacity = php->size = 0; } void HPDestroy(HP* php) { assert(php); if(php->arr); free(php->arr); php->arr = NULL; php->capacity = php->size = 0; }

堆的插入其实就是顺序表的尾插，不过尾插的数据不一定就是比父节点大，所以还需要与前面父节点进行比较，如果插入的数据更小则需要向上进行交换，为此，我们设定一个向上调整算法AdjustUp：

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; } } }

知道孩子节点，找父节点：parent = (child - 1) / 2，如果孩子节点小于父节点则进行交换，交换之后让孩子节点走到父节点，父节点向上继续走到新的父节点，如果发现孩子节点不小于父节点则break停止循环，循环的条件是child>0，不能越界。

其中，向上调整算法时间复杂度O(n∗ log2n)，

证明如下：

第1层， 2^0个结点，需要向上移动0层

第2层， 2^1个结点，需要向上移动1层

第3层， 2^2个结点，需要向上移动2层

第4层， 2^3个结点，需要向上移动3层

......

第h层， 2^h−1个结点，需要向上移动h-1层

则需要移动结点总的移动步数为：每层结点个数 * 向上调整次数（第⼀层调整次数为0）

T(h) = 2^1 ∗ 1 + 2^2 ∗ 2 + 2^3 ∗ 3 + .. + 2^h−2∗ (h− 2) + 2^h−1∗ (h− 1) ①

2 ∗T(h) = 2^2 ∗ 1 + 2^3 ∗ 2 + 2^4 ∗ 3 + .. + 2^h−1∗ (h− 2) + 2^h∗ (h− 1) ②

② ⼀ ① 错位相减：T(h) = −(2^h− 1) + 2^h∗ (h− 1) + 2^0

根据⼆叉树的性质：n= 2h− 1和h=log2(n+ 1)

//堆的插⼊ void HPPush(HP* php, HPDataType x) { assert(php); if (php->capacity == php->size) { int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity; HPDataType* tmp = (HPDataType*)realloc(php->arr,sizeof(HPDataType)*newcapacity); if (tmp == NULL) { perror("realloc fail"); exit(1); } php->arr = tmp; php->capacity = newcapacity; } php->arr[php->size++] = x; AdjustUp(php->arr,php->size-1); }

删除堆数据，删的是堆顶的数据，但如果直接删堆顶的数据，然后让数据整体向前移动一位，那么堆的结构就被破坏了，想重新变成原来小堆的结构就比较困难了，为此，我们先将堆顶数据与size-1位置交换，然后让size--,这虽然没有破坏堆的结构，但此时堆顶数据不一定就是最小，这个时候我们就需要向下调整算法AdjustDown：

void AdjustDown(HPDataType* arr, int n, int parent) { //左孩子 int child = 2 * parent + 1; while (child<n) { if (child + 1 < n && arr[child] > arr[child + 1]) { child++; } if (arr[child] < arr[parent]) { swap(&arr[child], &arr[parent]); parent = child; child = 2 * parent + 1; } else { break; } } }

向下调整需要先找到孩子节点中较小的那个节点，然后向下交换，这样才能保证交换上来的节点最小，后面实现的逻辑与向上调整算法差不多，循环结束的条件是child<n而不是parent<n，因为有时候会有child已经越界了，但parent还没有越界，此时循环还会继续，交换的值是不确定的，取决于此时child的值有没有被覆盖，child+1<n是为了防止没有右孩子的情况。

第1层， 2^0个结点，需要向下移动h-1层

第2层， 2^1个结点，需要向下移动h-2层

第3层， 2^2个结点，需要向下移动h-3层

第4层， 2^3个结点，需要向下移动h-4层

......

取堆顶数据：

HPDataType HPTop(HP* php) { assert(php && php->size); return php->arr[0]; }

判空：

bool HPEmpty(HP* php) { assert(php); return php->size == 0; }

4.链式结构实现二叉树

三种递归方式：

二叉树的链式结构实现是一次递归的暴力美学，而递归的方式主要分为三类：前序遍历(根左右)、中序遍历(左根右)、后序遍历(左右根)。

对于上诉二叉树来说，如果用：

前序遍历：1 2 4 3

中序遍历：4 2 1 3

后序遍历：4 2 3 1

如果用代码实现，如下：

//前序遍历 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 PostOrder(BTNode* root) { if (root == NULL) { return; } PostOrder(root->left); PostOrder(root->right); printf("%d", root->val); }

在了解三种递归方式后，我们来实现一下功能函数：

// ⼆叉树结点个数 int BinaryTreeSize(BTNode* root); // ⼆叉树叶⼦结点个数 int BinaryTreeLeafSize(BTNode* root); // ⼆叉树第k层结点个数 int BinaryTreeLevelKSize(BTNode* root, int k); //⼆叉树的深度/⾼度 int BinaryTreeDepth(BTNode* root); // ⼆叉树查找值为x的结点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x); // ⼆叉树销毁 void BinaryTreeDestory(BTNode** root);

求二叉树节点个数：

int BinaryTreeSize(BTNode* root) { if (root == NULL) { return 0; } return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right); }

递归结束条件为root(当前节点为NULL)，回归执行剩余代码：return 1+0+BinaryTreeSize(root->right)；进入BinaryTreeSize内部，遇到root == NULL，回归返回0，所以1+0+0 = 1，回到上一个函数栈帧继续执下一个代码：return 1+1+BinaryTreeSize，依此类推。

⼆叉树叶⼦结点个数

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) { 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 leftDep = BinaryTreeDepth(root->left); int rightDep = BinaryTreeDepth(root->right); return leftDep > rightDep ? leftDep + 1 : rightDep + 1; }

⼆叉树查找值为x的结点

BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { if (root == NULL) { return 0; } if (root->val == x) { return root; } BTNode* leftfind = BinaryTreeFind(root->left,x); if (leftfind) { return leftfind; } BTNode* rightfind = BinaryTreeFind(root->right, x); if (rightfind) { return rightfind; } return NULL; }

⼆叉树销毁

void BinaryTreeDestory(BTNode** root) { if (*root == NULL) { return; } BinaryTreeDestory(&((*root)->left)); BinaryTreeDestory(&((*root)->right)); free(*root); *root = NULL; }

层序遍历

void Levelorder(BTNode* root) { Queue q; QLInit(&q); QLPush(&q, root); while(!QLEmpty(&q)) { BTNode* front = QLFront(&q); QLPop(&q); printf("%d ", front->val); if (front->left) { QLPush(&q,front->left); } if (front->right) { QLPush(&q, front->right); } } QLDestroy(&q); }

大致思路为:用到队列数据结构，改队列存储的数据类型typedef struct BinaryTreeNode* QLDataType;之前存储int整形，现在改为存储二叉树结点。

将不为空的节点入队列，取队头，删队头保证每一次取出来的都是最新的队头，取一次打印一次，循环结束的条件是队列为NULL。

判断⼆叉树是否是完全⼆叉树

bool BinaryTreeComplete(BTNode* root) { Queue q; QLInit(&q); QLPush(&q, root); while (!QLEmpty(&q)) { BTNode* top = QLFront(&q); QLPop(&q); if (top == NULL) { break; } QLPush(&q, top->left); QLPush(&q, top-> right); } while (!QLEmpty(&q)) { BTNode* top = QLFront(&q); QLPop(&q); if (top != NULL) { QLDestroy(&q); return false; } } QLDestroy(&q); return true; }

大致思路与层序遍历类似，也需要用到队列，不同的是这次我需要将NULL也入队列，当我取队头元素取一次删一次保证每次取到的都是最新的队头，当取到NULL，break跳出来第一次循环，第二次循环只要我取到了非NULL节点，说明该二叉树不是完全二叉树，return false。如果两次循环都结束了，说明该二叉树为完全二叉树，return true。