408数据结构学习笔记-树-①树的逻辑结构①定义②结点间的关系描述③结点路径④结点，树的属性描述⑤有序树和无序树⑥森林⑦树的性质（6个性质）

目录

①定义

②结点间的关系描述

③结点路径

④结点，树的属性描述

⑤有序树和无序树

⑥森林

⑦树的性质（6个性质）

a.结点数=总度数+1

b.度为m的树和m叉树的区别

c.度为m的树第i层至多有

个结点

d.高度为h的m叉树至多有

个结点

e.高度为h的m叉树至少有h个结点

f.具有n个结点的m叉树的最小高度为

选择题中有涉及的有关树的性质：

1. 一颗树的总结点数=总度数(或总边数)+1——P78-8
2. 度为m的树T，其叶子结点个数n0=1+

①定义

• 非空树的定义：

• • 仅有一个根结点
  • 叶子结点：没有后继的结点
  • 分支结点：有后继的结点
  • 除了根结点，每个结点都有且仅有一个前驱

②结点间的关系描述

如：以家族族谱关系描述

• TND双亲也是™祖先结点。

③结点路径

• 路径：两个结点之间的距离（只能从上往下数）
• 结点路径：经过几条线路径就是多少，没有单位

④结点，树的属性描述

• 树的层次：根结点为第1层，其子树的根结点为第2层，从上到下
• 树的深度（从上往下数）：树的最大层次数
• 树的高度（从下往上）
• 结点的度：这个结点有几个孩子？即，这个结点有几个分支（子树的个数）

• • 我们常说的度数指的是结点的度数
  • 叶子结点的度=0
  • 分子结点的度≥1

• 树的度：各个结点的度的最大值

⑤有序树和无序树

• 使用有序树还是无序树，具体看你使用树来存放什么数据，是否需要用结点的左右位置反应某些逻辑关系
• 定义：

• • 有序树：各个结点的各子树从左到右都是有次序的，不可交换

• • • 如：家庭的族谱。从左到右一般按出生顺序来排列，如下

    • 

    • 如果交换了次序，岂不是乱了套。

• • 无序树：各个结点的各子树从左到右都是无次序的，可以交换

• • • 如：国家的行政区分布。

    • 

    • 各个省份间没有排序的必要（感觉有，应该按首拼音顺序）

⑥森林

• 定义：多个（m≥0）互不相交的树的集合

• • 多个树组成一个森林
  • 森林也可以没有树，为空森林

• 

• 如果让这些树连上同一个根结点，森林变成了一个树

• 

⑦树的性质（6个性质）

a.结点数=总度数+1

• 可以发现：一棵树，它的结点数=总的边树+1

• • 说明，度数和边数是等同的。

b.度为m的树和m叉树的区别

c.度为m的树第i层至多有

个结点

d.高度为h的m叉树至多有

个结点

• 实际是个等比求和公式

• 

e.高度为h的m叉树至少有h个结点

• 对应：高度为h，度为m的树至少有h+m-1个结点

• 

f.具有n个结点的m叉树的最小高度为

最后

以上就是粗犷睫毛膏为你收集整理的408数据结构学习笔记-树-①树的逻辑结构①定义②结点间的关系描述③结点路径④结点，树的属性描述⑤有序树和无序树⑥森林⑦树的性质（6个性质）的全部内容，希望文章能够帮你解决408数据结构学习笔记-树-①树的逻辑结构①定义②结点间的关系描述③结点路径④结点，树的属性描述⑤有序树和无序树⑥森林⑦树的性质（6个性质）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。