第6章树和森林 非线性数据结构 实际中有许多树型结构的问题,用树型数据结构来解决非常自然 树型结构在计算机领域的应用非常广泛 .1树和森林的概念 树的定义: 树是由n(n>=0)个结点组成的有限集合。若n=0则称为空树, 否则 (1)有一个特定的称之为根(root)的结点,它只有直接后继, 但没有直接前驱; (2)除根以外的其他结点可划分为若干个互不相交的有限集合, 每个集合又是一棵树,并且称之为根的子树( sub tree)。每 棵子树的根结点有且仅有一个直接前驱,但可以有0个或多 个直接后继。 2021220
2021/2/20 1 第6章 树和森林 非线性数据结构 实际中有许多树型结构的问题，用树型数据结构来解决非常自然 树型结构在计算机领域的应用非常广泛 6.1 树和森林的概念 树的定义： 树是由 n ( n>=0 ) 个结点组成的有限集合。若 n = 0 则称为空树， 否则： （1）有一个特定的称之为根( root )的结点，它只有直接后继， 但没有直接前驱； （2）除根以外的其他结点可划分为若干个互不相交的有限集合， 每个集合又是一棵树，并且称之为根的子树( subTree )。每 棵子树的根结点有且仅有一个直接前驱，但可以有0个或多 个直接后继
树的示意图: 结点 电点 分支结点 结点的层次 Level 0 子树 Level 1 eve 子树 子树| Level3 2021220
2021/2/20 2 树的示意图： 根 结 点 根结点 叶结点 分支结点 子树 子树 子树 Level 0 Level 1 Level 2 Level 3 结点的层次
树的基本术语 结点的度( degree):结点所拥有的子树数目 子女( child)结点:简称子结点 双亲( parent)结点:简称父结点( father) 兄弟( sibling)结点:具有同一个父结点的结点 根(root)结点 分支( branch)结点:又称非终端结点 叶(leaf)结点:又称终端结点 结点的层次(1eve):根结点的层次为0,子结点的层次等于其父结 点的层次加一 树的高度( depth):等于树中最大的结点层次数。空树的高度为-1 树的度( degree):等于树中最大的结点度数 有序树:树中结点的各子树之间的先后次序是有意乂的,不能互换, 否则就成为另一棵树了。 无序树:树中结点的各子树之间的先后次序无意乂,可以互换 森林( forest):若干棵树的集合 2021220
2021/2/20 3 树的基本术语 结点的度( degree )：结点所拥有的子树数目 子女( child ) 结点：简称子结点 双亲( parent) 结点：简称父结点( father ) 兄弟( sibling)结点：具有同一个父结点的结点 根( root ) 结点： 分支( branch )结点：又称非终端结点 叶( leaf ) 结点：又称终端结点 结点的层次( level ):根结点的层次为0，子结点的层次等于其父结 点的层次加一 树的高度( depth ):等于树中最大的结点层次数。空树的高度为－1 树的度( degree ):等于树中最大的结点度数 有序树：树中结点的各子树之间的先后次序是有意义的，不能互换， 否则就成为另一棵树了。 无序树：树中结点的各子树之间的先后次序无意义，可以互换 森林( forest ):若干棵树的集合
62二又树( Binary Tree 叉树是树的基础,一般的树可以转化为二叉树来处理。 62.1二叉树的定义 棵二叉树是一有限结点的集合,该集合或者为空(空二叉 树),或者是由一个根结点及其下的两棵互不相交的子二叉树构 成,其中左边的称为左子树,右边的称为右子树。 二叉树是一棵度数<=2的有序树。 6,2.2二叉树的性质 )二叉树的第i层的结点数<=2 (2)高度为k的二叉树的最大结点数=2k+1 (k>=-1) 满二叉树( Full Binary Tree):叶结点在同一层,非叶结点的度数均 为2的二叉树(参见图6.3a) 完全二叉树( Complete Binary Tree):按从上到下、从左到右顺序 编号一棵满二叉树,并按从大到小的顺序连续删除 该满二叉树的若干个结点后剩下的二叉树称为一棵 完全二叉树(参见图6.3b) 2021220
2021/2/20 4 6.2 二叉树( Binary Tree ) 二叉树是树的基础，一般的树可以转化为二叉树来处理。 6.2.1 二叉树的定义 一棵二叉树是一有限结点的集合，该集合或者为空（空二叉 树），或者是由一个根结点及其下的两棵互不相交的子二叉树构 成，其中左边的称为左子树，右边的称为右子树。 二叉树是一棵度数<= 2 的有序树。 6.2.2 二叉树的性质 （1）二叉树的第i 层的结点数<= （2）高度为k 的二叉树的最大结点数＝ ( k >= -1) 满二叉树( Full Binary Tree )：叶结点在同一层，非叶结点的度数均 为 2 的二叉树（参见图6.3a ） 完全二叉树( Complete Binary Tree )： 按从上到下、从左到右顺序 编号一棵满二叉树，并按从大到小的顺序连续删除 该满二叉树的若干个结点后剩下的二叉树称为一棵 完全二叉树（参见图6.3b ） 2 i 2 k+1 - 1
完全二叉树的性质和顺序存储结构 (1)具有n个结点的完全二叉树的高度=log2(n+1) (2)若将一棵按前述原则编号的完全二叉树,按其编号顺序存入 个一维数组中,则有 结点i的左子结点下标=2*i+1<n 结点i的右子结点下标=2*i+2<n 结点i的父结点下标=(i-1)/2的下取整值 另外注意:根结点(下标为0)无父结点 由上可知,完全二叉树的父—左子、父—右子之间的 关系可以通过相应结点的下标之间的简单数学关系完全地表示 出来,因此可以采用顺序存储结构来存储完全二叉树。(参见 教材6.3.1数组表示 顺序存储结构用于动态性较小的完全二叉树的存储不失为 种简单有效的方法,但不通用。树型数据结构一般采用链式存 储方式来存储。 2021220
2021/2/20 5 完全二叉树的性质和顺序存储结构 （1）具有n 个结点的完全二叉树的高度= log2 ( n + 1 ) – 1 （2）若将一棵按前述原则编号的完全二叉树，按其编号顺序存入一 个一维数组中，则有： 结点 i 的左子结点下标= 2* i + 1 < n 结点 i 的右子结点下标= 2* i + 2 < n 结点 i 的父结点下标= ( i – 1 ) / 2 的下取整值 另外注意：根结点（下标为0）无父结点 由上可知，完全二叉树的父——左子、父——右子之间的 关系可以通过相应结点的下标之间的简单数学关系完全地表示 出来，因此可以采用顺序存储结构来存储完全二叉树。（参见 教材 6.3.1 数组表示） 顺序存储结构用于动态性较小的完全二叉树的存储不失为 一种简单有效的方法，但不通用。树型数据结构一般采用链式存 储方式来存储