第五章树 树和森林的概念 二叉树 二叉树遍历 线索化二叉树 树与森林 堆 Huffman树
第五章 树 • 树和森林的概念 • 二叉树 • 二叉树遍历 • 线索化二叉树 • 树与森林 • 堆• Huffman树 1
树和森林的概念 有根树: ◆一棵有根树T,简称为树,它是n(n≥0)个结点 的有限集合。当n=0时,T称为空树;否则,T 是非空树。记作 =0 T Ir, I, I3.Tm 3, n>0 ◆r是一个特定的称为根(root)的结点,它只有直 接后继,没有直接前驱 ◆根以外的其他结点划分为m(m≥0)个互不相交 的有限集合T,T2,…,Tm,每个集合又是一棵树, 并且称为根的子树
树和森林的概念 • 有根树： ◆ 一棵有根树T，简称为树，它是n (n ≥ 0) 个结点 的有限集合。当n = 0时，T 称为空树；否则，T 是非空树。记作 ◆ r 是一个特定的称为根 (root) 的结点，它只有直 接后继，没有直接前驱 ◆ 根以外的其他结点划分为 m (m 0) 个互不相交 的有限集合T1 , T2 , …, Tm，每个集合又是一棵树， 并且称为根的子树 = = 0 0 r,T ,T ,...,T , n , n T 1 2 m { } Φ 2
◆每棵子树的根结点有且仅有一个直接前驱 但可以有0个或多个直接后继 B C E@④ K(L
◆ 每棵子树的根结点有且仅有一个直接前驱， 但可以有0个或多个直接后继 3 D A B C E F G H I J K L M
树的基本术语 子女:若结点的子树非空,结点子树的根即 为该结点的子女。 双亲(父亲):若结点有子女,该结点是子 女的双亲(父亲)。 兄弟:同一结点的子女互称为兄弟 度:结点的子女个数即为该结点的度;树中 各个结点的度的最大值称为树的度
树的基本术语 • 子女：若结点的子树非空，结点子树的根即 为该结点的子女。 • 双亲（父亲）：若结点有子女，该结点是子 女的双亲（父亲）。 • 兄弟：同一结点的子女互称为兄弟。 • 度：结点的子女个数即为该结点的度；树中 各个结点的度的最大值称为树的度。 4
分支结点:度不为0的结点即为分支结点, 亦称为非终端结点。 叶结点:度为0的结点即为叶结点,亦称为 终端结点。 祖先:根结点到该结点的路径上的各个结点 都是该结点的祖先。 子孙:某结点的所有下属结点,都是该结点 的子孙
• 分支结点：度不为0的结点即为分支结点， 亦称为非终端结点。 • 叶结点：度为0的结点即为叶结点，亦称为 终端结点。 • 祖先：根结点到该结点的路径上的各个结点 都是该结点的祖先。 • 子孙：某结点的所有下属结点，都是该结点 的子孙。 5
结点的层次:规定根结点在第一层,其子女 结点的层次等于它的层次加一。以下类推。 结点的深度:结点的深度即为结点的层次; 离根最远结点的层次即为树的深度。 A l层 B)(C①D 2层 depth height E)(F)(G)(H 3层 K( M 4层
• 结点的层次：规定根结点在第一层，其子女 结点的层次等于它的层次加一。以下类推。 • 结点的深度：结点的深度即为结点的层次； 离根最远结点的层次即为树的深度。 1层 2层 4层 3层 depth = 4 D A B C E F G H I J K L M height = 4 6
结点的高度:规定叶结点的高度为1,其双亲结 点的高度等于它的高度加一 树的高度:等于根结点的高度,即根结点所有 子女高度的最大值加一。 有序树:树中结点的各棵子树T1,T2,,是有次 序的,即为有序树。 无序树:树中结点的各棵子树之间的次序是不 重要的,可以互相交换位置。 森林:森林是m(m0)棵树的集合
• 结点的高度：规定叶结点的高度为1，其双亲结 点的高度等于它的高度加一。 • 树的高度：等于根结点的高度，即根结点所有 子女高度的最大值加一。 • 有序树：树中结点的各棵子树 T1 , T2 , …是有次 序的，即为有序树。 • 无序树：树中结点的各棵子树之间的次序是不 重要的，可以互相交换位置。 • 森林：森林是m（m≥0）棵树的集合。 7
树的抽象数据类型 template class tree i /对象:树是由mC>0)个结点组成的有限集合。在 类界面中的 position是树中结点的地址。在顺序 /存储方式下是下标型,在链表存储方式下是指针 /型。T是树结点中存放数据的类型,要求所有结 ∥点的数据类型都是一致的。 ublic: p Tree o; cTree o
树的抽象数据类型 template class Tree { //对象: 树是由n (≥0) 个结点组成的有限集合。在 //类界面中的 position 是树中结点的地址。在顺序 //存储方式下是下标型, 在链表存储方式下是指针 //型。T 是树结点中存放数据的类型, 要求所有结 //点的数据类型都是一致的。 public: Tree (); ~Tree (); 8
Buildroot(const T& value); ∥/建立树的根结点 position FirstChild(position p) ∥)回p第一个子女地址,天子女返回0 position NextSib ing(position p ∥回p下一兄弟地址,若天下一兄弟返回0 position Parent(position p); 回p双亲结点地址,若p为根返回0 T GetData(position p) ∥回结点卩中存放的值 bool InsertChild(position p, t& value); 在结点p下插入值为 value的新子女,若插 /失败。函数返回fale,否则返回true
BuildRoot (const T& value); //建立树的根结点 position FirstChild(position p); //返回 p 第一个子女地址, 无子女返回 0 position NextSibling(position p); //返回 p 下一兄弟地址, 若无下一兄弟返回 0 position Parent(position p); //返回 p 双亲结点地址, 若 p 为根返回 0 T GetData(position p); //返回结点 p 中存放的值 bool InsertChild(position p, T& value); //在结点 p 下插入值为 value 的新子女, 若插 //入失败, 函数返回false, 否则返回true 9
bool Delete Child(position p, int i ∥除结点p的第i个子女及其全部子孙结 ∥点,若删除失败,则返回 false,否则返回true void Delete Sub Tree(position t) /删除以t为根结点的子树 bool Isempty o /判树空否若空则返回true.否则返回 false void Traversal (void (visit)(position p)) ∥遍历以p为根的子树
bool DeleteChild (position p, int i); //删除结点 p 的第 i 个子女及其全部子孙结 //点, 若删除失败, 则返回false, 否则返回true void DeleteSubTree (position t); //删除以 t 为根结点的子树 bool IsEmpty (); //判树空否, 若空则返回true, 否则返回false void Traversal (void (*visit)(position p)); //遍历以 p 为根的子树 }; 10