第六章刺与麝邾 树和森林的概念 二叉树( Binary Tree 二叉树的表示 二叉树遍历( Binary Tree Traversa 线索化二叉树( Threaded Binary Tree 堆(Heap) 树与森林(Tree& Forest) 二叉树的计数 霍夫曼树( Huffman Tree
树和森林的概念 二叉树 (Binary Tree) 二叉树的表示 二叉树遍历 (Binary Tree Traversal) 线索化二叉树 (Threaded Binary Tree) 堆 ( Heap ) 树与森林 (Tree & Forest) 二叉树的计数 霍夫曼树 (Huffman Tree)
树和森林的概念 树的完义 树是由n(n≥0个结点组成的有限集合。如果n 0,称为空树;如果n>0,则 有一个特定的称之为根root的结点,它只有 直接后继,但没有直接前驱; 除根以外的其它结点划分为m(m≥0个互不 相交的有限集合T,T1,…,Tm,每个集合又是一 棵树,并且称之为根的子树( subTree)每棵子树 的根结点有且仅有一个直接前驱,但可以有0个 或多个直接后继
树和森林的概念 树的定义 树是由n (n 0)个结点组成的有限集合。如果n = 0，称为空树；如果n > 0，则 ▪ 有一个特定的称之为根(root)的结点，它只有 直接后继，但没有直接前驱； ▪ 除根以外的其它结点划分为m (m 0)个互不 相交的有限集合T0 , T1 , …, Tm-1，每个集合又是一 棵树，并且称之为根的子树(subTree)。每棵子树 的根结点有且仅有一个直接前驱，但可以有0个 或多个直接后继
root root A Level o (a) eve depth=3 E)(F)(G)(H level 2 level 3 0结点(mode) 0兄弟( ( Sibling)结点有序树 结点的度( degree)祖先 ancestor)结点无序树 分支( branch)结点子孙 descendant)结点·森林 叶(ea结点 0结点所处层次eve) 0子女( child)结点树的高度( depth) 0双亲( parent)结点。树的度( degree)
结点(node) 结点的度(degree) 分支(branch)结点 叶(leaf)结点 子女(child)结点 双亲(parent)结点 兄弟(sibling)结点 祖先(ancestor)结点 子孙(descendant)结点 结点所处层次(level) 树的高度(depth) 树的度(degree) ◼ 有序树 ◼ 无序树 ◼ 森林
树的抽象数据类型 template <class Type>class Tree i public ee e(); position root o; Buildroot( const Type& value ) position First Child( position position Nextsibling( position p, position v ) position Parent( position ) Type Retrieve( position p ) position Insertchild( const position p, const Type &value
template <class Type> class Tree { public: Tree ( ); ~Tree ( ); position Root ( ); BuildRoot ( const Type& value ); position FirstChild ( position p ); position NextSibling ( position p, position v ); position Parent ( position p ); Type Retrieve ( position p ); position InsertChild ( const position p, const Type &value ); 树的抽象数据类型
position Delete child(position p, int i) void Delete Tree(position int IsEmpty (;
position DeleteChild ( position p, int i ); void DeleteSubTree ( position t ); int IsEmpty ( ); }