0树的基本操作 第六章树和三叉树 ()建树函数 Create tree(xF) 生成一棵以x结点为根,以森林F为子树森林的树 (7)插入子树操作 InsChild(y,i,x) 置以结点ⅹ为根的树为结点y的第棵子树。若原树中无结点y, 或结点y的子树个数小于1,则为空操作 (8)删除子树操作 Delchild(xi) 删除结点x的第i棵子树。若无结点x或结点x的子树个数小于i, 则为空操作。 (9)树的遍历操作 Traverse(D 按某个次序依次访问树中各个结点,并使每个结点只被访问三 次 (I0)清除树的结构操作 Clear(T 将树置为空树 注.树的抽象数据类型可随需要而设定 第16页
第六章 树和二叉树 第16页 (6) 建树函数 CreateTree(x,F) 生成一棵以x结点为根，以森林F为子树森林的树。 (7) 插入子树操作 InsChild(y,i,x) 置以结点x为根的树为结点y的第i棵子树。若原树中无结点y， 或结点y的子树个数小于i-1，则为空操作。 (8) 删除子树操作 DelChild(x,i) 删除结点x的第i棵子树。若无结点x或结点x的子树个数小于i， 则为空操作。 (9) 树的遍历操作 Traverse(T) 按某个次序依次访问树中各个结点，并使每个结点只被访问 一次。 (10) 清除树的结构操作 Clear(T) 将树置为空树。 注. 树的抽象数据类型可随需要而设定。 ⚫ 树 的 基 本 操 作
第六章树和三叉树 0二又树的定义与基本操作 叉树是树型结构的另一个重要类型,许多实际间题 抽象出来的数据结构往往是二叉树的形式,即使是一般的 树也能简单地转换为二叉树,而且二叉树的存储结构及其 算法都较为简单,因此,二叉树显得特别重要。 二叉树的定义 定义(二叉树的递归定义)二叉树( binary tree)是结 的一个有限集合,这个集合或是空集,或是由一个根结 点及两棵分别称为根结点的左子树和右子树的互不相交的 二叉树组成 第17页
第六章 树和二叉树 第17页 二叉树是树型结构的另一个重要类型，许多实际问题 抽象出来的数据结构往往是二叉树的形式，即使是一般的 树也能简单地转换为二叉树，而且二叉树的存储结构及其 算法都较为简单，因此，二叉树显得特别重要。 二叉树的定义 定义（二叉树的递归定义）二叉树 (binary tree)是结 点的一个有限集合，这个集合或是空集，或是由一个根结 点及两棵分别称为根结点的左子树和右子树的互不相交的 二叉树组成。 ⚫ 二叉树的定义与基本操作
二叉树的五种基本形态 第六章树和三叉树 由于二叉树递归定义中的两棵子树亦都是二叉树,则它们亦可 为空树。故二叉树可有下列五种基本形态: (a)(b)(c) (d) (e) (a)空二叉树 b)仅有根结点的二又树 (c)有根结点及左子树,右子树为空的二叉树一 (d)有根结点及左、右子树的二叉树 (e)有根结点及右子树,左子树为空的二叉树 叉树中,每个结点最多只能有两棵子树,并且有左、右之分。 A● ●A B B D ●B D D E 两棵不同的二叉树 棵普通树 第18页
第六章 树和二叉树 第18页 由于二叉树递归定义中的两棵子树亦都是二叉树，则它们亦可 为空树。故二叉树可有下列五种基本形态： (a) (b) (c) (d) (e) (a) 空二叉树 (b) 仅有根结点的二叉树 (c) 有根结点及左子树，右子树为空的二叉树 (d) 有根结点及左、右子树的二叉树 (e) 有根结点及右子树，左子树为空的二叉树 二叉树中，每个结点最多只能有两棵子树，并且有左、右之分。 两棵不同的二叉树 一棵普通树 A B C D E A B C E D A B D C E 二叉树的五种基本形态
二叉树的定义与基本操作 第六章树和三叉树 二叉树示例 A A B G H E 深度为4 深度为5 第19页
第六章 树和二叉树 第19页 二叉树示例 深度为4 深度为5 A B C D E G H F A B C D E ⚫ 二叉树的定义与基本操作
二叉树的基本操作 第六章树和三叉树 一与树的基本操作相类似,不同的是在求孩子结点、兄弟结点以 及插入、删除等操作时,均有左、右之分。 (1)Initiate( BT) 初始化操作,置BT为空树 (2) Root(BT)或Root(x) 求根结点函数 (3)Parent(BTx 求双亲结点函数。 (4)LChild(BT, x)FA RChild(BTx) 求孩子结点函数。分别返回二叉树BT中结点x的左孩子结点和 右孩子结点。若结点x是二叉树BT的叶结点或x不在二叉树BT中 一则返回空函数值NULL。 (5 )SIbling(BT x) FA SIbling(BT x) 一求兄弟结点函数。分别返回二叉树BT中结点x的左兄弟结点和 右兄弟结点。若结点x是根结点或x不在BT中或x是其双亲的左/右子 一树根,则返回空函数值NULL。 第20页
第六章 树和二叉树 第20页 二叉树的基本操作 与树的基本操作相类似，不同的是在求孩子结点、兄弟结点以 及插入、删除等操作时，均有左、右之分。 (1) Initiate(BT) 初始化操作，置BT为空树。 (2) Root(BT) 或 Root(x) 求根结点函数 (3) Parent(BT,x) 求双亲结点函数。 (4) LChild(BT,x) 和 RChild(BT,x) 求孩子结点函数。分别返回二叉树BT中结点x的左孩子结点和 右孩子结点。若结点x是二叉树BT的叶结点或x不在二叉树BT中， 则返回空函数值NULL。 (5) LSibling(BT,x) 和 RSibling(BT,x) 求兄弟结点函数。分别返回二叉树BT中结点x的左兄弟结点和 右兄弟结点。若结点x是根结点或x不在BT中或x是其双亲的左/右子 树根，则返回空函数值NULL