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