[计算机软件及应用]树和二叉树.pptVIP

第6章　树和二叉树;　　本章主要介绍串，它属于线性结构，是数据元素的内部结构确定为符号的特殊线性表。讨论串的逻辑结构、逻辑结构上定义的运算、物理结构、逻辑结构与物理结构对应关系、运算的实现算法与效率分析。 重点研究串的概念、基本运算、顺序结构和链式存储结构及其主要运算的实现算法及其效率分析。;重点讲解;6.1.1 树的逻辑结构定义及术语 ; 举例：T ＝ ｛A，B，C，D，E，F，G，H，I，J，K，L，M｝ T_root ＝ A T1 ＝ ｛B，E，F，K，L｝ T2 ＝ ｛C，G｝ T3 ＝ ｛D，H，I，J，M｝ T1_root ＝ B T1_1 ＝｛E，K，L｝ T1_2 ＝｛F｝ T1_1_root ＝ E T1_1_1 ＝｛K｝ T1_1_2 ＝｛L｝ T2_root ＝ C T2_1 ＝ ｛G｝ T3_root ＝ D T3_1 ＝ ｛H，M｝ T3_2 ＝ ｛I｝ T3_3 ＝ ｛J｝ T3_1_root ＝ H T3_1_1 ＝ ｛M｝;A;A; 如果树中每个结点的子树从左至右认为是有序的，则称该树为有序树，否则称为无序树。 度数为n有序树称为n叉树，度数为n的无序树称为n元树。 m(m≥0)棵互不相交的树的集合称为森林。;6.1.2 树的基本运算 ;（9）数据赋值Assign(T，cur_e，value) 将结点value，赋值于树T的结点cur_e中。 （10）获得双亲Parent(T，cur_e) 返回树T中结点cur_e的双亲结点。 （11）获得最左孩子LeftChild(T，cur_e) 返回树T中结点cur_e的最左孩子。 （12）获得右兄弟RightSibling(T，cur_e) 返回树T中结点cur_e的右兄弟。 （13）插入子树InsertChild(T，p，i，c) 将树c插入到树T中p指向结点的第i个子树之前。 （14）删除子树DeleteChild(T，p，i) 删除树T中p指向结点的第i个子树。 （15）遍历树TraverseTree(T，visit());6.2.1 二叉树的定义 ;（1）创建二叉树IntBiTree(T) 创建1个空二叉树T。 （2）销毁二叉树DestroyBiTree(T) （3）构造二叉树CreatBiTree(T，definition) （4）置空二叉树ClearBiTree(T) 将二叉树T置为空二叉树。 （5）判空二叉树BiTreeEmpty(T) （6）求二叉树的深度BiTreeDepth(T) （7）获得二叉树根Root(T) （8）获取结点Value(T，cur_e，e) 将二叉树中结点cur_e存入e单元中。;（9）数据赋值Assign(T，cur_e，value) 将结点value，赋值于二叉树T的结点cur_e中。 （10）获得双亲Parent(T，cur_e) 返回二叉树T中结点cur_e的双亲结点。 （11）获得左孩子LeftChild(T，cur_e) 返回二叉树T中结点cur_e的左孩子。 （12）获得右孩子RightChild(T，cur_e) 返回二叉树T中结点cur_e的右孩子。 （13）插入子树InsertChild(T，p，LR，c) 将二叉树c插入到二叉树T中p指向结点的LR子树。 （14）删除子树DeleteChild(T，p，LR) 删除二叉树T中p指向结点的LR子树。 ;（15）前序遍历PreOrderTraverse(T，visit()) 将先visit()二叉树T的根，其次visit()二叉树T的左子树，再visit()二叉树T的右子树。其中，左子树和右子树均按上述同样次序visit()。 （16）中序遍历InOrderTraverse(