数据结构PPt——2.pptx

二叉树的抽象数据类型;6.4 二叉树的遍历(Traversing);;中序遍历算法框架：;后序遍历算法框架：; //采用二叉链表存储结构 status POT ( BiTree T, Status (* Visit)(TElemType e)) { if (T) { // 二叉树不为空 Visit(T - data)；// 访问根结点 POT ( T-lchild, Visit )； //先序遍历左子树 POT ( T-rchild, Visit )； //先序遍历右子树 return OK; } } //POT;//最简单的Visit 函数 Status PrintElement ( TElemType e ) { printf(“%d”,root-data); return OK; };status InOT ( BiTree T, Status (* Visit)(TElemType e)) { if (T) { // 二叉树不为空 InOT ( T-lchild, Visit )； //先序遍历左子树 Visit(T - data)；// 访问根结点 InOT ( T-rchild, Visit )； //先序遍历右子树 return OK; } };status PostOT ( BiTree T, Status (* Visit)(TElemType e)) { if (T) { // 二叉树不为空 PostOT( T-lchild, Visit )； //先序遍历左子树 PostOT( T-rchild, Visit )； //先序遍历右子树 Visit(T - data)；// 访问根结点 return OK; } };;已知中序遍历：B D C E A F H G 已知后序遍历：D E C B H G F A;3. 若已知中序和先序序列…… 例：已知一棵二叉树的先序序列和中序序列分别为ABDGHCEFI 和 GDHBAECIF，试确定二叉树结构。;;1. 查询二叉树中某个结点 ;Status Preorder (BiTree T, ElemType x, BiTree p) { // 若二叉树中存在和 x 相同的元素，则p指向该结点并返回 OK,否则返回 FALSE };2. 统计二叉树中叶子结点的个数;3. 求二叉树的深度;int Depth (BiTree T) { if ( !T ) depthval = 0; else{ depthLeft = Depth( T-lchild ); depthRight= Depth( T-rchild ); depthval = 1 +MAX (depthLeft , depthRight); } return depthval; };4. 二叉树的生成;Status CreateBiTree(BiTree T) { scanf(ch); if (ch== ) T = NULL; else { T =( BiTNode *)malloc(sizeof(BiTNode)); if (!T) exit(OVERFLOW); T-data = ch; // 生成根结点 CreateBiTree(T-lchild); // 构造左子树 CreateBiTree(T-rchild); // 构造右子树 } return OK; } // CreateBiTree;;层序遍历算法框架：;二叉树的应用——二叉排序树;;50;1. 二叉排序树的查找算法;(1). 二叉排序树上的成功查找;(2). 二叉排序树上查找失败;改造后的查找算法;算法描述如下：;;;4. 二叉排序树的删除算法; 二叉排序树的删除;50;（2）被删除的结点只有左子树或者只有右子树;50;5. 二叉排序树查找性能的分析;数据结构DATA STRUCTURE