第六章树与森林 树和森林的概念 二叉树 二叉树遍历 二叉树的计数 堆 树与森林 n霍夫曼树
◼ 树和森林的概念 ◼ 二叉树 ◼ 二叉树遍历 ◼ 二叉树的计数 ◼ 堆 ◼ 树与森林 ◼ 霍夫曼树
树和森林的概念 树的定义 树是由n(n≥0)个结点组成的有限集合。 如果n=0,称为空树;如果n>0,则 有一个特定的称之为根(root)的结点, 它只有直接后继,但没有直接前驱 除根以外的其它结点划分为m(m≥0) 个互不相交的有限集合T。飞根的子树。 91m1 每 个集合又是一棵树,并且称之
树和森林的概念 树的定义 树是由 n (n 0) 个结点组成的有限集合。 如果 n = 0，称为空树；如果 n > 0，则 ▪ 有一个特定的称之为根(root)的结点， 它只有直接后继，但没有直接前驱； ▪ 除根以外的其它结点划分为m (m 0) 个 互不相交的有限集合T0 , T1 , …, Tm-1，每 个集合又是一棵树，并且称之为根的子树
树的特点 每棵子树的根结点有且仅有一个直接前 驱,但可以有0个或多个直接后继。 A 0层 B D -1层 height BOO①“2层 K(L 3层
树的特点 ◼ 每棵子树的根结点有且仅有一个直接前 驱，但可以有0个或多个直接后继。 0层 1层 3层 2层 height = 3 A C G B D E F K L H M I J
结点子女祖先来树的度 结点的度米双亲癥子孙树高度 ※分支结点*兄弟*结点层次*森林 ※叶结点 A 0层 B D -1层 height O-2层3 K(L 3层
0层 1层 3层 2层 height = 3 A C G B D E F K L H M I J 结点 结点的度 分支结点 叶结点 子女 双亲 兄弟 祖先 子孙 结点层次 树的度 树高度 森林
二叉树( Binary Tree 二叉树的定义 一棵二叉树是结点的一个有限集合, 该集合或者为空,或者是由一个根结点加 上两棵分别称为左子树和右子树的、互不 相交的二叉树组成。 R LR 二叉树的五种不同形恋
二叉树 (Binary Tree) 二叉树的定义 二叉树的五种不同形态 一棵二叉树是结点的一个有限集合， 该集合或者为空，或者是由一个根结点加 上两棵分别称为左子树和右子树的、互不 相交的二叉树组成。 L R L R