智能建站系统哪个好,科技公司网站设计服务,多语言外贸企业网站源码,网站首页 flash本章代码仓库#xff1a;堆、二叉树链式结构 文章目录 #x1f36d;1. 树#x1f9c1;1.1 树的概念#x1f9c1;1.2 树的结构 #x1f36c;2. 二叉树#x1f36b;2.1 二叉树的概念#x1f36b;2.2 特殊的二叉树#x1f36b;2.3 二叉树的性质#x1f36b;2.4 二叉树的存… 本章代码仓库堆、二叉树链式结构 文章目录 1. 树1.1 树的概念1.2 树的结构 2. 二叉树2.1 二叉树的概念2.2 特殊的二叉树2.3 二叉树的性质2.4 二叉树的存储结构 3. 堆3.1 堆的实现接口声明接口实现 3.2 堆排序堆排序实现堆排序时间复杂度☕向下调整时间复杂度☕向上调整时间复杂度☕调堆时间复杂度 3.3 Top-K 4. 链式二叉树结构实现4.1 手搓链式4.2 二叉树遍历前序遍历中序遍历后序遍历层序遍历 4.3 二叉树结点个数4.4 树的深度4.5 K层结点个数4.6 查找值为x的结点4.6 查找值为x的结点 1. 树
1.1 树的概念
树是一种非线性的数据结构由n个有限节点组成的一个具有层次关系的有限集。
在任意一颗非空的树中
有且具有一个特定的节点称为root节点除根节点外其他节点被分成M个不互相交的有限集每棵子树根节点有且仅有一个前驱节点可以有0个或者多个后继节点树是递归定义的 节点的度一个节点含有的子树的个数称为该节点的度 如上图B的度为4 叶节点或终端节点度为0的节点称为叶节点没有孩子 如上图D、J、K、F、G、H、I 非终端节点或分支节点度不为0的节点有孩子 如上图B、C、E 双亲节点或父节点若一个节点含有子节点则这个节点称为其子节点的父节点 如上图A是B的父节点 孩子节点或子节点一个节点含有的子树的根节点称为该节点的子节点 如上图B是A的孩子节点 兄弟节点具有相同父节点的节点互称为兄弟节点 如上图B、C是兄弟节点 树的度一棵树中最大的节点的度称为树的度 如上图树的度为4 节点的层次从根开始定义起根为第1层根的子节点为第2层以此类推 树的高度或深度树中节点的最大层次 如上图树的高度为4 堂兄弟节点双亲在同一层的节点互为堂兄弟如上图G、H互为堂兄弟节点 节点的祖先从根到该节点所经分支上的所有节点如上图A是所有节点的祖先 子孙以某节点为根的子树中任一节点都称为该节点的子孙。如上图所有节点都是A的子孙 森林由mm0棵互不相交的树的集合称为森林 1.2 树的结构
树的结构如果用线性结构就会蛮复杂假设我们知道树的度为5那我们就可以定义一个指针数组来表示每层的节点
#define N 5
struct TreeNode
{struct TreeNode* children[N]; //指针数组
};在一般情况下我们都是不知道树的度如果采用线性结构十分不便
struct TreeNode
{SeqList sl; //存节点指针int val;
}所以在实际中一般采用孩子兄弟表示法
typedef int DateType;
struct TreeNode
{struct TreeNode* _firstChild; //第一个孩子节点struct TreeNode* _pNextBrother; //兄弟节点DateType _val; //数据
};树在数据结构中并不常用树在实际中的典型应用就是文件系统一层一层的 将Code文件看作根节点下面的cpp、remake-c、linux等就能看作是它的孩子节点 然后这些文件里面又包含了其他文件层层推进 2. 二叉树
2.1 二叉树的概念
二叉树可以看作一个进行了“计划生育”的树 二叉树的特点
每个节点至多有两颗子树不存在度大于2的节点左子树右子树有顺序次序不可颠倒好比人的左右手即使某个节点只要一棵子树也要区分是左子树还是右子树
2.2 特殊的二叉树 满二叉树 满二叉树就是所有的分支节点都有左右子树并且所有叶子都在同一层 假设二叉树的深度为K则总节点数则为2k-1 完全二叉树 完全二叉树从根节点开始从左到右依次填充节点直到最后一层最后一层的节点可以不满但节点都尽量靠左排列 满二叉树定是完全二叉树正方形也是一种特殊的长方形
2.3 二叉树的性质 一颗非空二叉树第i层至多有**2i-1**个结点 深度为k的二叉树至多有2k-1 个结点 对于任何一颗二叉树如果终端叶子节点为n0度为2的结点数为n2则n0 n2 1 有n个结点的满二叉树的深度h log2(n1) 高度为h的完全二叉树结点数量范围[2h-12h-1] 对于具有n个结点的完全二叉树如果按照从上至下从左至右的数组顺序对所有节点从0开始编号则对 于序号为i的结点有 若i0i位置节点的双亲序号(i-1)/2i0i为根节点编号无双亲节点若2i1n左孩子序号2i12i1n否则无左孩子若2i2n右孩子序号2i22i2n否则无右孩子
2.4 二叉树的存储结构
二叉树的存储结构可分为顺序存储和链式存储 顺序存储 顺序存储就是用数组来存储这一般适用于完全二叉树因为这样不会造成空间的浪费 这在物理上是一个数组但在逻辑上是一颗二叉树 链式存储 顾名思义采用链表来表示这颗二叉树 typedef int DateType;
struct TreeNode
{struct TreeNode* _lChild; //左孩子struct TreeNode* _rChild; //右孩子DateType _val; //数据
};3. 堆
堆是一颗完全二叉树堆中的每个节点都满足堆序性质即在最大堆中每个节点的值都大于或等于其子节点的值在最小堆中每个节点的值都小于或等于其子节点的值。
3.1 堆的实现
下面以大根堆为例
接口声明
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h
#define CAPACITY 4typedef int HPDateType;
typedef struct Heap
{HPDateType* val;int _size;int _capacity;
}HP;//初始化
void HeapInit(HP* php);
//插入数据
void HeapPush(HP* php, HPDateType x);
//删除堆顶元素
void HeapPop(HP* php);
//获取堆顶元素
HPDateType HeapTop(HP* php);
//是否有元素
bool HeapEmpty(HP* php);
//获取当前堆的元素数量
int HeapSize(HP* php);
//销毁
void HeapDestroy(HP* php);void AdjustUp(HPDateType* val, int child);
void AdjustDown(HPDateType* val, int sz, int parent);
void Swap(HPDateType* x1, HPDateType* x2);
接口实现
#define _CRT_SECURE_NO_WARNINGS 1
#pragma warning(disable:6031)
#includeHeap.h//初始化
void HeapInit(HP* php)
{assert(php);php-val (HPDateType*)malloc(sizeof(HPDateType) * CAPACITY);if (php-val NULL){perror(malloc fail);exit(-1);}php-_size 0;php-_capacity CAPACITY;
}
//交换元素
void Swap(HPDateType* x1, HPDateType* x2)
{HPDateType tmp *x1;*x1 *x2;*x2 tmp;
}
//向上调整 前提子树是堆
void AdjustUp(HPDateType* val, int child)
{int parent (child - 1) / 2;while (child 0){if (val[child] val[parent]){Swap(val[child], val[parent]);child parent;parent (child - 1) / 2;}else{break;}}
}
//向下调整 前提子树都是堆
void AdjustDown(HPDateType* val, int sz, int parent)
{//默认左孩子大int child parent * 2 1;//至多叶子结点结束while (child sz){//不越界 选出更大的孩子if (child1sz val[child] val[child1]){child;}if (val[child] val[parent]){Swap(val[child], val[parent]);parent child;child parent * 2 1;}else{break;}}
}
//插入数据
void HeapPush(HP* php, HPDateType x)
{assert(php);if (php-_size php-_capacity){//扩容HPDateType* tmp realloc(php-val, sizeof(HPDateType) * php-_capacity * 2);if (tmp NULL){perror(realloc fail);exit(-1);}php-val tmp;php-_capacity * 2;}php-val[php-_size] x;php-_size;AdjustUp(php-val, php-_size - 1);
}
//删除堆顶元素
void HeapPop(HP* php)
{assert(php);assert(!HeapEmpty(php));Swap(php-val[0], php-val[php-_size - 1]);php-_size--;AdjustDown(php-val, php-_size, 0);
}
//获取堆顶元素
HPDateType HeapTop(HP* php)
{assert(php);return php-val[0];
}
//是否有元素
bool HeapEmpty(HP* php)
{assert(php);return php-_size 0;
}
//获取当前堆的元素数量
int HeapSize(HP* php)
{assert(php);return php-_size;
}
//销毁
void HeapDestroy(HP* php)
{free(php-val);php-val NULL;php-_size 0;php-_capacity 0;
}3.2 堆排序
堆排序实现
堆排序分为两个步骤 建堆 排升序建大堆 排降序建小堆 堆删除的思想进行排序 如果排升序堆顶元素是最大的将其与最后一个元素交换这就是堆的删除操作但我们不需要将这个数据删除交换完不管它即可这样最后一个元素就是最大的然后再向下调整再找出最大的元素以此反复则可完成升序的排序。 使用堆排序不需要手搓一个数据结构堆出来我们只需要建堆和模拟删除操作即可
//排升序 建大堆
void HeapSort(int* pa, int sz)
{//向上调整 建堆 O(N*logN)//for (int i 0; i sz; i)//{// AdjustUp(pa, i);//}//向下调整 O(N)for (int i (sz - 1 - 1) / 2; i 0; --i){AdjustDown(pa, sz, i);}//向下调整排序 O(N*logN)for (int i 0; i sz; i){Swap(pa[0], pa[sz - 1 - i]);AdjustDown(pa, sz - 1 - i, 0);}}堆排序时间复杂度
建堆操作可以采用向上调整也可以采用向下调整但是向下调整的效率是高于向上调整的 ☕向下调整时间复杂度
向下调整是从第h-1层开始的
层数结点数向下移动层数12^0h-122^1h-232^2h-3h-12^(h-2)1
调整次数
T(N) 2h-1 * 1 2h-2 * 2 2h-3 * 3 … 22 * (h-3) 21 * (h-2) 20 * (h-1)
化简得T(N) 2h -1 - h
高度为h的满二叉树结点个数为N 2h - 1
这样即可推出时间复杂度为N - log2(N1)N和logN不在一个量级则时间复杂度为O(N)
过程示例 ☕向上调整时间复杂度
向上调整建堆是从第二层开始调整的
层数结点数向上移动层数22^1132^22h-12^(h-2)h-2h2^(h-1)h-1
调整次数
T(N) 21 * 1 22 * 2 … 2h-1 * (h-2) 2h-1 * (h-1)
化简得T(N) -2h 2 2h * h - 2h 2h * h - 2h * 2 2
高度为h的满二叉树结点个数为N 2h - 1
推出时间复杂度为(N1)*log2(N1) - 2*(N1) 2N和logN不在一个量级则时间复杂度为O(N*logN)
过程示例 这里也很好比较
向上调整建堆时结点数多的地方调整次数多
而向下调整建堆时结点数多的地方调整次数少所以采用向下调整建堆时效率会高于向上调整
☕调堆时间复杂度
建完堆直接我们只能保证栈顶元素是最大/最下的要完成排序还需要调堆
调堆采用的是删除堆顶元素的逻辑N个元素每次调整的时间复杂度为O(logN)则整个堆排序时间复杂度为N*log(N)
3.3 Top-K
在现实的世界中大部分只关注前多少多少例如我国排名前十的大学、一个专业学生成绩的前五等等。
这些都是排序如果数据量较大数据可能不会一下子就全部加载到内存当中那我们就可以采用Top-K的思路解决
用数据集合中的前k个来建堆然后再用剩余的N-K个元素依次与堆顶元素比较
前k个最大元素建小堆前k个最小元素建大堆 例如要在十万个数据当中找出5个最大/最小的数据只需要建一个存储5个元素的堆 以前5个最大元素为例那就是建小堆那堆顶元素则是最小的每次只需将堆顶元素和数据进行对比如果大于堆顶元素则替换掉堆顶元素然后进堆这样就一直保证堆顶元素是这个堆中最小的元素 场景模拟
一万个小于一万的随机数找出前k个最大元素
void Print_TopK(const char* file, int k)
{int* topk (int*)malloc(sizeof(int) * 5);if (topk NULL){perror(malloc fail);exit(-1);}FILE* fout fopen(file, r);if (fout NULL){perror(fopen fail);exit(-1);}//读取前k个数据for (int i 0; i k; i){fscanf(fout, %d, topk[i]);}//建小堆for (int i (k - 2) / 2; i 0; i--){AdjustDown(topk, k, i);}//将剩余元素与堆顶元素比较大于堆顶元素则替换int val 0;int ret fscanf(fout, %d, val);while (ret ! EOF){if (val topk[0]){topk[0] val;AdjustDown(topk, k, 0);}ret fscanf(fout, %d, val);}for (int i 0; i k; i){printf(%d , topk[i]);}printf(\n);free(topk);topk NULL;fclose(fout);
}
//造数据
void CreateDate()
{int n 10000;srand((int)time(0));const char* file data.txt;FILE* fin fopen(file, w);if (fin NULL){perror(fopen fail);exit(-1);}for (size_t i 0; i n; i){int x rand() % 10000;fprintf(fin, %d\n, x);}fclose(fin);
}4. 链式二叉树结构实现
4.1 手搓链式
堆属于一种线性二叉树对于链式二叉树本次采用手搓的方式创建
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;
//申请结点
BTNode* BuyNode(BTDataType x)
{BTNode* node (BTNode*)malloc(sizeof(BTNode));if (node NULL){perror(malloc fail);exit(-1);}node-data x;node-left NULL;node-right NULL;return node;
}
//造树手搓
BTNode* CreatTree()
{BTNode* node1 BuyNode(1);BTNode* node2 BuyNode(2);BTNode* node3 BuyNode(3);BTNode* node4 BuyNode(4);BTNode* node5 BuyNode(5);BTNode* node6 BuyNode(6);BTNode* node7 BuyNode(7);BTNode* node8 BuyNode(8);node1-left node2;node1-right node4;;node2-left node3;node3-right node7;node7-left node8;node4-left node5;node4-right node6;return node1;
}4.2 二叉树遍历
前序遍历
前序遍历也叫做先序遍历访问顺序根 - 左子树 - 右子树
//前序遍历:根 左子树 右子树
void PreOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}printf(%d , root-data);PreOrder(root-left);PreOrder(root-right);
}中序遍历
中序遍历访问顺序左子树 - 根 - 右子树
//中序遍历左子树 根 右子树
void InOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}InOrder(root-left);printf(%d , root-data);InOrder(root-right);
}后序遍历
后序遍历访问顺序左子树 - 右子树 - 根
//后序遍历左子树 右子树 根
void PostOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}PostOrder(root-left);PostOrder(root-right);printf(%d , root-data);
}层序遍历
层序遍历与前三种不一样层序遍历采用队列的方式实现 首先根节点进队列当遍历根节点之后根节点出队列的同时把左右孩子带进去 然后再两个孩子依次出队同时带入孩子的孩子依次反复 void LevelOrder(BTNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);printf(%d , front-data);if(front-left)QueuePush(q, front-left);if (front-right)QueuePush(q, front-right);}QueueDestroy(q);
}4.3 二叉树结点个数
统计左子树和右子树的结点然后再加上自己的一个
//树的结点树
int TreeSize(BTNode* root)
{return root NULL ? 0 : TreeSize(root-left) TreeSize(root-right) 1;
}4.4 树的深度
这里每次都要记录每次统计的结点个数不然每次每层都得重新统计(如注释代码块)
//树的深度
int TreeHeight(BTNode* root)
{if (root NULL){return 0; }//记录深度int left TreeHeight(root-left)1;int right TreeHeight(root-right)1;printf(%d %d\n, left, right);return leftright?left:right;//return rootNULL?0: TreeHeight(root-left) TreeHeight(root-right) ? TreeHeight(root-left)1 : TreeHeight(root-right)1;
}4.5 K层结点个数
//K层结点个数
int TreeKLevel(BTNode* root, int k)
{if (root NULL)return 0;if (k 1)return 1;int leftChild TreeKLevel(root-left, k - 1);int rightChild TreeKLevel(root-right, k - 1);return leftChild rightChild;}4.6 查找值为x的结点
//查找值为x的结点
BTNode* TreeFind(BTNode* root, BTDataType x)
{if (root NULL)return NULL;if (root-data x)return root;//记录结点BTNode* leftNode TreeFind(root-left, x);BTNode* rightNode TreeFind(root-right, x);if (leftNode)return leftNode;else if (rightNode)return rightNode;return NULL;
}root-left) TreeHeight(root-right) ? TreeHeight(root-left)1 : TreeHeight(root-right)1; } ## 4.5 K层结点个数c
//K层结点个数
int TreeKLevel(BTNode* root, int k)
{if (root NULL)return 0;if (k 1)return 1;int leftChild TreeKLevel(root-left, k - 1);int rightChild TreeKLevel(root-right, k - 1);return leftChild rightChild;}4.6 查找值为x的结点
//查找值为x的结点
BTNode* TreeFind(BTNode* root, BTDataType x)
{if (root NULL)return NULL;if (root-data x)return root;//记录结点BTNode* leftNode TreeFind(root-left, x);BTNode* rightNode TreeFind(root-right, x);if (leftNode)return leftNode;else if (rightNode)return rightNode;return NULL;
}
