开发一个网站的过程是什么,中国建设教育网官网,网页模板模板王,推荐做ppt照片的网站1、树
1.1 树的相关概念 节点的度#xff1a;一个节点含有的子树的个数称为该节点的度#xff1b; 如上图#xff1a;A的为6
叶节点或终端节点#xff1a;度为0的节点称为叶节点#xff1b; 如上图#xff1a;B、C、H、I...等节点为叶节点
非终端节点或分支节点#…1、树
1.1 树的相关概念 节点的度一个节点含有的子树的个数称为该节点的度 如上图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.2 树的表示
树结构相对线性表就比较复杂了要存储表示起来就比较麻烦了既然保存值域也要保存结点和结点之间 的关系实际中树有很多种表示方式如双亲表示法孩子表示法、孩子双亲表示法以及孩子兄弟表示法 等。其中最常用的是孩子兄弟表示法。 typedef int DataType;struct Node{struct Node* _firstChild1; // 第一个孩子结点 struct Node* _pNextBrother; // 指向其下一个兄弟结点 DataType _data; // 结点中的数据域 };
2.二叉树概念及结构
2.1概念
一棵二叉树是结点的一个有限集合该集合:
1. 或者为空
2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成 1. 二叉树不存在度大于2的结点 2. 二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树 2.2特殊的二叉树 1. 满二叉树一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉树。也就是 说如果一个二叉树的层数为K且结点总数是则它就是满二叉树。 满二叉树每一层都是满的结点个数为2^h-1 2. 完全二叉树完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为K 的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对 应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。 完全二叉树前n-1层都是满的最后一层可以不满但是从左到右是连续的结点范围[2^(h-1), 2^h-1] 2.3 二叉树的性质
1. 若规定根节点的层数为1则一棵非空二叉树的第i层上最多有 个结点2^(i-1).
2. 若规定根节点的层数为1则深度为h的二叉树的最大结点数是2^h-1.
3. 对任何一棵二叉树, 如果度为0其叶结点个数为 n0 , 度为2的分支结点个数为n0n21.
4. 若规定根节点的层数为1具有n个结点的满二叉树的深度h ,则有 . (ps 1 是log以2 为底n1为对数)
5. 对于具有n个结点的完全二叉树如果按照从上至下从左至右的数组顺序对所有节点从0开始编号则对 于序号为i的结点有 1. 若i0i位置节点的双亲序号(i-1)/2i0i为根节点编号无双亲节点 2. 若2i1n否则无左孩子 3. 若2i2n否则无右孩子
3.二叉树的顺序结构及实现
3.1 二叉树的顺序结构
普通的二叉树是不适合用数组来存储的因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结 构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储需要注意的是这里的堆和操作系统 虚拟进程地址空间中的堆是两回事一个是数据结构一个是操作系统中管理内存的一块区域分段。
3.2 堆的概念及结构
一个集合所有元素按完全二叉树的顺序存储方式存储在一个一维数组中堆中某个节点的值总是小于或等于其父节点的值是大堆堆中某个节点的值总是大于或等于其父节点的值是小堆。
3.3 堆的实现
#include Heap.hvoid HPInit(HP* php)
{assert(php);php-a (Datatype*)malloc(sizeof(Datatype) * 4);if (php-a NULL){perror(malloc fail);return;}php-size 0;php-capacity 4;
}void HPInitArray(HP* php, int* a, int n)
{assert(php);php-a (Datatype*)malloc(sizeof(Datatype) * n);if (php-a NULL){perror(malloc fail);return;}php-size n;php-capacity n;for (int i (n - 1 - 1) / 2; i 0; i){AdjustDown(php-a, php-size, i);}
}void HPDestroy(HP* php)
{assert(php);free(php-a);php-a NULL;php-size 0;php-capacity 0;
}void Swap(Datatype* p1, Datatype* p2)
{Datatype tmp p1;*p1 *p2;*p2 tmp;
}//除了child前面的数据都构成堆
void AdjustUp(Datatype* a, int child)
{int parent (child - 1) / 2;while (child 0){if (a[child] a[parent])// 大堆{Swap(a[child], a[parent]);child parent;parent (child - 1) / 2;}else{break;}}
}//左右子树都构成大堆或小堆
void AdjustDown(Datatype* 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;}}}void HPPush(HP* php, Datatype x)
{assert(php);if (php-size php-capacity){Datatype* tmp (Datatype*)realloc(php-a, sizeof(Datatype)*php-capacity*2);if (tmp NULL){perror(realloc fail);return;}php-a tmp;php-capacity * 2;}php-a[php-size] x;php-size;AdjustUp(php-a, php-size - 1);
}void HPPop(HP* php)
{assert(php);assert(!PHEmpty(php));//和最后一个数据交换Swap(php-a[0], php-a[php-size - 1]);php-size--;AdjustDown(php-a, php-size - 1, 0);}Datatype HPTop(HP* php)
{assert(php);return php-a[0];
}bool HPEmpty(HP* php)
{assert(php);return php-size 0;
}int HPSize(HP* php)
{assert(php);return php-size;
}//堆排序--升序--建大堆
void HPSort(int* a, int n)
{建堆--向上调整--O(NlogN)//for (int i 1; i n; i)//{// AdjustUp(a, i);//}//建堆--向下调整--O(N)for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(a, n, i);}//实现排序--O(NlogN)int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);end--;}
}
