网站备案账号是什么情况,建设淘宝客网站源码怎么弄,网站推广话术,wordpress新闻小程序目录 1.树1.基本概念1.空树2.非空树 2.基本术语1.结点之间的关系描述2.结点、树的属性描述3.有序树、无序树4.森林 3.树的常考性质 2.二叉树1.基本概念2.特殊二叉树1.满二叉树2.完全二叉树3.二叉排序树4.平衡二叉树 3.常考性质4.二叉树的存储结构1.顺序存储2.链式存储 1.树
1.… 目录 1.树1.基本概念1.空树2.非空树 2.基本术语1.结点之间的关系描述2.结点、树的属性描述3.有序树、无序树4.森林 3.树的常考性质 2.二叉树1.基本概念2.特殊二叉树1.满二叉树2.完全二叉树3.二叉排序树4.平衡二叉树 3.常考性质4.二叉树的存储结构1.顺序存储2.链式存储 1.树
1.基本概念 树是n (n0个结点的有限集合n 0时称为空树这是一种特殊情况。 在任意一棵非空树中应满足: ①有且仅有一个特定的称为根的结点。 ②当n1时其余结点可分为m (m0个互不相交的有限集合T1,T2…… Tm其中每个集合本身又是一棵树并且称为根结点的子树。 ③树是一种递归定义的数据结构。 1.空树 结点数为0的树。 2.非空树 ①有且仅有一个根节点 ②没有后继的结点称为“叶子结点”(或终端结点) ③有后继的结点称为“分支结点”(或非终端结点 ④除了根节点外任何一个结点都有且仅有一个前驱 ⑤每个结点可以有0个或多个后继。 2.基本术语
1.结点之间的关系描述 ①祖先结点 ②子孙结点 ③双亲结点父节点 ④孩子结点 ⑤兄弟结点 ⑥堂兄弟结点 ⑦路径只能从上而下 ⑧路径长度经过几条边 2.结点、树的属性描述 ①结点的层次深度)从上往下数默认从1开始) ②结点的高度从下往上数 ③树的高度深度总共多少层 ④结点的度有几个孩子分支) ⑤树的度各结点的度的最大值 3.有序树、无序树 ①有序树――逻辑上看树中结点的各子树从左至右是有次序的不能互换 ②无序树――逻辑上看树中结点的各子树从左至右是无次序的可以互换 4.森林 森林是m ( m≥0棵互不相交的树的集合。 3.树的常考性质 ①结点数总度数1 ②度为m的树、m叉树的区别 树的度各结点的度的最大值 m叉树每个结点最多只能有m个孩子的树 ③度为m的树第i层至多有 m i − 1 m^{i-1} mi−1个结点( i≥1) ④高度为h的m叉树至多有 m h − 1 m − 1 \frac{m^h-1}{m-1} m−1mh−1个结点。(等比数列求和) ⑤高度为h的m叉树至少有h个结点。 高度为h、度为m的树至少有hm-1个结点。 ⑥具有n个结点的m叉树的最小高度为 [ l o g m ( n ( m − 1 ) 1 ) ] [log_m^{(n(m - 1) 1)}] [logm(n(m−1)1)](向上取整) 2.二叉树
1.基本概念 二叉树是n (n≥0个结点的有限集合: ①或者为空二叉树即n 0。 ②或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。 左子树和右子树又分别是一棵二叉树。 特点:①每个结点至多只有两棵子树②左右子树不能颠倒(二叉树是有序树) 2.特殊二叉树
1.满二叉树 一棵高度为h且含有 2 h − 1 2^h-1 2h−1个结点的二叉树 特点: ①只有最后一层有叶子结点 ②不存在度为1的结点 ③按层序从1开始编号结点i的左孩子为2i右孩子为2i1; 结点i的父节点为[i/2] (向下取整) 2.完全二叉树 当且仅当其每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时称为完全二叉树。 特点: ①只有最后两层可能有叶子结点 ②最多只有一个度为1的结点 ③按层序从1开始编号结点i的左孩子为2i右孩子为2i1; ④i≤ [n/2]为分支结点i[n/2]为叶子结点(向下取整) 3.二叉排序树 一棵二叉树或者是空二叉树或者是具有如下性质的二叉树: 左子树上所有结点的关键字均小于根结点的关键字; 右子树上所有结点的关键字均大于根结点的关键字。 左子树和右子树又各是一棵二叉排序树。(左小右大) 二叉排序树可用于元素的排序、搜索。 4.平衡二叉树 树上任一结点的左子树和右子树的深度之差不超过1。 平衡二叉树能有更高的搜索效率。 3.常考性质 ①:设非空二叉树中度为0、1和2的结点个数分别为n0,n1,和n2则n0 n2 1。(叶子结点比二分支结点多一个) 树的结点数总度数1 ②二叉树第i层至多有 2 i − 1 2^{i-1} 2i−1个结点 i≥1) ③高度为h的二叉树至多有 2 h — 1 2^h —1 2h—1个结点满二叉树) ④具有n个(n 0结点的完全二叉树的高度h为 [ l o g 2 ( n 1 ) ] ( 向上取整 ) 或 [ l o g 2 n ] 1 向下取整 [log_2^{(n 1)}](向上取整)或[log_2^n] 1向下取整 [log2(n1)](向上取整)或[log2n]1向下取整 ⑤若完全二叉树有2k个偶数个结点则必有n11n0 k, n2 k-1 若完全二叉树有2k-1个奇数个结点则必有n10n0 k, n2 k-1. 4.二叉树的存储结构
1.顺序存储 二叉树的顺序存储中一定要把二叉树的结点编号与完全二叉树对应起来。 利用完全二叉树父节点与孩子结点的关系存放在指定数组下标。 最坏情况:高度为h 且只有h个结点的单支树所有结点只有右孩子也至少需要 2 h − 1 2^h-1 2h−1个存储单元。 结论:二叉树的顺序存储结构只适合存储完全二叉树。 2.链式存储 n个结点的二叉链表共有n1个空链域。 使用三叉链表――方便找父结点。
