复旦大学961-数据结构-第二章-树（1）基本概念和术语；树的性质；树的定义；树的遍历

待我称王封你为后i 2022-12-11 12:19 145阅读 0赞

[961全部内容链接][961]

### 文章目录 ###

*  基本概念和术语
 *  树的性质
 *  树的定义（非二叉树）
 *  树的遍历（非二叉树）

# 基本概念和术语 #

1.  树：树是n个节点的有限集合
2.  空树：n=0时（一个节点都没有），称为空树。
3.  根：树最上层的那个节点称为根
4.  子树：从树中抽取一个集合，该集合仍是一棵树，则这个树称为该树的子树
5.  树的高度（或深度）：从根节点算起（包括根节点），树的层数就是树的高度
6.  树的节点关系：
    
     *  祖先：从根A到节点K的唯一路径上的任意节点，称为节点K的祖先
     *  子孙：若节点K是节点B的祖先，那节点B称为节点K的子孙
     *  双亲：父节点。
     *  孩子：子节点
     *  兄弟：有相同双亲的节点称为兄弟
7.  节点的度：一个节点的孩子个数称为该节点的度。
8.  树的度：树中节点的最大度数称为树的度
9.  分支节点（非终端节点）：度大于0的节点称为分支节点（非终端节点）
10. 叶子结点（终端节点） ：度为0的节点，即没有孩子的节点
11. 节点的深度：从根节点开始自顶向下逐层累加的，根节点算1。
12. 节点的高度：从叶节点开始自底向上逐层累加的，叶节点算1。
13. 有序树：每个节点的左右子树不能随便换
14. 无序树：不是有序树，那就是无序树
15. 路径：两个节点之间所经过的节点序列就是两个节点之间的路径
16. 路径长度：路径上所经过的边的个数
17. 森林：多个互不相交的树，组成森林

# 树的性质 #

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，前序，后序，层序

[961]: https://blog.csdn.net/zhaohongfei_358/article/details/111414370