数据结构之四：堆和二叉树

堆的实现:SData/Heap/heap.c · Hera_Yc/bit_C_学习 - 码云 - 开源中国

树

树的概念

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

把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

• 有一个特殊的结点，称为根结点，根节点没有前驱结点。
• 除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i<= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继
• 因此，树是递归定义的。

树形结构中，子树之间不能有交集，否则就不是树形结构。

（树中不能构成回路，不能有孤立的点）。

如何理解树是递归定义的呢？

相关概念

 树的结构定义

链式表示：

 数组表示：

 二叉树

二叉树概念

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

1. 或者为空。
2.  由一个根节点加上两棵别称为左子树和右子树的二叉树组成。
3. 二叉树不存在度大于2的结点。
4. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树。

特殊的二叉树

•  满二叉树：一个二叉树，如果每一个层的结点数都达到最大值（2），则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K。那么，结点总数是(2^K - 1)，则它就是满二叉树。
• 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。满二叉树是一种特殊的完全二叉树。（假设有k层的完全二叉树，前k-1层都是满的，最后一层可以不满，但必须是从左到右连续）。

 二叉树性质

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

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

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

即：度为0（叶子结点）的数量 = 度为2的结点数量 + 1 。

3.在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）
A n
B n+1
C n-1
D n/2

解析：假设叶子结点右x个，则度为2的结点右x-1个

总节点数  =  x   +   (x  - 1)  +  度为1的结点数量

所以：总数量= 2*n =x+(x-1)+1   = > x=n

4.二叉树的高度：（用于堆的选树、搜索二叉树、平衡搜索二叉树）

 二叉树存储

二叉树的逻辑结构是一棵树，物理结构分为顺序存储和链式存储两种结构。

数组实现：

 ------------------------------------------------二叉树实现在文章末尾 ------------------------------------------------ 

堆

堆：实际上就是数组形式存储的完全二叉树。(逻辑结构是完全二叉树，物理结构是数组)

堆的作用：堆排序效率高、选数等

向下调整算法

(向下调整算法是堆中最重要的算法，堆、堆排序等都需要调整算法来支撑。

向下调整算法构建堆：

前提是：根节点的左右字数必须是大堆或者小堆。

//向下调整算法 
//左右子树必须保证：都是小堆（或者大堆）
static void AdjustDown(HPDataType* a, int n, int root)
{int parent = root;int child = parent * 2 + 1;//默认是左孩子更小while (child<n){//找出左右孩子中小的一个if (child+1<n && a[child + 1] < a[child]){++child;}//如果孩子小于父亲则交换if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent*2+1;}else{break;}}
}

 数组建堆

向下调整算法用于建堆

//arr是传入的数据 arr[n]
void HeapInit(Heap* php, HPDataType* arr, int n)
{assert(php);php->_a = (HPDataType*)malloc(sizeof(HPDataType) * n);if (php->_a == NULL){printf("%s\n", strerror(errno));return;}memcpy(php->_a, arr, sizeof(HPDataType) * n);//内存拷贝php->_size = n;php->_capacity = n;//数组建堆//利用的向下调整算法:// 从最下面的第一个非叶子结点开始调整,// 一层层完成小堆的构建//直到根节点,在对根节点向下调整int i = 0;for (i=(php->_size-1);i >= 0; i--){AdjustDown(php->_a, php->_size, i);}//
}

 向上调整算法

向上调整算法用于入堆。

     向上调整算法与向下调整类似，不过是从子节点往父节点走。对于堆而言，父节点和子节点的下标关系是必须掌握的。

void AdjustUp(HPDataType* arr,int n,int child)
{//从子节点往父结点调整//由child得出parentint 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;}}
}

堆排序：见排序与查找-CSDN博客。

入堆

void HeapPush(Heap* php, HPDataType x)
{assert(php);if (php->_size == php->_capacity){php->_capacity *= 2;HPDataType* tmp = (HPDataType*)realloc(php->_a,sizeof(HPDataType) * (php->_size));if (tmp == NULL){printf("%s\n", strerror(errno));return;}php->_a = tmp;}php->_a[php->_size++] = x;AdjustUp(php->_a, php->_size, php->_size-1);}

与堆有关的OJ题:面试题 17.14. 最小K个数 - 力扣（LeetCode）（典型的TopK问题）

N个树中找出最大或最小的前K个数？

• 排序  问题：a、N*logN的效率能否进一步提高？  b、假设N非常大，内存不够排序
• 建一个大小为K的堆来解决问题，

eg：找最大的前K个，建一个大小为K的小堆，比堆顶大则进堆(顶替掉堆顶的数据,然后向下调整)。

• 大堆性质：堆顶的元素一定是最大的。（找最小的K个数）。
• 小堆性质：堆顶的元素一定是最小的。（找最大的K个数）。

解法一在：leetcode/TopK/test_1.c · Hera_Yc/bit_C_学习 - 码云 - 开源中国 

//建K大小的堆解法
void Swap(int* x, int* y) {int tmp = *x;*x = *y;*y = tmp;
}void AdjustDown(int* arr, int n, int root) {int parent = root;int child = parent * 2 + 1;while (child < n) // child不越界{if (child + 1 < n && arr[child + 1] > arr[child]) // 大堆找更大的孩子{child++;}if (arr[child] > arr[parent]) // 大堆的父节点更大{Swap(&arr[child], &arr[parent]);parent = child;child = 2 * parent + 1; // 向下迭代} else {break;}}
}int* smallestK(int* arr, int arrSize, int k, int* returnSize) {*returnSize = k;if (k == 0)return NULL;int* retArr = (int*)malloc(sizeof(int) * k);*returnSize = k;int i = 0;// 建K个数的大堆：for (i = 0; i < k; i++) {retArr[i] = arr[i];}for (i = (k - 1 - 1) / 2; i >= 0; i--) {AdjustDown(retArr, k, i);} // 大堆建立完成：K个数的大堆int j = 0;for (j = k; j < arrSize; j++) {if (arr[j] < retArr[0]) {retArr[0] = arr[j];AdjustDown(retArr, k, 0);}}return retArr;
}

 ------------------------------------------------堆到此结束 ------------------------------------------------

二叉树

伪树

        在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。由于现在对二叉树结构掌握还不够深入，为了降低学习成本，此处手动快速创建一棵简单的二叉树，快速进入二叉树操作学习，等二叉树结构了解的差不多时，我们反过头再来研究二叉树真正的创建方式。

BTNode* BuyNode(BTDataType ch)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));node->_data = ch;node->_left = NULL;node->_right = NULL;return node;
}
//一个树的增删查改没有意义
//这里写一颗伪树
BTNode* A = BuyNode('A');
BTNode* B = BuyNode('B');
BTNode* C = BuyNode('C');
BTNode* D = BuyNode('D');
BTNode* E = BuyNode('E');
BTNode* f = BuyNode('f');
A->_left = B;
A->_right = C;
B->_left = D;
B->_right = E;
D->_left = f;

