每个元素都有唯一的前驱第一个除外和后继最后一

每个元素都有唯一的前驱第一个除外和后继最后一内容摘要：

虚拟实现： typedef 用户数据类型 elemtype。 //定义数据元素类型 struct bitree { elemtype data。 //结点数据类型 bitree *parent， *lson, *rson。 //定义左、右孩子为指针型 } 167。 .2 二叉树的链式存储结构及虚拟实现 167。 二叉树的存储结构及操作的虚拟实现 a b c d e f g 举例： a b ^ c d e f g ^ ^ ^ ^ ^ ^ ^ ^ 167。 .3 二叉树链式存储结构下操作的虚拟实现 （二叉链式存储结构） 167。 二叉树的存储结构及操作的虚拟实现 一、遍历操作 遍历 ( Traversal )： 把二叉树中的结点访问且仅访问一次， 又称为扫描。 遍历方式 ： 由于元素之间的关系复杂了，按什么样的顺序 访问数据元素。 广度优先遍历 深度优先遍历 广度优先遍历 ： 又称为层次遍历，从第 1层开始，逐层访问 二叉树的元素，每一层从左向右。 167。 二叉树的存储结构及操作的虚拟实现 167。 .3 二叉树链式存储结构下操作的虚拟实现 （二叉链式存储结构） a b c d e f g a a b c b c d e d e f g f g 167。 二叉树的存储结构及操作的虚拟实现 167。 .3 二叉树链式存储结构下操作的虚拟实现 （二叉链式存储结构） 算法： void lorder(t:bitreptr)。 { Iniqueue(Q)。 //队列 初始化 if(t!=NULL) Enqueue(Q,t)。 //树 根入队 while (!Empty(Q)) // 当 队列不空时，重复 { Dlqueue(Q,p)。 //出 队一个元素 visit(pdata)。 if(p lchild!=NULL) Enqueue(Q,plchild)。 if (prchild!=NULL) Enqueue(Q,prchild)。 } } 要实现分层输出，如何处理。 167。 二叉树的存储结构及操作的虚拟实现 167。 .3 二叉树链式存储结构下操作的虚拟实现 （二叉链式存储结构） 队列 1 队列 2 当前层入队列 1，出队时，其左、右儿子入队列 2， 当队列 1为空，则当前层结束，其下层在队列 2中， 队列 2变为当前层。 自己写出算法。 上次课内容回顾 二叉树的定义：递归、形态 二叉树的性质： 满二叉树、完全二叉树 二叉树的存储结构：方式、特点 顺序存储、二叉链式、三叉链式 二叉树的操作的虚拟实现（二叉链式存储结构） 遍历：广度方式 167。 二叉树的存储结构及操作的虚拟实现 167。 .3 二叉树链式存储结构下操作的虚拟实现 （二叉链式存储结构） 深度优先遍历 ： 基本思想是： 按某种原则访问一个元素，由于它与多个元素 有关系（ 1个前趋、 2个后继），按同样原则选 择一个元素继续访问。 注意与广度遍历的区别。 假设一棵树表示为根（ D）、 左子树（ L）、 右子树（ R） 则，它们的顺序关系有 3。 =6种： DLR DRL LDR RDL LRD RLD 如果规定先左后右，则剩下 3种。 L D R 167。 二叉树的存储结构及操作的虚拟实现 167。 .3 二叉树链式存储结构下操作的虚拟实现 （二叉链式存储结构） 前序遍历（ DLR）： 访问根； 前序遍历左子树； 前序遍历右子树； 中序遍历（ LDR）： 中序遍历左子树； 访问根； 中序遍历右子树； 后序遍历（ LRD）： 后序遍历左子树； 后序遍历右子树； 访问根； Preorder Traversal Inorder Traversal Postorder Traversal 遍历序列：按某种方式遍历二叉树的元素，得到的元素序列 167。 二叉树的存储结构及操作的虚拟实现 167。 .3 二叉树链式存储结构下操作的虚拟实现 （二叉链式存储结构） a b c d e f g 前序遍历序列： 1 a 2 b 3 d 4 c 5 e 6 f 7 g 中序遍历序列： d b a f e g c 后序遍历序列： d b f g e c a 167。 二叉树的存储结构及操作的虚拟实现 167。 .3 二叉树链式存储结构下操作的虚拟实现 （二叉链式存储结构） 遍历序列的特点： 根结点 左子树的前序遍历 右子树的前序遍历 根结点 左子树的中序遍历 右子树的中序遍历 根结点 左子树的后序遍历 右子树的后序遍历 167。 二叉树的存储结构及操作的虚拟实现 167。 .3 二叉树链式存储结构下操作的虚拟实现 （二叉链式存储结构） 前序遍 历算法： void preorder(bitree *root) { bitree *p。 p=root。 if(p!=NULL) {coutpdata“ ”。 preorder(plchild)。 preorder (prchild)。 } } 访问到该元素。 递归前序遍历左子树 递归前序遍历右子树 167。 二叉树的存储结构及操作的虚拟实现 167。 .3 二叉树链式存储结构下操作的虚拟实现 （二叉链式存储结构） 中序遍 历算法： void inorder(biteee *root) { bitree *p。 p=root。 if (p!=NULL) { inorder(plchild)。 coutpdata“ ”。 inorder(prchild)。 } } 访问到该元素。 递归中序遍历左子树 递归中序遍历右子树 167。 二叉树的存储结构及操作的虚拟实现 167。 .3 二叉树链式存储结构下操作的虚拟实现 （二叉链式存储结构） 后序遍 历算法： void postorder( bitree *root) { bitree *p。 p=root。 if (p!=NULL) { postorder (plchild)。 postorder (prchild)。 coutpdata“ ”。 } } 访问到该元素。 递归后序遍历左子树 递归后序遍历右子树 167。 二叉树的存储结构及操作的虚拟实现 167。 .3 二叉树链式存储结构下操作的虚拟实现 （二叉链式存储结构） 算术表达式的二叉树表示及前、后缀形式 （ 1）算术表达式表示为二叉树： 若表达式为常数、简单变量，则二叉树只有根，数据元素为 常数或变量； 否则，表达式可以写作： 表达式 =表达式 1 算符 表达式 2 于是，二叉树的根是 算符 ，根的左子树由 表达式 1形成， 根的右子树由 表达式 2 形成；（递归的。 ） 167。 二叉树的存储结构及操作的虚拟实现 167。 .3 二叉树链式存储结构下操作的虚拟实现 （二叉链式存储结构） 例如有算术表达式 ： a+b*(cd)e/f e/f a + b*(cd) a b*(cd) + b * cd c d e / f c d e b * a + / f 表达式的二叉树形式是否唯一。 167。 二叉树的存储结构及操作的虚拟实现 167。 .3 二叉树链式存储结构下操作的虚拟实现 （二叉链式存储结构） （ 2）算术表达式的前缀、后缀形式： 前序遍历表达式的二叉树，得到的前序遍历序 列是表达式的前缀形式。 后序遍历表达式的二叉树，得到的后序遍历序 列是表达式的后缀形式。 167。 二叉树的存储结构及操作的虚拟实现 167。 .3 二叉树链式存储结构下操作的虚拟实现 （二叉链式存储结构） c d e b * a + / f 例： a+b*(cd)e/f 前缀： +a*bcd/ef 后缀： abcd*+ef/ 表达式的中缀形式如何得到 ?中序遍历。 167。 二叉树的存储结构及操作的虚拟实现 167。 .3 二叉树链式存储结构下操作的虚拟实现 （二叉链式存储结构） 167。 二叉树的存储结构及操作的虚拟实现 167。 .3 二叉树链式存储结构下操作的虚拟实现 （二叉链式存储结构） 二、二叉树的插入与删除操作 在二叉树中进行插入、删除操作，若简单的描述为“在二叉 树的某个位置插入（删除）一个结点”，是无法进行操作的因为 ，它涉及前驱（ 1个）和后继（ 2个）的调整，不象线性表那么简 单。 除了知道在哪个位置插入、删除外，一般遵循两个原则： （ 1）、插入、删除后如何调整 ——对一般二叉树 （ 2）、达到某种性质（或保持某种性质） ——对特殊二叉树 167。 二叉树的存储结构及操作的虚拟实现 167。 .3 二叉树链式存储结构下操作的虚拟实现 （二叉链式存储结构） 插入： 插入一个数据元素 Y， 使之成为数据元素 X的左儿子， 而原来 X的左儿子成为 Y的左儿子。 方法：找到数据元素 X， 可采用广度、深度遍历均可； 生成插入结点； 插入并调整； ... ... ( r 指向数据元素 X结点 ) New(p)。 pdata=y。 plchild=rlchild。 rlchild=p。 X Y 167。 二叉树的存储结构及操作的虚拟实现 167。 .3 二叉树链式存储结构下操作的虚拟实现 （二叉链式存储结构） 删除： 删除数据元素为 X的结点，使其左儿子成为其双亲的 儿子， X原来的右儿子成为 X原来左儿子的最右下儿 子。 方法：找到数据元素 X， 可采用广度、深度遍历均可（ 由于 涉及元素 X的双亲，所以要得到指向双亲结点的指针）； 得到指向 X左、右儿子的指针； 删除元素 X结点； 按置好左、右儿子 167。 二叉树的存储结构及操作的虚拟实现 167。 .3 二叉树链式存储结构下。