网站开发人员职能,河南天丰建设工程有限公司网站,红酒网站模板,必应搜索引擎入口目录
编辑
1.树概念及结构
2. 树的表示 3.二叉树概念及结构
特殊的二叉树 二叉树的性质
编辑
二叉树选择题
二叉树的存储结构
4.堆的概念及结构 父亲孩子下标关系编辑 堆的实现接口
堆结构体设计堆的初始化堆的销毁
堆的插入(附#xff1a;向上调整算法)
堆…目录
编辑
1.树概念及结构
2. 树的表示 3.二叉树概念及结构
特殊的二叉树 二叉树的性质
编辑
二叉树选择题
二叉树的存储结构
4.堆的概念及结构 父亲孩子下标关系编辑 堆的实现接口
堆结构体设计堆的初始化堆的销毁
堆的插入(附向上调整算法)
堆的删除
取堆顶数据堆的大小堆的判空 万物皆有裂痕,那是光照进来的地方 1.树概念及结构 树是一种非线性的数据结构它是由nn0个有限结点组成一个具有层次关系的集合。把它叫做树是因 为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。 因此树是递归定义的。 节点的度一个节点含有的子树的个数称为该节点的度 如上图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的子孙 森林由mm0棵互不相交的树的集合称为森林 2. 树的表示 介绍最常用的一种孩子兄弟表示法。 结点指向左孩子孩子再指向自己的兄弟 typedef int DataType;
struct Node
{struct Node* _firstChild1; // 第一个孩子结点struct Node* _pNextBrother; // 指向其下一个兄弟结点DataType _data; // 结点中的数据域
}; 3.二叉树概念及结构 一棵二叉树是结点的一个有限集合该集合 : 1. 或者为空 2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成 1. 二叉树不存在度大于2的结点 2. 二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树 只有一个孩子和没有孩子也可以称为二叉树
特殊的二叉树
满二叉树和完全二叉树 1. 满二叉树一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉树。
每一层都是满的 2. 完全二叉树完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为K 的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对 应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。 前h-1层都是满的最后一层可以不满从左到右是连续的 二叉树的性质 二叉树选择题 1. 某二叉树共有 399 个结点其中有 199 个度为 2 的结点则该二叉树中的叶子结点数为 A 不存在这样的二叉树 B 200 C 198 D 199 由性质可知n0 n21. n0 1991 200 2.在具有 2n 个结点的完全二叉树中叶子结点个数为 A n B n1 C n-1 D n/2 首先分析题干如何求叶子节点的个数和节点个数相关的公式有二 n0 n2 1N n0 n1 n2 已知总个数N为2n那么只要知道n1即可求出n0. 这里有一个重要的结论 在完全二叉树中如果节点总个数为奇数则没有度为1的节点如果节点总个数为偶数只有一个度为1的节点。 2n为偶数因此有一个度为1的节点。 2n n0 1 n2 n0 1 n0 - 1 2n 2n0 n0 n故选A 3.一个具有767个节点的完全二叉树其叶子节点个数为 A 383 B 384 C 385 D 386 本题同上。此时共有奇数个节点因此没有度为1的节点即n1 0. 由 N n0 n1 n2得 767 n0 0 n0 - 1 n0 768/2 384 4.一棵完全二叉树的节点数位为531个那么这棵树的高度为 A 11 B 10 C 8 D 12 把h带进去10在这个范围里面所以选B
二叉树的存储结构 二叉树一般可以使用两种结构存储一种顺序结构一种链式结构。 1. 顺序存储 顺序结构存储就是使用数组来存储一般使用数组只适合表示 完全二叉树 因为不是完全二叉树会有空 间的浪费。而现实中使用 中只有堆才会使用数组来存储 。二叉树顺序存储在 物理上是一个数组在逻辑上是一颗二叉树。 2. 链式存储 二叉树的链式存储结构是指用链表来表示一棵二叉树即用链来指示元素的逻辑关系。 通常的方法是 链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所 在的链结点的存储地址 。链式结构又分为二叉链和三叉链当前我们学习中一般都是二叉链。 typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{struct BinTreeNode* _pLeft; // 指向当前节点左孩子struct BinTreeNode* _pRight; // 指向当前节点右孩子BTDataType _data; // 当前节点值域
} 4.堆的概念及结构 父亲孩子下标关系 堆的实现接口
堆结构体设计堆的初始化堆的销毁
typedef int HPDateType;
typedef struct Heap
{HPDateType* a;int size;int capacity;
}HP;
void HeapInit(HP* php)
{php-size 0;php-capacity 0;php-a NULL;}
void HeapDestory(HP* php)
{free(php-a);php-a NULL;php-size php-capacity 0;}堆的插入(附向上调整算法) void HeapPush(HP* php, HPDateType x){//插入进行扩容assert(php);if (php-size php-capacity){int newcapacity php-capacity 0 ? 4 : php-capacity * 2;HPDateType* tmp (HPDateType*)realloc(php-a,sizeof(HPDateType)*newcapacity);if (tmp NULL){//判断一下是否开辟失败printf(realloc fail\n);exit(-1); //结束程序}php-a tmp;php-capacity newcapacity;}php-a[php-size] x;php-size;//向上调整从刚刚插入孩子的位置Adjustdown(php-a, php-size - 1);
}
向上调整算法
//小堆
void Adjustdown(HPDateType*a, int child)
{int parent (child - 1) / 2;while (child0){if (a[child] a[parent]){HPDateType* tmp a[child];a[child] a[parent];a[parent] tmp;child parent;parent (child - 1) / 2;}else {break;}}}
孩子调整的结束条件是到根结点跟结点的下标是0所以大于0就一直调整
堆的删除 void HeapPop(HP* php)
{assert(php);//堆顶和最后一个数据互换Swap(php-a[0], php-a[php-size - 1]);php-size--;//从堆顶开始调整堆顶是下标是0AdjustDown(php-a, php-size, 0);
}
向下调整
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;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}} 插入删除的时间复杂度都是o(logN
取堆顶数据堆的大小堆的判空
HPDataType HeapTop(HP* php)
{assert(php);assert(php-size 0);return php-a[0];
}
int HeapSize(HP* php)
{assert(php);return php-size;
}
bool HeapEmpty(HP* php)
{assert(php);return php-size 0;}测试接口
#includeHeap.hint main()
{HP hp;HeapInit(hp);int a[] { 65, 100, 70, 32, 50, 60 };for (int i 0; i sizeof(a) / sizeof(int); i){HeapPush(hp, a[i]);}return 0;}
大堆的实现把 符号改成符号即可。
5.堆的应用
1.堆排序 1. 建堆 升序建大堆 降序建小堆 2. 利用堆删除思想来进行排序 建堆 时间复杂度为oN void HeapSort(int* a, int n)
{for (int i (n - 1 - 1) / 2; i 0; --i){AdjustDown(a, n, i);}for (int end n - 1; end 0; --end){Swap(a[end], a[0]);AdjustDown(a, end, 0);}
}
int main()
{int a[] { 70, 56, 30, 25, 15, 10, 75, 33, 50, 69 };HeapSort(a, sizeof(a) / sizeof(a[0]));for (int i 0; i sizeof(a) / sizeof(a[0]); i){printf(%d , a[i]);}printf(\n);return 0;
}时间复杂度
堆排序N*logN
冒泡排序 N*2
2.TOP-K问题
