数据结构初级—— 二叉树初讲

一、树的概念和结构树是一种非线性的数据结构它是由n(n0)个有限的节点组成的一个具有关系层次的集合。把它叫做树是因为它看起来像一颗倒挂的树其根是朝上的叶子朝下。有⼀个特殊的结点称为根结点根结点没有前驱结点。除根结点外其余结点被分成 M(M0) 个互不相交的集合 T1、T2、……、Tm 其中每一个集合 Ti(1 i m) ⼜是⼀棵结构与树类似的子树。每棵子树的根结点有且只有⼀个前驱可以有 0 个或多个后继。因此树是递归定义的。二、相关树的一些定义父结点/双亲结点若一个结点含有子结点则这个结点称为其子结点的父结点 如上图A是B的父结点子结点/孩子结点一个结点含有的子树的根结点称为该结点的子结点 如上图B是A的孩子结点结点的度一个结点有几个孩子他的度就是多少比如A的度为6F的度为2K的度为0树的度⼀棵树中最大的结点的度称为树的度 如上图树的度为 6叶子结点/终端结点度为 0 的结点称为叶结点 如上图 B、C、H、I... 等结点为叶结点分支结点/非终端结点度不为 0 的结点 如上图 D、E、F、G... 等结点为分支结点兄弟结点具有相同父结点的结点互称为兄弟结点(亲兄弟) 如上图 B、C 是兄弟结点结点的层次从根开始定义起根为第 1 层根的子结点为第 2 层以此类推树的高度或深度树中结点的最大层次 如上图树的高度为 4结点的祖先从根到该结点所经分支上的所有结点如上图 A 是所有结点的祖先路径一条从树中任意节点出发沿父节点-子节点连接达到任意节点的序列比如A到Q的路径为A-E-J-QH到Q的路径H-D-A-E-J-Q子孙以某结点为根的子树中任一结点都称为该结点的子孙。如上图所有结点都是A的子孙森林由 mm0 棵互不相交的树的集合称为森林三、树的表示以及运用场景树的表示:树的结构相对来说比较复杂存储起来也很麻烦我们用什么办法来表示呢树的应用树的应用场景很多比如文件夹套文件夹就是一棵树每个文件夹是节点子文件夹是子节点四、二叉树的概念与结构在树形结构中如果我们直接使用太过复杂我们比较常用的一般是二叉树一颗二叉树是结点的一个有效集合该集合由一个根结点加上两颗分别称为左子树和右子树的二叉树组成或者为空。每个节点最多只有 2 个孩子只能是0 个、1 个、2 个不能更多。两个孩子分别叫左孩子、右孩子。子树有左右之分顺序不能乱左子树和右子树是不一样的交换一下就是两棵不同的树。第 i 层最多有 2^(i−1) 个节点比如第 1 层最多 1 个第 2 层最多 2 个第 3 层最多 4 个……深度为 k 的二叉树最多有 2^k − 1 个节点这种每一层都满的叫满二叉树。五、特殊的二叉树满二叉树一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉树也就是说如果一个二叉树层次为k,其结点总数就是2^k-1则它就是满二叉树完全二叉树完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为k的有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。注意满二叉树是一种特殊的完全二叉树。二叉树的性质满二叉树性质若规定根结点的层数为 1 则⼀棵非空二叉树的第i层上最多有 2 ^(i−1) 个结点若规定根结点的层数为 1 则深度为 h 的二叉树的最大结点数是 2 ^h − 1若规定根结点的层数为 1 具有 n 个结点的满二叉树的深度 h log(n 1) ( log以2为底 n1 为对数)完全二叉树最后一层结点个数2^(i-1)六、二叉树存储结构二叉树一般可以使用两种结构存储一种是顺序结构一种是链式结构顺序结构顺序结构存储就是使用数组来存储一般使用数组只适合表示完全二叉树因为不是完全二叉树会有空间的浪费完全二叉树更适合使用顺序结构存储链式结构二叉树的链式存储结构是指用链表来表示一棵二叉树即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链当前我们学习中一般都是二叉链。后面课程学到高阶数据结构如红黑树等会用到三叉树。七、堆的概念与结构如果有一个关键码的集合K{}把它所有的元素按照完全二叉树的顺序存储方式存储这里堆的底层实现其实也就是一个数组。我们堆分为小堆和大堆。我们将根结点最大的堆叫做最大堆或大根堆根结点最小的堆叫做最小堆或者小根堆。堆具有一下性质堆中某个结点的值总是不大于或者不小于其父结点的值堆总是一颗完全二叉树堆顶是最值(最大值或最小值)堆的建立typedef int HPDataType; typedef struct Heap { HPDataType* arr; int size; int capacity; }HP;堆的初始化和检查// 初始化堆 void HeapInit(HP* php) { php-arr (HPDataType*)malloc(sizeof(HPDataType) * 4); php-size 0; php-capacity 4; } // 检查并扩容 void HeapCheckCapacity(HP* php) { if (php-size php-capacity) { HPDataType* tmp (HPDataType*)realloc(php-arr, php-capacity * 2 * sizeof(HPDataType)); if (tmp) { php-arr tmp; php-capacity * 2; } } }堆的销毁if (php-arr ! NULL) { free(php-arr); php-arr NULL; }八、堆的插入数据包含向上调整算法的实现我们实现堆的插入大致思路都跟顺序表一样但是在尾部插入一个数据后原来的堆就改变了我们需要把插入的数据调整到对应的位置上我们先来看个图片吧(以大堆为例)如果child小于parent就进行交换所以这里是小堆void HPPop(HP* php) { assert(!HPEmpty(php)); Swap(php-arr[0], php-arr[php-size-1]); --php-size; AdjustDown(php-arr, 0, php-size); }判断不为空将堆顶数据与最后一个数据进行交换size--就删除了堆顶数据然后进行向下调整九、堆排序的实现建堆就是把一个普通数组调成大根堆 / 小根堆只用向下调整实现最简单。堆用数组存下标从 0 开始从最后一个非叶子节点开始往前遍历每个节点都做一次向下调整遍历完整个数组就是堆了。// 向下调整大根堆 void AdjustDown(int heap[], int size, int parent) { int child 2 * parent 1; while (child size) { // 找较大的孩子 if (child 1 size heap[child1] heap[child]) child; if (heap[parent] heap[child]) break; // 交换 int temp heap[parent]; heap[parent] heap[child]; heap[child] temp; parent child; child 2 * parent 1; } } // 建堆 void BuildHeap(int heap[], int n) { // 从最后一个非叶子节点开始 for (int i (n-2)/2; i 0; i--) { AdjustDown(heap, n, i); } }这段代码整体实现了堆排序核心分为三步AdjustDown向下调整从某个父节点开始和左右孩子比较把较大的值往上交换让父节点沉到合适位置保证局部满足大根堆规则。BuildHeap建堆从最后一个非叶子节点向前遍历对每个节点执行向下调整把无序数组整体调整为大根堆。HeapSort排序先建好堆再不断将堆顶最大值与末尾元素交换缩小堆范围后重新调整堆顶重复操作最终得到升序有序数组。总结综上所述树是一种层次分明的非线性数据结构而二叉树作为其中最常用的形式结构简洁、性质清晰便于存储和操作。从链式表示到顺序存储从普通二叉树到满二叉树、完全二叉树再到以完全二叉树为基础的堆结构层层递进构成了完整的知识体系。堆通过向上、向下调整实现高效插入与排序堆排序更是利用建堆与调整完成了高效的数据排序。掌握树与二叉树的基本概念、结构特点及堆的相关操作不仅能理解各类层次化数据的组织方式也为后续更复杂的数据结构与算法打下了重要基础。