查看“树(Tree)”的源代码
←
树(Tree)
跳到导航
跳到搜索
因为以下原因,您没有权限编辑本页:
您请求的操作仅限属于该用户组的用户执行:
用户
您可以查看和复制此页面的源代码。
[[category:数据结构]] == 关于“树” == 在计算机科学中,树(tree)是一种抽象数据类型(ADT)。它是由 n(n>0)个有限节点组成一个具有层次关系的集合。 树具有以下的特点: * 每个节点都只有有限个子节点或无子节点; * 没有父节点的节点称为根节点; * 每一个非根节点有且只有一个父节点; * 除了根节点外,每个子节点可以分为多个不相交的子树; * 树里面没有环路(cycle) 术语: * 节点的'''度''':一个节点含有的子树的个数称为该节点的度; * '''树的度''':一棵树中,最大的节点度称为树的度; * 叶节点(终端节点):度为零的节点; * 分支节点(非终端节点):度不为零的节点; * 父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点; * 子节点:一个节点含有的子树的根节点称为该节点的子节点; * 兄弟节点:具有相同父节点的节点互称为兄弟节点; * 其堂兄弟节点:父节点在同一层的节点互为堂兄弟; * 节点的祖先:从根到该节点所经分支上的所有节点; * 子孙:以某节点为根的子树中任一节点都称为该节点的子孙。 * 节点的'''层次''':从根开始定义起,根为第 1 层,根的子节点为第 2 层,以此类推; * '''深度''':从根到节点的唯一路径长。('''根的深度为 0''') * '''高度''':从节点到其树叶的最长路径长。(所有树叶的高度为 0) * 森林:由 m(m>=0)棵互不相交的树的集合称为森林; 树的种类: # 无序树:树中任意节点的子节点之间没有顺序关系,也称为自由树; # 有序树:树中任意节点的子节点之间有顺序关系; ## 二叉树:每个节点最多含有两个子树的树称为二叉树; ### 完全二叉树:对于一棵二叉树,假设其深度为 d(d > 1)。除了第 d 层外,其它各层的节点数目均已达最大值,且第 d 层所有节点从左向右连续地紧密排列; #### 满二叉树:所有叶节点都在最底层的完全二叉树;(最后一层子节点全满的特殊的完全二叉树) ### 平衡二叉树(AVL 树):当且仅当任何节点的两棵子树的高度差不大于 1 的二叉树; ### 排序二叉树(二叉查找树,Binary Search Tree):也称“二叉搜索树”、“有序二叉树”; ## 霍夫曼树:带权路径最短的二叉树称为“哈夫曼树”或“最优二叉树”; ## B 树:一种对读写操作进行优化的'''自平衡的二叉查找树''',能够保持数据有序,拥有'''多于两个子树'''。【???B 树不是二叉树吧???】 == 二叉树 == 在计算机科学中,二叉树(Binary tree)是每个节点最多只有两个分支(即不存在分支度大于 2 的节点)的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序,不能随意颠倒。 * 二叉树的第“i”层至多拥有“2^(i-1)”个节点; * 深度为“k”的二叉树至多总共有“2^(k+1)-1”个节点; 二叉树的遍历: # 深度优先(DFS) ## 先序(根)遍历(DLR) ## 中序(根)遍历(LDR) ## 后序(根)遍历(LRD) # 广度优先(BFS,即:层次遍历) === 排序二叉树 === ---- 排序二叉树, 又称为'''二叉查找树'''。其的特点: * 一个节点左孩子的值, 一定小于它本身节点的值。 * 一个节点右孩子的值, 一定大于它本身节点的值。 * 左、右孩子(子树)也分别是排序二叉树。 *(没有键值相等的结点) 遍历方式的特点:【不同的遍历方式,有着不同的应用场景】 # 先序:复制一个排序二叉树最快。【复制节点或树】 # '''中序''':得到二叉树从小到大排序的数据。【获取序列】 # 后序:执行操作时,肯定已经遍历过该节点的左右子节点,故适用于要进行破坏性操作的情况,比如删除所有节点。【文件系统常用】 排序二叉树体现了'''二分查找'''的思想,'''查找所需的最大次数等于二叉查找树的高度'''。 === 平衡二叉树 === ---- 平衡二叉树(Balanced BinaryTree)又被称为'''AVL树'''。它具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1,并且左右两个子树都是一棵平衡二叉树。 * 平衡因子:节点的两个子树的高度差。(其绝对值必须小于等于 1,否则需要进行调整) ==== 平衡的调整 ==== 平衡的调整通过对节点的旋转实现,共有四种情况:【L、R 代表“导致失衡的子节点”相对于“失衡节点”的位置,而非左旋或右旋的操作】 *(橘黄色的结点为旋转中心,黑色结点的为离插入结点最近的失衡结点) # LL:(左子树的左边节点) #: [[File:平衡二叉树:LL型调整.png|400px]] #: 解决:'''右旋''' # RR:(右子树的右边节点) #: [[File:平衡二叉树:RR型调整.png|400px]] #: 解决:'''左旋''' # LR:(左子树的右边节点) #: [[File:平衡二叉树:LR型调整.png|400px]] #: 解决:'''先左旋再右旋''' # RL:(右子树的左边节点) #: [[File:平衡二叉树:RL型调整.png|400px]] #: 解决:'''先右旋再左旋''' === 红黑树 === * 见:'''“[[树:红黑树]]”'''。 === Treap === * 见:'''“[[树:Treap]]”'''。 == 多叉树 == === 2-3 树 === * 见:'''“[[树:2-3树]]”'''。 === B树 === * 见:'''“[[树:B树]]”'''。 === B+树 === * 见:'''“[[树:B+树]]”'''。 === B*树 === * 见:'''“[[树:B*树]]”'''。 == 空间数据树 == === R树 === * 见:'''“[[树:R树]]”'''。 === R*树 === * 见:'''“[[树:R*树]]”'''。
返回至“
树(Tree)
”。
导航菜单
个人工具
登录
命名空间
页面
讨论
大陆简体
已展开
已折叠
查看
阅读
查看源代码
查看历史
更多
已展开
已折叠
搜索
导航
首页
最近更改
随机页面
MediaWiki帮助
笔记
服务器
数据库
后端
前端
工具
《To do list》
日常
阅读
电影
摄影
其他
Software
Windows
WIKIOE
所有分类
所有页面
侧边栏
站点日志
工具
链入页面
相关更改
特殊页面
页面信息