第六章树与森林 树和森林的概念 二叉树 树遍历 叉树的计数 线索化二叉树 堆 与森休 霍夫曼树
◼ 树和森林的概念 ◼ 二叉树 ◼ 二叉树遍历 ◼ 二叉树的计数 ◼ 线索化二叉树 ◼ 堆 ◼ 树与森林 ◼ 霍夫曼树
树和森林的概念 树的定义 树是由n(≥0)个结点组成的有限集合。 如果n=0,称为空树;如果n>0,则 有一个特定的称之为根(root)的结点, 它只有直接后继,但没有直接前驱 除根以外的其它结点划分为m(m≥0) 个互不相交的有限集合TT,…,Tm1,每 个集合又是一棵树,并且称之为根的子树
树和森林的概念 树的定义 树是由 n (n 0) 个结点组成的有限集合。 如果 n = 0，称为空树；如果 n > 0，则 ▪ 有一个特定的称之为根(root)的结点， 它只有直接后继，但没有直接前驱； ▪ 除根以外的其它结点划分为m (m 0) 个 互不相交的有限集合T0 , T1 , …, Tm-1，每 个集合又是一棵树，并且称之为根的子树
树的特点 每棵子树的根结点有且仅有一个直接前 驱,但可以有0个或多个直接后继。 A 0层 B D l层 height O-2层3 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 l层 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 结点 结点的度 分支结点 叶结点 子女 双亲 兄弟 祖先 子孙 结点层次 树的度 树高度 森林
树的抽象数据类型 template <class Type> class Tree t /对象:树是由n(0)个结点组成的有限集 /合。在类界面中的 position是树中结点的 /地址。在顺序存储方式下是下标型,在链 /表存储方式下是指针型。Type是树结点中 存放数据的类型。 public Tree (; caree()
template <class Type> class Tree { //对象: 树是由n(≥0)个结点组成的有限集 //合。在类界面中的position是树中结点的 //地址。在顺序存储方式下是下标型, 在链 //表存储方式下是指针型。Type是树结点中 存放数据的类型。 public: Tree ( ); ~Tree ( ); 树的抽象数据类型