南昌市城市建设档案馆网站,桔子建站是什么平台,服务类型的网站怎么做,html语言做网站1. 树相关术语 父结点/双亲结点#xff1a;如果一个结点有子结点那么它就是父结点或者双亲结点#xff1b;例如A是BCDEFG的父结点#xff0c;J是PQ的父结点等等#xff1b;子结点#xff1a;一个结点含有的子树的根节点称为该结点的子结点#xff1b;如上图的H是D的子结点…1. 树相关术语 父结点/双亲结点如果一个结点有子结点那么它就是父结点或者双亲结点例如A是BCDEFG的父结点J是PQ的父结点等等子结点一个结点含有的子树的根节点称为该结点的子结点如上图的H是D的子结点BCDEFG是A的子结点结点的度一个结点有几个子结点那他就有多少度例如A的度为6他的子结点是BCDEFG例如D的度为1他的子结点为H树的度树的度就是最大结点的度上图A的度最大为6所以上面那棵树的度为6叶子结点度为0的结点称为叶子结点也就是没有子结点的结点分支结点度不为0的结点称为分支结点例如DEFGJ都是兄弟结点具有相同父结点的结点称为兄弟结点例如BCDEFG都是兄弟结点因为他们有是A的子结点 结点的层次从根开始定义起根为第 1 层根的⼦结点为第 2 层以此类推 树的高度就是结点的最大层次也就是4其实就是看跟结点到最底部的结点有多少层就是树的高度 结点的祖先从根到该结点所经分⽀上的所有结点如上图 A 是所有结点的祖先 森林由 m m0 棵互不相交的树的集合称为森林 2. 树的表示方法
孩子兄弟表示法就是说一个结点里有一个data值存储数据一个指向从左边开始的第一个子结点还有一个指向右边的兄弟结点如下图和代码所示
struct TreeNode
{struct Node* child; // 左边开始的第⼀个孩⼦结点struct Node* brother; // 指向其右边的下⼀个兄弟结点int data; // 结点中的数据域
}; 3. 二叉树
顾名思义就是开叉的树一个根节点右左子树和右子树组成如下图所示
二叉树不存在度大于2的结点二叉树的子树有左右之分次序不能颠倒所以二叉树是有序的树 3.1 满二叉树
满二叉树就是除了最后一层以外其他每一层的结点都为最大值也就是2则成为满二叉树如果二叉树的层数为k 则结点的总个数为2的k次方-1
3.2 完全二叉树
除了最后一层外其余每一层的结点个数都必须有2的k-1次方个且最后一层的每一个子结点都必须是从左到右依次排放满二叉树是完全二叉树但完全二叉树不一定是满二叉树 二叉树的性质 1若规定根结点的层数为 1 则⼀棵⾮空⼆叉树的第i层上最多有 2 的i次方 −1 个结点 2若规定根结点的层数为 1 则深度为 h 的⼆叉树的最⼤结点数是 2 的h次方 − 1 3若规定根结点的层数为 1 具有 n 个结点的满⼆叉树的深度 h log 2 ( n 1) ( log 以2为底 n1 为对数) 4. 二叉树的存储结构
4.1 顺序结构
顺序结构的底层存储方式是数组但一般只适合完全二叉树如果不是满二叉树的话会有空间的浪费完全二叉树更适合使用顺序结构进行存储 而我们把完全二叉树的顺序存储称为堆这里的堆和操作系统的堆不一样。
4.2 顺序结构二叉树 ⼀般堆使用顺序结构的数组来存储数据堆是⼀种特殊的⼆叉树具有二叉树的特性的同时还具备其他的特性。 4.2.1 堆分为小根堆和大根堆
顾名思义小根堆的根是最小的大根堆的根是最大的值如下图可知
小堆的某个结点的值不得小于其父节点的值大堆的某个结点的值不得大于其父节点的值堆一般都是一棵完全二叉树
4.2.2 堆的性质
4.2.3 堆的实现
由于堆的底层就是数组那么堆的结构和顺序表就大差不差了如下代码所示.h文件也就是准备要实现堆的每个功能的声明
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h
#includestring//定义堆的结构---数组
typedef int HPDataType;
typedef struct Heap
{HPDataType* arr;int size;//有效的数据个数int capacity;//空间大小
}HP;//交换
void Swap(int* x, int* y);//堆的初始化
void HPInit(HP* php);//堆的销毁
void HPDestroy(HP* php);//堆的插入数据
void HPPush(HP* php, HPDataType x);//堆的删除数据
void HPPop(HP* php);//取堆顶数据
HPDataType HPTop(HP* php);// 判空
bool HPEmpty(HP* php);//向上调整
void AdjustUp(HPDataType* arr, int child);//向下调整
void AdjustDown(HPDataType* arr, int parent, int n);
堆的初始化
void HPInit(HP* php)
{assert(php);php-arr NULL;php-capacity 0;php-size 0;
} 堆的删除
void HPDestroy(HP* php)
{assert(php);if (php-arr){free(php-arr);}php-arr NULL;php-capacity 0;php-size 0;
} Swap
void Swap(int* x, int* y)
{int temp *x;*x *y;*y temp;
} 向上调整就是说如果插入的数据不符合小堆或者大堆的性质的话就需要往上调整如下图所示这个就不是小堆因为43比6大父结点大于子结点所以我们需要向上移动如下动图和代码所示
void AdjustUp(HPDataType* arr, int child)
{int parent (child - 1) / 2;while (child 0){if (arr[parent] arr[child]){Swap(arr[parent], arr[child]);child parent;parent (child - 1) / 2;}else{break; }}
} 插入数据插入数据就是在尾部插入一个数据需要判断空间是否充足因为底层是顺序表插入数据后还要向上调整一下如果说符合小堆或大堆特性则不动如果不符合则往上调整如下代码所示
void HPPush(HP* php, HPDataType x)
{//push就是尾插assert(php);//进行插入的时候我们要判断空间是否充足if (php-size php-capacity){int Newcapacity php-capacity 0 ? 4 : 2 * php-capacity;HPDataType* temp (HPDataType*)realloc(php-arr, Newcapacity * sizeof(HPDataType));//漏了sizeof(HPDataType)if (temp NULL){perror(realloc fail!);exit(1);}//增容成功php-arr temp;php-capacity Newcapacity;}php-arr[php-size] x;AdjustUp(php-arr, php-size);php-size;
} 堆的向下调整传入一个父结点判断该父结点和子结点是否符合小堆或大堆的性质和向上调整不一样向上调整是传入子结点判断子结点和父结点如果说在小堆里父结点大于子结点的话就需要向下调整如下图和代码所示
void AdjustDown(HPDataType* arr, int parent, int n)
{int child parent * 2 1;while (child n){if (child 1 n arr[child] arr[child 1]){child;}if (arr[child] arr[parent]){Swap(arr[child], arr[parent]);parent child;child parent * 2 1;}else{break;}}
} 堆的头删操作如果说我们直接删除头结点的话就会出现错误因为本身头结点就是根节点如果说我们直接删掉的话那就出问题了树没有根了所以我们需要交换根节点和最后一个结点然后--size删除掉最后一个结点其实也就是根节点然后再向下调整即可
void HPPop(HP* php)
{assert(php);assert(php-size); //这个就是树要有结点Swap(php-arr[0], php-arr[php-size - 1]);--php-size;AdjustDown(php-arr, 0, php-size);} 判空操作直接就是看size是否为0因为size是计算堆中数据的个数的如下代码所示
bool HPEmpty(HP* php)
{assert(php);return php-size 0;
} 取堆顶元素取堆顶元素就是直接取下标为0的元素即可如下代码所示
HPDataType HPTop(HP* php)
{assert(php php-size);return php-arr[0];
} 4.2.4 堆排序
小堆排序首位交换小的到最下面了然后再对堆顶元素进行向下调整然后--end再首位交换一直循环到end0的时候小数据就全部在后面大数据就全部在前面得到一个降序的数组如果想得到一个升序的则用大堆排序如下代码所示
void HeapSort(int* arr, int n)
{//建堆//升序--大堆//降序--小堆向上建堆//for (int i 0; i n; i)//{// AdjustUp(arr, i);//}//向下建堆得从最下面开始建起//因为向下调整必须他下面就是一个堆//那么就从传入的数据开始传入的i就是childfor (int i (n - 1 - 1) / 2; i 0; i--){//i就是最后一个孩子的父母AdjustDown(arr, i, n);}//建完堆后int end n - 1;while (end 0){Swap(arr[0], arr[end]);AdjustDown(arr, 0, end);end--;}
}int main()
{int arr[] { 17,20,10,13,19,15 };HeapSort(arr, 6);for (int i 0; i 6; i){printf(%d , arr[i]);}return 0;
} 运行结果为 4.3 链式结构实现
用链表来实现一棵二叉树一个结点有三个域组成一个data存储数据一个指向左孩子还有一个指向右孩子
#pragma once
#includeiostream
#includeassert.h
#includestdlib.h
using namespace std;//定义一个链表树
typedef int BTNodeType;
typedef struct BinaryTree
{BTNodeType data;struct BinaryTree* LeftNode;struct BinaryTree* RightNode;}BTNode;
在这里不实现二叉树的插入和删除就先手动创建几个结点如下代码所示
#includeTree.h
BTNode* Buynode(BTNodeType x)
{BTNode* newnode (BTNode*)malloc(sizeof(BTNode));if (newnode NULL){perror(malloc fail!);exit(1);}newnode-data x;newnode-LeftNode newnode-RightNode NULL;return newnode;
}void createTree()
{BTNode* node1 Buynode(1);BTNode* node2 Buynode(2);BTNode* node3 Buynode(3);BTNode* node4 Buynode(4);node1-LeftNode node2;node1-RightNode node3;node2-LeftNode node4;} 调试结果为
4.3.1 前中后序遍历
二叉树有三种方式遍历前序遍历、中序遍历、后序遍历。而这三种遍历都需要使用递归来实现
1前序遍历Preorder先访问根结点、然后左子树、最后右子树总结根左右。
2中序遍历Inorder先访问左子树、然后根结点、最后访问右子树总结左根右
3后序遍历Posorder先访问左子树、然后右子树、最后根结点总结左右根 代码实现如下
//根左右
void PreOrder(BTNode* root)
{if (root NULL){return;}printf(%d, root-data);PreOrder(root-LeftNode);PreOrder(root-RightNode);
}//左根右
void InOrder(BTNode* root)
{if (root NULL){return;}InOrder(root-LeftNode);printf(%d, root-data);InOrder(root-RightNode);
}//左右根
void PosOrder(BTNode* root)
{if (root NULL){return;}PosOrder(root-LeftNode);PosOrder(root-RightNode);printf(%d, root-data);
} 4.3.2 计算Tree的结点个数
首先我们要知道链式结构的二叉树遍历都是需要递归的递归会产生多个函数栈帧如果说我们想创建局部变量来存储的话则无法返回值因为局部变量出了作用域自动被销毁而创建全局变量的话则会出现比如说tree的结点有4个我们调用了两次计算结点个数的函数的话那在第二次打印结点个数的时候会显示8所以一般做叠加计算的话都是通过返回值进行处理如下代码所示
int BinaryTreeSize(BTNode* root)
{if (root NULL){return 0;}return 1 BinaryTreeSize(root-LeftNode) BinaryTreeSize(root-RightNode);
} 4.3.3 计算Tree的叶子结点的个数
计算叶子结点的话也是通过递归进行那我们就要先想清楚递归停止的条件如果不想清楚则会无限陷入递归里面同样也是像上面那样通过返回值进行递归当递归到空节点的时候则要返回0如果说该结点的左右孩子都为NULL的话则说明这是一个叶子结点就返回1如下代码所示
// ⼆叉树叶⼦结点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root NULL){return 0;}if (root-LeftNode NULL root-RightNode NULL){return 1;}return BinaryTreeLeafSize(root-LeftNode) BinaryTreeLeafSize(root-RightNode);
}4.3.4 计算二叉树第k层结点个数
计算第k层结点的个数假如传入的层数k 2 根节点位于第一层遍历到第二层的话就可以通过k-1来实现当k等于1的时候为第二层加入传入的层数k 3的话那就每次递归-1当k等于1的时候就为第三层了
// ⼆叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root NULL){return 0;}if (k 1){return 1;}return BinaryTreeLevelKSize(root-LeftNode, k - 1) BinaryTreeLevelKSize(root-RightNode, k - 1);
}4.3.5 计算二叉树的深度/高度
递归到NULL的时候返回0如果不是NULL则返回1然后还要比较左右子树的大小我们只要最大的所以用个三目运算符进行判断
//⼆叉树的深度/⾼度
int BinaryTreeDepth(BTNode* root)
{if (root NULL){return 0;}int left BinaryTreeDepth(root-LeftNode);int right BinaryTreeDepth(root-RightNode);return left right ? left 1 : right 1;
}
4.3.6 二叉树查找值为x的结点
当找到的时候返回当前结点的地址没找到则返回NULL如果遍历到空的时候返回NULL // ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTNodeType x)
{if (root NULL){return NULL;}if (root-data x){return root;}BTNode* left BinaryTreeFind(root-LeftNode,x);if (left)return left;BTNode* right BinaryTreeFind(root-RightNode,x);if (right)return right;return NULL;
}
4.3.7 二叉树销毁
销毁操作就不同上面的了如果说遍历到空结点的时候则让他直接跳出该次循环直接进入下一条语句当遍历完LeftNode结点和RightNode结点的时候再free掉当前结点但有一个要注意的是需要改变实参那就要进行传址操作而这里就需要用到二级指针如下代码所示
// ⼆叉树销毁
void BinaryTreeDestory(BTNode** root)
{if ((*root) NULL){return;}BinaryTreeDestory(((*root)-LeftNode));BinaryTreeDestory(((*root)-RightNode));free(*root);*root NULL;
}
4.3.8 层序遍历
层序遍历则需要用到队列这里不需要递归只需要进行入队列打印出队列然后判断左右结点是否为空不为空则插入左结点和右结点
一直循环直到队列为空的时候结束循环。如下代码所示
//层序遍历
void LevelOrder(BTNode* root)
{Queue q;QueueInit(q);QueuePush(q, root);while (!(QueueEmpty(q))){BTNode* front QueueFront(q);printf(%d , front-data);QueuePop(q);if(front-LeftNode)QueuePush(q, front-LeftNode);if(front-RightNode)QueuePush(q, front-RightNode);}QueueDestroy(q);
} 4.3.9 判断是否为完全二叉树
这就是完全二叉树 如果不是完全二叉树则会出现打印空之后还有值如下图所示
如下代码所示
//判断二叉树是否为完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(q);QueuePush(q, root);while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);if (front NULL){break;}QueuePush(q,root-LeftNode);QueuePush(q, root-RightNode);}while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);if (front ! NULL){QueueDestroy(q);return false;}}QueueDestroy(q);return true;
} END
