丁香园做科室网站,国外展柜网站,四川建设厅官方网站查询资料员,做餐饮公司网站一.二叉树的顺序结构
1.定义#xff1a;使用数组存储数据#xff0c;一般使用数组只适合表示完全二叉树#xff0c;此时不会有空间的浪费
注#xff1a;二叉树的顺序存储在逻辑上是一颗二叉树#xff0c;但是在物理上是一个数组#xff0c;此时需要程序员自己想清楚调整…一.二叉树的顺序结构
1.定义使用数组存储数据一般使用数组只适合表示完全二叉树此时不会有空间的浪费
注二叉树的顺序存储在逻辑上是一颗二叉树但是在物理上是一个数组此时需要程序员自己想清楚调整数据时应该怎样调整
2.堆
(1)定义集合中所有元素按照完全二叉树的顺序存储在一个一维数组中并满足KiK2*i1且K2*i2(或KiK2*i1且K2*i2)的规律则称之为堆 (2)性质
1堆中某个节点的值总是不大于(或不小于)其父节点的值
2堆是一颗完全二叉树
3大堆任何一个父节点的值孩子的值 小堆任何一个父节点的值孩子的值 (3)堆的实现(以小堆为例)
1堆的结构体定义数组指针(用于存储数据),有效数据个数空间容量大小
typedef int HeapDataType;
typedef struct Heap
{HeapDataType* a;//数组指针int size;//有效数据个数int capacity;//有效空间大小
}HP;2堆的初始化
//堆的初始化
void HPInit(HP* ph)
{assert(ph);ph-a NULL;ph-size ph-capacity 0;
}3堆的销毁
//堆的销毁
void HPDestory(HP* ph)
{assert(ph);free(ph-a);ph-a NULL;ph-size ph-capacity 0;
}
4向堆中插入数据
**思路将数据插在原数据的最后面在不断向上调整以保证插入数据后仍为小堆
**画图解释 **代码实现
//向堆内插入数据
void HPPush(HP* ph, HeapDataType x)
{assert(ph);//判断是否需要增容if (ph-size ph-capacity){int newcapacity ph-capacity * 2 0 ? 4 : ph-capacity * 2;HeapDataType* tmp (HeapDataType*)realloc(ph-a, sizeof(HeapDataType) * newcapacity);if (tmp NULL){perror(realloc fail);return;}ph-a tmp;ph-capacity newcapacity;}ph-a[ph-size] x;ph-size;AdjustUp(ph-a, ph-size-1);}5向上调整数据
思路找孩子的父亲判断父亲是否大于孩子若大于则交换父子地位继续向上调整 注由于堆是完全二叉树一个父亲最多有两个孩子所以父亲的下标应该是孩子的下标减一再除以2即parent(child-1)/2;
//向上调整
void AdjustUp(HeapDataType* a, int child)
{int parent (child - 1) / 2;while (child 0){if (a[parent] a[child]){Swap(a[parent], a[child]);child parent;parent (child - 1) / 2;}else{break;}}
}
6删除根部数据
思路先交换根部数据和最后一个数据再删除根部数据同时将最后一个数据向下调整以保证删除后的堆仍为小堆
//删除堆顶数据(根位置)
void HPPop(HP* ph)
{assert(ph);Swap(ph-a[0], ph-a[ph-size - 1]);ph-size--;AdjustDown(ph-a, ph-size, 0);
}
7向下调整数据
**思路先找左右孩子中较小的那个孩子与父亲相比若父亲大于孩子则交换父子地位继续向下调整
注由于堆是完全二叉树一个父亲最多有两个孩子所以左孩子的下标应该是父亲的下标乘以2再加1即childparent*21;
**画图解释 **代码实现
//向下调整
void AdjustDown(HeapDataType* a, int size, int parent)
{//默认左孩子小int child parent * 2 1;while (child size){//找左右孩子中小的那一个if ((child1) size a[child1] a[child]){child ;}if (a[parent] a[child]){Swap(a[parent], a[child]);parent child;child parent * 2 1;}else{break;}}
}
(4)堆的应用
1堆排序
1.1)思路注降序建小堆升序建大堆 将数组中的元素建堆交换最后的数据与首位数据并进行向下调整让size--循环操 作直至完成排序
1.2)时间复杂度ON*log N 1.3)画图解释 1.4)代码实现
void HeapSort(int* a, int size)
{//将数组建堆for (int i 1; i size; i){AdjustUp(a, i);}int end size - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);--end;}
}
2TOP_K(以求前K个最大的数据为例)
2.1)定义求出数据中前K个最大的数据或前K个最小的数据
2.2)思路
思路一创建一个含N个节点的大堆PopK次即可获取前K个最大的数据 弊端当N非常大时在创建节点时需要占用大量的内存
思路二建一个含K个节点的小堆将剩余的N-K个数据与堆顶数据相比若大于堆顶数据则入 堆进行向下调整否则进行下一个比较
注思路二更优效率高
2.3)代码实现
void TOP_K(int* a,int n,int k)
{//在文件中读取数据const char* fp data.txt;FILE* fout fopen(fp, r);if (fout NULL){perror(fopen fail);return;}//读取前K个数据for (int i 0; i k; i){fscanf(fout,%d, a[i]);}//建小堆for (int i (k-1-1)/2;i0;i--){AdjustDown(a, k, i);}//将剩余的n-k个数据于堆顶数据相比int x 0;while (fscanf(fout,%d,x)!EOF){if (a[0]x){a[0] x;AdjustDown(a, k, 0);}}for (int i 0; i k; i){printf(%d , a[i]);}printf(\n);
}2.4)数据验证
思路将N的节点的数据模上N是他们处于小于N的状态在随机挑K个数据将他们调大于N若在选出来的K个数据为大于N的数据则说明该程序执行的是选取前K个最大的数据的指令
二.二叉树的链式结构(以二叉链表为例)
注在二叉树的实现中多用递归来达到一层一层向下查找的目的(所以读者需要熟练掌握递归的相关知识)
1.定义用链表表示一颗二叉树即用链表表示元素之间的逻辑关系
2.二叉树节点的定义该节点内存储的数据指向左孩子的指针指向右孩子的指针
typedef int BTNodeData;
typedef struct BinaryTreeNode
{BTNodeData val;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;
3.二叉树的创建(根据前序遍历来创建二叉树)
以数组abd##e#h##cf##g##构建二叉树
1思路1)若当前数据为#则返回NULL 2)否则开辟一个二叉树节点root将该数据赋给val,给左右孩子赋值通过调用函数递 归实现
2代码实现
//创建二叉树
BTNode* BTCreate(BTNodeData* a, int* pi)
{if (a[*pi] ‘#’){(*pi);return NULL;}BTNode* root (BTNode*)malloc(sizeof(BTNode));root-val a[*pi];(*pi);root-left BTCreate(a,pi);root-right BTCreate(a, pi);return root;
}
4.二叉树的前序遍历
1访问顺序根左子树右子树
2思路如果根为空打印N什么都不返回否则先打印根的值再调用该函数将左子树的地址作为参数然后调用该函数将右子树的地址作为参数利用递归实现前序遍历 3代码实现
//前序遍历
void PreOrder(BTNode* root)
{if (root NULL){printf(N );return;}printf(%d , root-val);PreOrder(root-left);PreOrder(root-right);
}
5.二叉树的中序遍历
1访问顺序左子树根右子树
2思路与前序遍历类似
3代码实现
//中序遍历
void InOrder(BTNode* root)
{if (root NULL){printf(N );return;}InOrder(root-left);printf(%d , root-val);InOrder(root-right);
}
6.二叉树的后序遍历
1访问顺序左子树右子树根
2思路与前序遍历类似
3代码实现
//后序遍历
void PostOrder(BTNode* root)
{if (root NULL){printf(N );return;}PostOrder(root-left);PostOrder(root-right);printf(%d , root-val);
}
7.二叉树的层序遍历
1思路利用队列让上一层的节点先入队列在删除他们时带进去下一层若节点为空不进队列
2代码实现
//层序遍历
void BTLevelOrder(BTNode* root)
{Queue q;QueueInit(q);if (root){QueuePush(q, root);}while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);printf(%d , front-val);//当节点不为空时入队列if (front-left){QueuePush(q, front-left);}if(front-right){QueuePush(q, front-right);}}printf(\n);QueueDestory(q);
}8.二叉树的节点个数
1思路1)如果根节点为空返回0 2)否则返回左子树的节点数右子树的节点数1(利用递归法实现左右子树节点数的计算)
2代码实现
//二叉树节点个数
int BTSize(BTNode* root)
{if (root NULL){return 0;}return BTSize(root-left) BTSize(root-right) 1;
}9.二叉树的叶子节点个数
1思路1)如果根为空返回0 2)如果左右孩子均为空返回1 3)否则返回左子树叶子数右子树叶子数(利用递归实现左右子树叶子数的计算)
2代码实现
//二叉树叶子节点个数
int BTLeafSize(BTNode* root)
{if (root NULL){return 0;}if (root-left NULL root-right NULL){return 1;}return BTLeafSize(root-left) BTLeafSize(root-right);
}
10.二叉树第K层节点个数
1思路1)如果根为空返回0 2)如果k1返回1 3)否则返回左子树的k-1层右子树的k-1层
注将树一层一层向下压直至出现两种特殊情况
2代码实现
//二叉树第K层节点个数
int BTLevelKSize(BTNode* root, int k)
{if (root NULL){return 0;}if (k 1){return 1;}return BTLevelKSize(root-left, k - 1) BTLevelKSize(root-right, k - 1);
}
11.二叉树查找值为X的节点
1思路1)若根为空返回空 2)若根的值等于待查找数据返回根的地址 3)否则查找左子树是否有值为X的节点若有返回该节点的地址否则查找右子树是否有值 为X的节点若有返回该节点的地址若左右子树均没有是否有值为X的节点则返回空
2代码实现
//二叉树查找值为X的节点
BTNode* BTFind(BTNode* root, BTNodeData x)
{if (root NULL){return NULL;}if (root-val x){return root;}//比较左子树是否有节点值为xBTNode* ret1 BTFind(root-left, x);if (ret1!NULL){return ret1;}//比较右子树是否有节点值为xBTNode* ret2 BTFind(root-right, x);if (ret2 ! NULL){return ret2;}//左右子树中均未找到值为x的节点return NULL;
}
12.树的高度
1思路1)若根为空返回0 2)否则记录并分别求左右子树的高度哪个值更大哪个即为树的高度
注每次都需记录所求的树的高度否则会出现走到上一层忘了下一层的情况导致反复求某棵树高度的情况
2代码实现
//二叉树的高度
int BTHeight(BTNode* root)
{if (root NULL){return 0;}int HeightLeft BTHeight(root-left)1;int HeightRight BTHeight(root-right)1;return HeightLeft HeightRight ? HeightLeft : HeightRight ;
}
13.二叉树的销毁
1思路用后序遍历的思想先销毁左右子树再销毁根(若先销毁根销毁根后无法找到左右子树)
2代码实现
//二叉树的销毁
void BTDestory(BTNode* root)
{if (root NULL)return;BTDestory(root-left);BTDestory(root-right);free(root);}
14.判断二叉树是否为完全二叉树
1思路无论节点是否为空都入队列当检查到第一个空节点时开始遍历后面的节点看是否有非空节点若有则不是完全二叉树否则是完全二叉树
2代码实现
//二叉树是否为完全二叉树
bool BTComplete(BTNode* root)
{Queue q;QueueInit(q);if (root){QueuePush(q, root);}while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);//若第一个空如队列跳出循坏开始遍历看之后是否有非空节点的存在if (front NULL){break;}QueuePush(q, front-left);QueuePush(q, front-right);}//遍历看是否有非空节点while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);if (front ! NULL){QueueDestory(q);return false;}}QueueDestory(q);return true;
}
