本单元涉及的内容

本单元涉及的内容内容摘要：

*TNODE。 void Create_t(TNODE amp。 bt) { char ch。 cinch。 if(ch==39。 39。 ) bt=NULL。 else { bt=new struct tnode。 btdata=ch。 Create_t(btlchild)。 Create_t(btrchild)。 } } A B C D E F ABC..DE..F... 下一页 上一页 停止放映 第 41 页 建立二叉树 (续） void preOrder_t (struct tnode *root) { if ( root != NULL ) {coutrootdata。 preOrder_t(rootlchild)。 preOrder_t(rootrchild)。 } } main() { TNODE root。 Create_t(root)。 preOrder_t(root)。 } 下一页 上一页 停止放映 第 42 页 树的存储结构  双亲表示法  孩子表示法  孩子兄弟表示法 下一页 上一页 停止放映 第 43 页 双亲表示法 1 2 3 4 5 6 7 8 9 结点序号 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 0 1 1 2 2 3 5 5 5 方法特点： 找根容易，找子结点难， 要遍历整个数组。 下一页 上一页 停止放映 第 44 页 双亲表示法 C++描述 用数组存储树的结点信息 ， 在每个结点中附设一个指示器指示其双亲结点在数组中的位置 ,也称为数组实现方法。 结构描述： define MAXSIZE 100 typedef struct PTNode{ TElemType data； int parent ； } PTNode； typedef struc { PTNode nodes[MAXSIZE]； int n； } Ptree； 下一页 上一页 停止放映 第 45 页 孩子表示法 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 2 3 ^ 4 5 ^ 6 ^ ^ ^ ^ ^ ^ 7 8 9 ^ 方法特点 : 便于实现对孩子的操 作 ,却不便于对父亲 的操作 . 下一页 上一页 停止放映 第 46 页 孩子表示法 C++描述  把每个结点的孩子结点排列起来，组成一个线性表，且以单链表作为存储结构，则 n个结点有 n个孩子链表，也称为链表实现方式。  结构描述为： typedef struct CTNode typedef struct { int child； { CTBox nodes[MAXSIZE]； struct CTNode *next： int n； } *Childptr； } Ctree； typedef struct { TElemType data； Childptr firstchild； } CTBox； 下一页 上一页 停止放映 第 47 页 孩子兄弟表示法 1 2 3 4 5 6 7 8 9 1 2 ^ 3 7 4 5 6 8 9 ^ ^ ^ ^ ^ ^ ^ ^ 方法特点 : 这种存储结构便于实现各种树的操作 . ^ 下一页 上一页 停止放映 第 48 页 孩子兄弟表示法 C++描述  二叉链表实现方式 （ 孩子兄弟表示法 ） 以二叉链表作为树的存储结构。 链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。 结构描述为： typedef struct CSNode{ ElemType data； struct CSNode *firstchild ， *nextsibling； } CSNode， * CSTree； 下一页 上一页 停止放映 第 49 页 表达式树及应用  在计算机中对表达式进行分析和计算是一项重要的任务。  举例 ， 用二叉树表示表达式： a + b * （ c d ） － ｅ ／ｆ 前序遍历序列：－＋ａ＊ｂ－ｃｄ／ｅｆ 中序遍历序列：ａ＋ｂ＊ｃ－ｄ－ｅ／ｆ 后序遍历序列：ａｂｃｄ－＊＋ｅｆ／－  分析： – 每个叶结点为运算对象； – 每个非叶结点为运算符； – 每个子树对应一个子表达式。  表达式处理一般采用后序法 ， 也称 “ 逆波兰 ” 法。  表达式处理规则： – 见运算数入栈； – 见运算符 ， 取两个栈顶元素运算后再压栈； – 直到处理结束。 － ＋ ／ － e f ＊b － c d a 下一页 上一页 停止放映 第 50 页 树、森林与二叉树的转换  由于二叉树的存储结构比较简单 ， 处理起来也比较方便 ， 所以有时需要把复杂的树 ， 转换为简单的二叉树后再作处理。  树转换成二叉树  森林转换成二叉树 下一页 上一页 停止放映 第 51 页 树转换成二叉树  操作算法： – 保留一个结点的最左子结点； – 抹掉其余兄弟结点与上级结点的连线； – 将兄弟结点连在一起； – 以根为轴 ， 顺时针旋转一个角度。  举例： o o o o o o o o o o o o o o 加线 抹线 o o o o o o o 旋转 o o o o o o o 下一页 上一页 停止放映 第 52 页 森林转换成二叉树  操作算法： – 将森林中每棵树的树根连接起来； – 将每棵树转换成对应的二叉树； – 以森林中第一棵树的根为轴顺时针旋转一个角度。  举例 o o o o o o o o o o 连线 o o o o o o o o o o 抹线 o o o o o o o o o o 旋转 o o o o o o o o o o 下一页 上一页 停止放映 第 53 页 将二叉树还原成树事例 A B E C F D G A B E C F D G （ a）二叉树 （ b）加连线 A B E C F D G （ c）删除与 右子的连线 A B E C F D G （ d）还原后的树 下一页 上一页 停止放映 第 54 页 将二叉树还原成树  将二叉树还原成树的操作步骤为： step1 把各结点的右子、都与该结点的双亲结点用线连起来； step2 删除原二叉树中所有的双亲结点与右子结点的连线； step3 旋转一定角度。 下一页 上一页 停止放映 第 55 页 六、二叉排序树的生成 对给定数列 {a1， a2， … ,an},根据二叉排序树特性 ,逐个将结点插入到二叉排序中。 具体操作步骤： step1 a1是根结点； step2 若 aiaj ,且 aj的左子为空 ,则将 ai插入到 aj的左子。 若 aj的左子非空 ,则继续寻找合适的插入位置。 若 aiaj， 且 aj的右子为空 ， 则将 ai插入到 aj的右子；否则继续沿右子树寻找合适的插入位置； 插入 ai 插入到 aj的左子 ai〈 aj 插入到 aj的右子 ai  aj step3 重复 step2，直到所有结点插入完为止。 下一页 上一页 停止放映 第 56 页 二叉排序树算法 二叉排序树结点结构： struct tree { char info；。