61树 树形结构是一类重要的非线性结构,树形结构是结 点之间有分支、分层关系的结构 树的定义:树是n(n20)个结点的有限集。 它满足以下两个条件: (1)有且仅有一个特定的称为根的结点。 (2)其余的结点可分为m个互不相交的有限集合T 其中,每个集合又都是一棵树(子 树) 树的表示
6.1 树 树形结构是一类重要的非线性结构，树形结构是结 点之间有分支、分层关系的结构。 ⚫ 树的定义：树是n(n≥0)个结点的有限集。 它满足以下两个条件： （1）有且仅有一个特定的称为根的结点。 （2）其余的结点可分为m个互不相交的有限集合T1 , T2 ,…,Tm，其中，每个集合又都是一棵树（子 树）。 ⚫ 树的表示
61树 结点的度:一个结点的子树个数称为该结点的度。 树的度:一棵树中结点度的最大值。 叶子(终端结点):度为0的结点。 分支结点(非终端结点):度不为0的结点。 内部结点:除根结点之外的分支结点。 孩子:树中某个结点的子树的根称为个结点的孩子 双亲:该结点则为孩子的双亲 兄弟:同一个双亲的孩子 路径:若树中存在一个结点序列k1k2…k,使得k是k+的双亲 (1≤i<j),称该结点序列是从k到的条路径。 祖先:若树中结点k到k存在一条路径,则称k是ks的祖先 子孙:k是k的子孙
6.1 树 结点的度：一个结点的子树个数称为该结点的度。 树的度：一棵树中结点度的最大值。 叶子（终端结点）：度为0的结点。 分支结点（非终端结点）：度不为0的结点。 内部结点：除根结点之外的分支结点。 孩子：树中某个结点的子树的根称为个结点的孩子。 双亲：该结点则为孩子的双亲。 兄弟：同一个双亲的孩子。 路径：若树中存在一个结点序列k1 ,k2 ,…,kj，使得ki是ki+1的双亲 (1≤i<j)，称该结点序列是从k1到kj的一条路径。 祖先：若树中结点k到ks存在一条路径，则称k是ks的祖先。 子孙：ks是k的子孙
61树 层次:结点的层次是从根开始算起(根为1层) 高度:树中结点的最大层次称为树的高度或深度 有序树:若将树中每个结点的各子树看成是从左到右有 秩序的。 无序树:否则称为无序树。 森林:是m(m0棵互不相交的树的集合 (树形结构的逻辑特征可用树中结点之间的父子关系来描 述)
6.1 树 层次：结点的层次是从根开始算起(根为1层)。 高度：树中结点的最大层次称为树的高度或深度。 有序树：若将树中每个结点的各子树看成是从左到右有 秩序的。 无序树：否则称为无序树。 森林：是m(m≥0)棵互不相交的树的集合。 (树形结构的逻辑特征可用树中结点之间的父子关系来描 述)
61树 树的基本操作有下列几种 (1)初始化操作。 (2)求根函数。 3)求双亲函数 (4)求孩子结点函数 (5)求右兄弟函数 (6)建树函数 7)插入子树操作。 (8)删除子树操作。 (9)遍历操作。 (10)清除结构操作
6.1 树 树的基本操作有下列几种： （1）初始化操作。 （2）求根函数。 （3）求双亲函数。 （4）求孩子结点函数。 （5）求右兄弟函数。 （6）建树函数。 （7）插入子树操作。 （8）删除子树操作。 （9）遍历操作。 （10）清除结构操作
62二叉树 概念 ●性质 ●存储结构 遍历 ●线索化
6.2 二叉树 ⚫ 概念 ⚫ 性质 ⚫ 存储结构 ⚫ 遍历 ⚫ 线索化