【数据结构】：二叉树与堆排序的实现

1.树概念及结构(了解) 1.1树的概念

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的有一个特殊的结点，称为根结点，根节点没有前驱结点 除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继 因此，树是递归定义的 节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为6 叶节点或终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I…等节点为叶节点 非终端节点或分支节点：度不为0的节点； 如上图：D、E、F、G…等节点为分支节点 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点 兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点 树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为6 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推； 树的高度或深度：树中节点的最大层次； 如上图：树的高度为4 节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙 森林：由m（m>0）棵互不相交的多颗树的集合称为森林；（数据结构中的学习并查集本质就是一个森林）

1.2树的表示

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，实际中树有很多种表示方式， 如：双亲表示法，孩子表示法、孩子兄弟表示法等等。我们这里就简单的了解其中最常用的孩子 兄弟表示法

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

注意：在Linux中我们能够输入tree指令把我们电脑中的文件以多叉树的形式呈现

2.二叉树概念及结构 2.1概念

一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子 树和右子树的二叉树组成。

二叉树的特点： 每个结点最多有两棵子树，即二叉树不存在度大于2的结点。二叉树的子树有左右之分，其子树的次序不能颠倒。 2.2现实中的二叉树：

2.3数据结构中的二叉树：

2.4特殊的二叉树： 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树 2.5 二叉树的存储结构

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

若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个结点.若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h- 1.对任何一棵二叉树, 如果度为0其叶结点个数为 n0, 度为2的分支结点个数为 n2,则有n0＝n2+1若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=LogN 2.5.1 顺序存储：

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

2.5.2 链式存储：

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，后面课程学到高阶数据结构如红黑树等会用到三叉链

// 二叉链 struct BinaryTreeNode { struct BinTreeNode* pLeft; // 指向当前节点左孩子 struct BinTreeNode* pRight; // 指向当前节点右孩子 BTDataType _data; // 当前节点值域 } // 三叉链 struct BinaryTreeNode { struct BinTreeNode* pParent; // 指向当前节点的双亲 struct BinTreeNode* pLeft; // 指向当前节点左孩子 struct BinTreeNode* pRight; // 指向当前节点右孩子 BTDataType _data; // 当前节点值域 }； 3.二叉树链式结构的实现 3.1二叉树链式结构的遍历

所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问 题。 遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础 前序/中序/后序的递归结构遍历：是根据访问结点操作发生位置命名

NLR：前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前LNR：中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）LRN：后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历 层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的 根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然 后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问 树的结点的过程就是层序遍历 练习：请写出下面的前序/中序/后序/层序遍历 实现推排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种 它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆 遵循最大堆与最小堆的原则 最大堆：每个节点的值都大于或者等于他的左右孩子节点的值 最小堆：每个节点的值都大于或者等于他的左右孩子节点的值

堆排序使用堆来选数，效率就高了很多时间复杂度：O(N*logN)空间复杂度：O(1)稳定性：不稳定 堆排序总的代码的实现 #pragma once #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> typedef int HPDataType; typedef struct Heap { HPDataType* a; HPDataType _size; HPDataType _capacity; }HP; void HeapInit(HP* php); void HeapDestroy(HP* php); void HeapPush(HP* php, HPDataType x); void HeapPop(HP* php); bool HeapEmpty(HP* php); HPDataType HeapTop(HP* php); #include"Heap.h" void HeapInit(HP* php) { assert(php); php->a = NULL; php->_size = 0; php->_capacity = 0; } void HeapDestroy(HP* php) { assert(php); free(php->a); php->a = NULL; php->_size = 0; php->_capacity = 0; } void AdJustUP(HPDataType* a, int child) { int parent = (child - 1) / 2; while (child > 0) { if (a[child] < a[parent]) { Swap(&a[child], &a[parent]);//C语言交换函数可自行尝试解决 child = parent; parent = (parent - 1) / 2; } else { break; } } } void AdjustDown(HPDataType* 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[child] > a[parent]) { Swap(&a[child], &a[parent]); // 继续往下调整 parent = child; child = parent * 2 + 1; } else { break; } } } void HeapPush(HP* php, HPDataType x) { assert(php); if (php->_capacity == php->_size) { int NewCapacity = php->_capacity = 0 ? 4 : php->_capacity * 2; HPDataType* temp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * NewCapacity); if (temp == NULL) { perror("realloc fail"); exit(-1); } php->a = temp; php->_capacity = NewCapacity; } php->a[php->_size] = x; php->_size++; AdJustUP(php->a, php->_size - 1); } void HeapPop(HP* php) { assert(php); assert(php->_size > 0); Swap(&php->a[0], &php->a[php->_size - 1]); --php->_size; AdjustDown(php->a, php->_size, 0); } HPDataType HeapTop(HP* php) { assert(php); assert(php->_size > 0); return php->a[0]; } bool HeapEmpty(HP* php) { assert(php); return php->_size == 0; }

这里涉及一些数学知识 稍微想一下就能够理解各位老铁 等差数列和等比数列的知识

