高安建站公司,济宁哪里做网站最便宜,珠海seo,网站美工建设意见文章目录 1.树1.1概念1.2相关定义1.3 表示#xff08;左孩子右兄弟#xff09; 2.二叉树2.1概念2.2特殊的二叉树1. 满二叉树#xff1a;2. 完全二叉树#xff1a; 2.3二叉树的性质2.4练习 3.二叉树的存储结构1. 顺序存储2. 链式存储 4.完全二叉树的代码实现4.1堆的介绍1.堆… 文章目录 1.树1.1概念1.2相关定义1.3 表示左孩子右兄弟 2.二叉树2.1概念2.2特殊的二叉树1. 满二叉树2. 完全二叉树 2.3二叉树的性质2.4练习 3.二叉树的存储结构1. 顺序存储2. 链式存储 4.完全二叉树的代码实现4.1堆的介绍1.堆的性质2.堆的应用 4.2堆的实现1.Heap.h2.Heap.c3.test.c 4.3堆的应用1.堆排序1.1建堆时间复杂度最优为下调N1.1.1下调O(N)1.1.2 上调O(NlogN) 1.2代码实现1.3堆排序时间复杂度 2.topk问题2.1介绍及解决方式2.2代码举例 5.普通二叉树的结构5.1代码实现5.2算法图解(递归) 1.树
1.1概念
树是一种非线性的数据结构它是由nn0个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。
有一个特殊的结点称为根结点根节点没有前驱结点除根节点外其余结点被分成M(M0)个互不相交的集合T1、T2、……、Tm其中每一个集合Ti(1 i m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱可以有0个或多个后继树是递归定义的。树形结构中子树之间不能有交集否则就不是树形结构
1.2相关定义 节点的度一个节点含有的子树的个数称为该节点的度 如上图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棵互不相交的树的集合称为森林
1.3 表示左孩子右兄弟 2.二叉树 2.1概念
一棵二叉树是结点的一个有限集合该集合:
可以为空由一个根节点加上两棵称为左子树和右子树的二叉树组成二叉树不存在度大于2的结点二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树
2.2特殊的二叉树 1. 满二叉树
每一个层的结点数都达到了最大值的二叉树。 如果一个二叉树的层数为K且结点总数是 2^k-1 则它就是满二叉树。
2. 完全二叉树
完全二叉树是效率很高的数据结构完全二叉树是由满二叉树引出来的。 对于深度为K结点为n的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对 应时称之为完全二叉树。 前k-1层是满二叉树 第k层不满且从左到右连续 若第k层也满 则为满二叉树 满二叉树是一种特殊的完全二叉树。
2.3二叉树的性质
若规定根节点的层数为1
一棵非空二叉树的第i层上最多有 2^i - 1 个结点深度为k的二叉树的最大结点数即满二叉树是 2^k - 1对任何一棵二叉树, 度为0的叶结点个数为x0 , 度为2的分支结点个数为 x2,则x0 x21度为0的永远比度为2的多1个具有n个结点的满二叉树的深度hlog2n1对于具有n个结点的完全二叉树如果按照从上至下从左至右的数组顺序对所有节点从0开始编号则对 于序号为i的结点有 i0i为根节点编号无双亲节点 i0i的父节点(i-1)/2 2i1n左孩子序号2i12i1n无左孩子 2i2n右孩子序号2i22i2n无右孩子 高度为h的完全二叉树的结点个数区间【2^(h-1) 2^h-1】
2.4练习
1. 某二叉树共有 399 个结点其中有 199 个度为 2 的结点则该二叉树中的叶子结点数为 200
A 不存在这样的二叉树
B 200
C 198
D 199
x0 x21
2.下列数据结构中不适合采用顺序存储结构的是 A
A 非完全二叉树
B 堆
C 队列
D 栈
3.在具有 2n 个结点的完全二叉树中叶子结点个数(即x0)为 A
A n
B n1
C n-1
D n/2
完全二叉树前k-1层是满二叉树 ; 第k层不满且从左到右连续
2n x0 x1 x2
2n x0 x1 x0 - 1
2n 2x0 x1 - 1
x1为0/1 2n为整数 x1只能为1 》x0 n
4.一棵完全二叉树的节点数为531个那么这棵树的高度为 B
A 11
B 10
C 8
D 12
法一如果是满二叉树 h 256 512 10242^ 8 9 10
法二利用结论【2^(h-1) 2^h-1】
5.一个具有767个节点的完全二叉树其叶子节点个数为 B
A 383
B 384
C 385
D 386
完全二叉树前k-1层是满二叉树 ; 第k层不满且从左到右连续
767 x0 x1 x2
767 x0 x1 x0 - 1
767 2x0 x1 - 1
x1为0/1 767为奇数 x1只能为0 》x0 3843.二叉树的存储结构
1. 顺序存储
顺序结构存储就是使用数组来存储一般使用数组只适合表示完全二叉树不是完全二叉树会有空 间浪费。二叉树顺序存储在物理上是一个数组在逻辑上是一颗二叉树。通常把堆(一种二叉树)用顺序结构的数组来存储这里的堆是数据结构操作系统虚拟进程地址空间中的堆是管理内存的一块区域分段。
2. 链式存储
链式存储结构是用链表来表示一棵二叉树即用链表来指示元素的逻辑关系。 链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在链结点的存储地址 。链式结构分为二叉链和三叉链。
4.完全二叉树的代码实现
4.1堆的介绍
如果有一个关键码的集合K { … }把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中并满足 且 ( 且 ) i 01 2…则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆根节点最小的堆叫做最小堆或小根堆。
1.堆的性质
堆中某个节点的值总是 或 其父节点的值小根堆子节点值父亲大根堆子节点值父亲堆总是一棵完全二叉树。
2.堆的应用
1.堆排序 – ON * logN 2.topk问题
4.2堆的实现
1.Heap.h
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.htypedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;//交换
void Swap(HPDataType* p1, HPDataType* p2);//打印
void HeapPrint(HP* php);//上调
void AdjustUp(HPDataType* a, int child);//下调
void AdjustDwon(HPDataType* a, int size, int parent);//初始化
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);//堆大小
int HeapSize(HP* php);
2.Heap.c
#include Heap.h//交换
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}//打印
void HeapPrint(HP* php)
{assert(php);for (int i 0; i php-size; i){printf(%d , php-a[i]);}printf(\n);
}//上调logN
void AdjustUp(HPDataType* a, int child)
{//定位父节点下标int parent (child - 1) / 2;while (child 0){// if (a[child] a[parent]) //大堆if (a[child] a[parent]) //小堆{//交换数据Swap(a[child], a[parent]);//交换后更新child parent;parent (child - 1) / 2;}else{break;}}
}//下调logN
void AdjustDwon(HPDataType* a, int size, int parent)
{//设左孩子较小int child parent * 2 1;//当未达到堆末 进入循环while (child size){//确定real大孩子// if (child 1 size a[child 1] a[child]) //大堆//确定real小孩子if (child 1 size a[child 1] a[child]) //小堆{child;}// if (a[parent] a[child]) //大堆if (a[parent] a[child]) //小堆{Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}//初始化
void HeapInit(HP* php)
{assert(php);php-a NULL;php-size php-capacity 0;
}//销毁
void HeapDestroy(HP* php)
{assert(php); free(php-a);php-a NULL;php-size php-capacity 0;
}//入堆
void HeapPush(HP* php, HPDataType x)
{assert(php);if (php-size php-capacity){int newcapacity php-capacity 0 ? 4 : php-capacity * 2;HPDataType* tmp (HPDataType*)realloc(php-a, sizeof(HPDataType) * newcapacity);if (tmp NULL){printf(realloc fail\n);exit(-1);}php-a tmp;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--;//将原堆末(现堆头下调置适当位置)AdjustDwon(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;
}//堆大小
int HeapSize(HP* php)
{assert(php);return php-size;
}
3.test.c
#define _CRT_SECURE_NO_WARNINGS
#includeHeap.h//测试函数
void TestHeap()
{//创建HP hp;//初始化HeapInit(hp);//入堆int a[] { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };for (int i 0; i sizeof(a) / sizeof(int); i){HeapPush(hp, a[i]);}///打印HeapPrint(hp);//入堆 -- 打印HeapPush(hp, 10);HeapPrint(hp);//出堆 -- 打印HeapPop(hp);HeapPrint(hp); HeapPop(hp);HeapPrint(hp);
}4.3堆的应用
1.堆排序
1.1建堆时间复杂度最优为下调N
1.1.1下调O(N) 1.1.2 上调O(NlogN) 1.2代码实现 //堆排序1.0 升序--用--小堆 降序--用--大堆
//问题
//1、需要有一个堆数据结构存在 才能创建堆对象
//2、在堆对象空间再创建一个数组 调整后回写 空间复杂度为 O(N)
void Low_HeapSort(int* a, int n)
{HP hp;HeapInit(hp);for (int i 0; i n; i){HeapPush(hp, a[i]);}int i 0;while (!HeapEmpty(hp)){a[i] HeapTop(hp);HeapPop(hp);}HeapDestroy(hp);
}
//堆排序2.0 升序--建--大堆 降序--建--大堆
void Plus_HeapSort(int* a, int n)
{
//一、建堆
// 1.0 上调建堆法 O(N*logN)
// 将数组a传参后 假设原数组就是一颗树 只不过这棵树待调整
// 上调法遍历数组 从1到n-1 上调至合适位置
// 定位父节点下标 int parent (child - 1) / 2 -- i从1开始而非0/*for (int i 1; i n; i){AdjustUp(a, i);}*/
// 2.0 下调建堆法 O(N)
// 将数组a传参后 假设原数组就是一颗树 只不过这棵树待调整
// 下调法遍历数组 叶子节点无孩子不用下调
// 从倒数第一个非叶子节点开始遍历至根节点
// 倒数第一个非叶子节点末节点的父亲
// 公式计算父节点下标 int parent (child - 1) / 2
// 末节点下标n - 1 - 1
// 设左孩子较小 int child parent * 2 1;for (int i (n - 1 - 1) / 2; i 0; --i){AdjustDwon(a, n, i);}
//二、排序(升序法将大值一次排到尾部 建大堆--根最大) O(N*logN)//定位末节点int end n - 1;//排序 遍历已经调好位置的大堆while (end 0){//头尾交换(最大的值(根结点)与末节点的值交换)//下调Swap(a[0], a[end]);AdjustDwon(a, end, 0);//下标前移--end;}
}//测试堆排序
void TestHeapSort()
{int a[] { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };Plus_HeapSort(a, sizeof(a) / sizeof(int));for (int i 0; i sizeof(a) / sizeof(int); i){printf(%d , a[i]);}
}int main()
{TestHeapSort();return 0;
}1.3堆排序时间复杂度
堆排序时间复杂度 建堆 排序 O(N) O(N*longN) O(NlogN)
2.topk问题
2.1介绍及解决方式
介绍 求数据结合中前K个最大的元素或者最小的元素 解决方式 用堆来解决 基本思路
思路一O(N * logN) 将N个数据进行排序 目前接触到的排序算法最优为堆排序思路二O(N k * logN) 【N个数据建堆空间浪费巨大】 将N个数据建成大堆 然后Top/Pop k次 时间复杂度 下调建大堆 Top/Pop思路三O[K (N-K) * logK] 【最优 时间上可能比二差点 但空间上效率提高】 将N个数据前K个元素建堆取前k个最大的元素–建小堆取前k个最小的元素建大堆 用剩余的N-K个元素依次与堆顶元素比较不满足则替换堆顶元素 将剩余N-K个元素依次与堆顶元素比完之后堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
2.2代码举例
//打印Topk函数
void PrintTopK(int* a, int n, int k)
{// 1.下调建堆 -- 用前k个元素建堆//申请空间int* kHeap (int*)malloc(sizeof(int) * k);assert(kHeap);//拷贝前k个for (int i 0; i k; i){kHeap[i] a[i];}//显示kHeapprintf(kHeap的数据显示\n);for (int i 0; i k; i){printf(%d , kHeap[i]);}printf(\n);//下调建堆for (int i (k - 1 - 1) / 2; i 0; --i){AdjustDwon(kHeap, k, i); //此时AdjustDwon实现的是建小堆} //显示kHeapprintf(kHeap的数据显示\n);for (int i 0; i k; i){printf(%d , kHeap[i]);}printf(\n);// 2.访问数组a中n-k个元素 -- 依次与堆顶元素比较 -- 不满足则替换for (int j k; j n; j){if (a[j] kHeap[0]){kHeap[0] a[j];AdjustDwon(kHeap, k, 0);printf(kHeap的数据显示\n);for (int i 0; i k; i){printf(%d , kHeap[i]);}printf(\n);}}//打印printf(kHeap的数据显示\n);for (int i 0; i k; i){printf(%d , kHeap[i]);}printf(\n);
}//Topk测试函数
void TestTopk()
{//一、生成10个100的数int* a (int*)malloc(sizeof(int) * 10);srand(time(0));for (int i 0; i 10; i){a[i] rand() % 100;}//将其中5个数修改成大于100的数a[6] 100 6;a[4] 100 9;a[8] 100 2;a[2] 100 1;a[0] 100 4;//打印查看printf(a的数据显示\n);for (int i 0; i 10; i){printf(%d , a[i]);}printf(\n);//检验PrintTopK(a, 10, 5);
}int main()
{TestTopk();return 0;
}5.普通二叉树的结构
5.1代码实现 #define _CRT_SECURE_NO_WARNINGS#includestdio.h
#includestdlib.h
#includestdbool.h
#includeassert.htypedef int BTDataType;
typedef struct BinaryTreeNode
{struct BinaryTreeNode* left;struct BinaryTreeNode* right;BTDataType data;
}BTNode;//创建新结点
BTNode* CreatNode(BTDataType x)
{BTNode* node (BTNode*)malloc(sizeof(BTNode));assert(node);node-data x;node-left NULL;node-right NULL;return node;
}//自创二叉树
BTNode* CreatBinaryTree()
{BTNode* node1 CreatNode(1);BTNode* node2 CreatNode(2);BTNode* node3 CreatNode(3);BTNode* node4 CreatNode(4);BTNode* node5 CreatNode(5);BTNode* node6 CreatNode(6);node1-left node2;node1-right node4;node2-left node3;node4-left node5;node4-right node6;return node1;
}//前序遍历NLR
void PreOrder(BTNode* root)
{if (root NULL){printf(# );return;}printf(%d , root-data);PreOrder(root-left);PreOrder(root-right);
}//中序遍历LNR
void InOrder(BTNode* root)
{if (root NULL){printf(# );return;}InOrder(root-left);printf(%d , root-data);InOrder(root-right);
}//后序遍历LRN
void PostOrder(BTNode* root)
{if (root NULL) {printf(# );return;}PostOrder(root-left);PostOrder(root-right);printf(%d , root-data);
}//结点个数1.0--NLR
int count 0;
void TreeSize1(BTNode* root)
{if (root NULL){return;}count;TreeSize1(root-left);TreeSize1(root-right);
}//结点个数2.0--LRN
int TreeSize2(BTNode* root)
{return root NULL ? 0 :TreeSize2(root-left) TreeSize2(root-right) 1;
}//叶子结点数--LRN
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层结点个数--LRN
int TreeKLevel(BTNode* root, int k)
{assert(k 1);if (root NULL)return 0;if (k 1)return 1;return TreeKLevel(root-left, k - 1) TreeKLevel(root-right, k - 1);
}// 求二叉树深度--LRN
int TreeDepth(BTNode* root)
{if (root NULL)return 0;int leftDepth TreeDepth(root - left);int rightDepth TreeDepth(root - right);return leftDepth rightDepth ? leftDepth 1 : rightDepth 1;
}//查找目标结点--NLR
BTNode* TreeFind(BTNode* root, BTDataType x)
{if (root NULL)return NULL;if (root-data x)return root; BTNode* ret1 TreeFind(root-left, x); if (ret1) return ret1;BTNode* ret2 TreeFind(root-right, x); if (ret2) return ret2;return NULL;
}int main()
{//创建二叉树 BTNode* root CreatBinaryTree();//NLRPreOrder(root);printf(\n);//LNRInOrder(root);printf(\n);//LRNPostOrder(root);printf(\n);//结点个数1.0count 0;TreeSize1(root);printf(TreeSize:%d\n, count);//结点个数2.0printf(TreeSize:%d\n, TreeSize2(root));printf(TreeSize:%d\n, TreeSize2(root));//叶子结点数printf(LeafSize:%d\n, TreeLeafSize(root));//第k层结点个数printf(KLevelSize:%d\n, TreeKLevel(root, 1));printf(KLevelSize:%d\n, TreeKLevel(root, 2));printf(KLevelSize:%d\n, TreeKLevel(root, 3));printf(KLevelSize:%d\n, TreeKLevel(root, 4));return 0;
}5.2算法图解(递归)
