数据结构——树和二叉树
主讲:张昱 yuzhang@ustc.edu 0551-3603804
1/106
第六章 树和二叉树
重点:二叉树的性质,遍历;二叉树 与森林(树)的相互转换 难点:树和二叉树应用的算法设计
2/106
第六章 树和二叉树
6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.6 赫夫曼树及其应用 6.5 树与等价问题 6.7 回溯法与树的遍历 6.8 树的计数
3/106
6.1 树的定义和基本术语
树的定义(递归定义)
树是n(n≥0)个结点(元素)的有限集. 若 n=0,称为空树. 若 n > 0,则 有且仅有一个特定的称为根的结点root; 当n > 1时,除根以外的其他结点划分为m(m>0) 个互 不相交的有限集T1, T2,… Tm,其中每一个集合本身又是 一棵树,并且称为根的子树. 且对任意的i(m≥i≥1), Ti存在惟一的结点xi , 有 ∈H H为树中元素之间的二元关系集
4/106
6.1 树的定义和基本术语
树的表示
A A E K B F L C G H D I J
6.1 树的定义-其他表示
树的其他表示
嵌套集合,广义表表示,凹入表示 A***************** C G E B F K L A H I D J
B**************** E*************** F*************** K************** L************** C**************** G*************** D**************** H*************** I*************** J***************
(A(B(E, F(K,L)), C(G), D(H, I, J)))
5/106 6/106
6.1 树的定义-基本术语
基本术语
B E F A C G H D I J 第1层 第2层 第3层 第4层 树的度 树的深度/高度 有序树 无序树 森林
8/106
高度为4
K L 结点 结点的度 结点的层次 终端结点(叶子) 非终端结点(分支结点) 内部结点
孩子 双亲 兄弟 祖先 子孙 堂兄弟
7/106
9/106
10/106
6.1 树的定义-ADT Tree
ADT Tree
查找:Parent(T,cur_e) LeftChild(T, cur_e) RightSibling(T, cur_e) 插入:InsertChild(&T, &p, i, c) 删除:DeleteChild(&T, &p, i) 遍历:TraverseTree(T, Visit())
11/106
12/106
6.2 二叉树
二叉树的定义(递归定义)
特点:每个结点至多只有两棵子树,子树有左右之分 二叉树 vs 度不大于2的有序树 ADT BinaryTree
6.2 二叉树-性质(1)

下一页