实现二叉树 #include<stdio.h> #include<stdlib.h> // 不是增删查改，学习二叉树结构 typedef struct BinaryTreeNode { struct BinaryTreeNode* left; struct BinaryTreeNode* right; int val; }BTNode; BTNode* BuyNode(int x) { BTNode* node = (BTNode*)malloc(sizeof(BTNode)); if (node == NULL) { perror("malloc fail"); exit(-1); } node->val = x; node->left = NULL; node->right = NULL; return node; } void PrevOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } printf("%d ", root->val); PrevOrder(root->left); PrevOrder(root->right); } void InOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } InOrder(root->left); printf("%d ", root->val); InOrder(root->right); } void PostOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } PostOrder(root->left); PostOrder(root->right); printf("%d ", root->val); } // 节点个数 //int TreeSize(BTNode* root) //{ // static int size = 0; // if (root == NULL) // return 0; // else // ++size; // // TreeSize(root->left); // TreeSize(root->right); // // return size; //} //int size = 0; //int TreeSize(BTNode* root) //{ // if (root == NULL) // return 0; // else // ++size; // // TreeSize(root->left); // TreeSize(root->right); // // return size; //} int TreeSize(BTNode* root) { return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1; } // 叶子节点个数 int TreeLeafSize(BTNode* root) { if (root == NULL) return 0; if (root->left == NULL && root->right == NULL) { return 1; } return TreeLeafSize(root->left) + TreeLeafSize(root->right); } // 第k层的节点个数 int TreeKLevel(BTNode* root, int k) { assert(k > 0); if (root == NULL) return 0; if (k == 1) { return 1; } return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1); } int main() { // 手动构建 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; PrevOrder(node1); printf("\n"); InOrder(node1); printf("\n"); PostOrder(node1); printf("\n"); printf("%d\n", TreeSize(node1)); //size = 0; printf("%d\n", TreeSize(node1)); return 0; }

二叉树的本质是递归 这里二叉树的遍历又分为前中后序遍历 前面的图片已经给大家呈现出来了 下面给大家画一个二叉树前序遍历的递归展开图 中后序递归展开图大家可以下去自己画图试一试

总的代码实现如下 #include<stdio.h> #include<stdlib.h> // 不是增删查改，学习二叉树结构 typedef struct BinaryTreeNode { struct BinaryTreeNode* left; struct BinaryTreeNode* right; int val; }BTNode; BTNode* BuyNode(int x) { BTNode* node = (BTNode*)malloc(sizeof(BTNode)); if (node == NULL) { perror("malloc fail"); exit(-1); } node->val = x; node->left = NULL; node->right = NULL; return node; } void PrevOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } printf("%d ", root->val); PrevOrder(root->left); PrevOrder(root->right); } void InOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } InOrder(root->left); printf("%d ", root->val); InOrder(root->right); } void PostOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } PostOrder(root->left); PostOrder(root->right); printf("%d ", root->val); } // 节点个数 //int TreeSize(BTNode* root) //{ // static int size = 0; // if (root == NULL) // return 0; // else // ++size; // // TreeSize(root->left); // TreeSize(root->right); // // return size; //} //int size = 0; //int TreeSize(BTNode* root) //{ // if (root == NULL) // return 0; // else // ++size; // // TreeSize(root->left); // TreeSize(root->right); // // return size; //} int TreeSize(BTNode* root) { return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1; } // 叶子节点个数 int TreeLeafSize(BTNode* root) { if (root == NULL) return 0; if (root->left == NULL && root->right == NULL) { return 1; } return TreeLeafSize(root->left) + TreeLeafSize(root->right); } // 第k层的节点个数 int TreeKLevel(BTNode* root, int k) { assert(k > 0); if (root == NULL) return 0; if (k == 1) { return 1; } return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1); } int main() { // 手动构建 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; PrevOrder(node1); printf("\n"); InOrder(node1); printf("\n"); PostOrder(node1); printf("\n"); printf("%d\n", TreeSize(node1)); //size = 0; printf("%d\n", TreeSize(node1)); return 0; } #pragma once #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> typedef int HPDataType; typedef struct Heap { HPDataType* a; HPDataType _size; HPDataType _capacity; }HP; void HeapInit(HP* php); void HeapDestroy(HP* php); void HeapPush(HP* php, HPDataType x); void HeapPop(HP* php); bool HeapEmpty(HP* php); HPDataType HeapTop(HP* php); #include"Heap.h" void HeapInit(HP* php) { assert(php); php->a = NULL; php->_size = 0; php->_capacity = 0; } void HeapDestroy(HP* php) { assert(php); free(php->a); php->a = NULL; php->_size = 0; php->_capacity = 0; } void AdJustUP(HPDataType* a, int child) { int parent = (child - 1) / 2; while (child > 0) { if (a[child] < a[parent]) { Swap(&a[child], &a[parent]);//C语言交换函数可自行尝试解决 child = parent; parent = (parent - 1) / 2; } else { break; } } } void AdjustDown(HPDataType* 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[child] > a[parent]) { Swap(&a[child], &a[parent]); // 继续往下调整 parent = child; child = parent * 2 + 1; } else { break; } } } void HeapPush(HP* php, HPDataType x) { assert(php); if (php->_capacity == php->_size) { int NewCapacity = php->_capacity = 0 ? 4 : php->_capacity * 2; HPDataType* temp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * NewCapacity); if (temp == NULL) { perror("realloc fail"); exit(-1); } php->a = temp; php->_capacity = NewCapacity; } php->a[php->_size] = x; php->_size++; AdJustUP(php->a, php->_size - 1); } void HeapPop(HP* php) { assert(php); assert(php->_size > 0); Swap(&php->a[0], &php->a[php->_size - 1]); --php->_size; AdjustDown(php->a, php->_size, 0); } HPDataType HeapTop(HP* php) { assert(php); assert(php->_size > 0); return php->a[0]; } bool HeapEmpty(HP* php) { assert(php); return php->_size == 0; }