（学习二叉树的目的是为了掌握更加深层的数据结构，因此会边学边补充）

任何一个二叉树，都要看作三个部分：

1、根节点。2、左子树。3、右子树。

遍历 

• 深度优先遍历：先往深处走，无路可走是退回来 访问其他结点。（递归和栈实现）。
• 广度优先遍历：一层层的走，走完一层走下一层。（队列实现）。

树不同于其他的数据结构：

1. 简单的树的增删查改没有意义。
2. 单独的二叉树没有意义。
3. 平衡二叉树和搜索二叉树才有实际意义。

深度优先遍历 

// 二叉树前序遍历
void PreOrder(BTNode* root);
// 二叉树中序遍历
void InOrder(BTNode* root);
// 二叉树后序遍历
void PostOrder(BTNode* root);

typedef char BTDataType;
typedef struct BinaryTree
{BTDataType _data;struct BinaryTree* _left;struct BinaryTree* _right;
}BTNode;
//前序
void PreOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}printf("%c ", root->_data); //根PreOrder(root->_left);		//左子树PreOrder(root->_right);		//右子树
}
int TreeSize(BTNode* root)
{if (root == NULL)return 0;elsereturn 1 + TreeSize(root->_left) + TreeSize(root->_right);
}

关于TreeSize如何返回值？

广度优先遍历 

广度优先遍历：即层序遍历，与递归无关，通过队列的性质（先进先出）来实现。

 结点个数

// 二叉树节点个数
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;elsereturn 1 + TreeSize(root->_left) + TreeSize(root->_right);
}
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL){return 0;}else if(root->_left == NULL && root->_right == NULL){return 1;}else{return TreeLeafSize(root->_left) + TreeLeafSize(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);
}

 查找

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL)return NULL;if (root->_data == x)return root;BTNode* node = BinaryTreeFind(root->_left, x);if (node)return node;node = BinaryTreeFind(root->_right, x);if (node)return node;return NULL;
}

销毁

// 二叉树销毁
void BinaryTreeDestory(BTNode* root);
// 二叉树销毁
void BinaryTreeDestory(BTNode* root)
{if (root == NULL)return;BinaryTreeDestory(root->_left);BinaryTreeDestory(root->_right);free((root));//后序free不需要保存左和右root = NULL;
}

判断一棵树是否是完全二叉树

// 判断二叉树是否是完全二叉树
//是返回1，不是返回0
int BinaryTreeComplete(BTNode* root)
{//完全二叉树的层序遍历是两段：非空结点+空节点Queue q;QueueInit(&q);if (root == NULL)return 0;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 0;}}QueueDestory(&q);return 1;
}

------------------------------------------本文二叉树到此结束-----------------------------------------------

到这里，二叉树的学习进程仅有40%左右，其余待补充.....