复旦大学961-数据结构-第二章-树(1)基本概念和术语;树的性质;树的定义;树的遍历
基本概念和术语
- 树:树是n个节点的有限集合
- 空树:n=0时(一个节点都没有),称为空树。
- 根:树最上层的那个节点称为根
- 子树:从树中抽取一个集合,该集合仍是一棵树,则这个树称为该树的子树
- 树的高度(或深度):从根节点算起(包括根节点),树的层数就是树的高度
- 树的节点关系:
- 祖先:从根A到节点K的唯一路径上的任意节点,称为节点K的祖先
- 子孙:若节点K是节点B的祖先,那节点B称为节点K的子孙
- 双亲:父节点。
- 孩子:子节点
- 兄弟:有相同双亲的节点称为兄弟
- 节点的度:一个节点的孩子个数称为该节点的度。
- 树的度:树中节点的最大度数称为树的度
- 分支节点(非终端节点):度大于0的节点称为分支节点(非终端节点)
- 叶子结点(终端节点) :度为0的节点,即没有孩子的节点
- 节点的深度:从根节点开始自顶向下逐层累加的,根节点算1。
- 节点的高度:从叶节点开始自底向上逐层累加的,叶节点算1。
- 有序树:每个节点的左右子树不能随便换
- 无序树:不是有序树,那就是无序树
- 路径:两个节点之间所经过的节点序列就是两个节点之间的路径
- 路径长度:路径上所经过的边的个数
- 森林:多个互不相交的树,组成森林
树的性质
1. 树 中 的 节 点 数 等 于 所 有 节 点 的 度 数 加 1 2. 度 为 m 的 树 第 i 层 上 至 多 有 m i − 1 个 节 点 ( i ≥ 1 ) 3. 高 度 为 h 的 m 叉 树 至 多 有 ( 1 − m h ) ( 1 − m ) 节 点 4. 具 有 n 个 节 点 的 m 叉 树 最 小 高 度 为 ⌈ log m ( n ( m − 1 ) + 1 ) ⌉ \begin{aligned} & 1. 树中的节点数等于所有节点的度数加1 \\ & 2. 度为m的树第i层上至多有m^{i-1}个节点(i\ge1) \\ & 3. 高度为h的m叉树至多有 \frac{(1-m^h)}{(1-m)} 节点 \\ & 4. 具有n个节点的m叉树最小高度为 \lceil \log_m(n(m-1)+1)\rceil \end{aligned} 1.树中的节点数等于所有节点的度数加12.度为m的树第i层上至多有mi−1个节点(i≥1)3.高度为h的m叉树至多有(1−m)(1−mh)节点4.具有n个节点的m叉树最小高度为⌈logm(n(m−1)+1)⌉
树的定义(非二叉树)
public class TreeNode<AnyType> {
AnyType element;
TreeNode<AnyType> firstChild;
TreeNode<AnyType> nextSibling; // sibling: 兄弟姐妹
}
树的遍历(非二叉树)
todo,前序,后序,层序
相关文章
- x64驱动 遍历驱动模块
- 数据结构:二叉树(前,中,后,层次)非递归遍历。
- HTML5 本地存储 localStorage、sessionStorage 的遍历、存储大小限制处理
- [译]聊聊C#中的泛型的使用(新手勿入) Seaching TreeVIew WPF 可编辑树Ztree的使用(包括对后台数据库的增删改查) 字段和属性的区别 C# 遍历Dictionary并修改其中的Value 学习笔记——异步 程序员常说的「哈希表」是个什么鬼?
- C/C++的readdir和readdir_r函数(遍历目录)
- 1155 Heap Paths (30 分)【难度: 一般 / 知识点: 堆 堆的遍历】
- 【Web漏洞探索】目录遍历漏洞
- 数据结构 有序树转二叉树 (树的遍历)
- 用php实现遍历目录
- Java Map各遍历方式的性能比较
- java遍历树(深度遍历和广度遍历
- CentOS下递归遍历文件夹下所有文件,查找指定字符
- Map中使用和遍历map方法
- Unity 基础 之 实现枚举(enum/Enum)遍历的三种简单方法(foreach/for)
- 《剑指offer》17:二叉搜索树的后序遍历
- iOS - 遍历指定路径下的所有文件(不包括更下级文件)
- [LeetCode] 987. Vertical Order Traversal of a Binary Tree 竖直遍历二叉树
- LeetCode根据前序与中序、中序与后序,前序与后序遍历序列构建二叉树
- 33数据结构与算法分析之---图的遍历
- leetcode 106. Construct Binary Tree from Inorder and Postorder Traversal 从中序与后序遍历序列构造二叉树(中等)
- 算法补天系列之——中级提高班-2(树的递归,动态规划,调整遍历方向减少复杂度)