数据结构-二叉树的存储结构和遍历.ppt

二叉树的存储结构和遍历 二叉树的遍历 二叉树的存储结构 小结和作业 顺序存储 二叉链表 三叉链表 链式存储 问题的提出 递归遍历算法 遍历的应用实例 二叉树的顺序存储 顺序存储是用一组连续的存储单元存放数据 顺序存储要求数据是线性结构 二叉树是非线性结构 如何把二叉树转换为线性结构 而且保持结点之间的父 子关系 二叉树的顺序存储 A C G B D E F K L H J I M N O 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 满二叉树 从上到下 从左往右依次编号 二叉树的顺序存储 0123456789101112131415 数组的下标 也是结点的编号 0123456789101112131415 二叉树的顺序存储 完全二叉树 从上到下 从左往右依次编号 012345678910 二叉树的顺序存储 一般的二叉树 想象成一个完全二叉树 0 0 0 0 0 0 0 0 二叉树的顺序存储 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 二叉树的顺序存储 01234567891011121314 01234567891011121314 如何知道有无数据 defineMAX TREE SIZE100 二叉树的最大结点数typedefTElemTypeSqBiTree MAX TREE SIZE 1号单元存储根结点SqBiTreebt 二叉树的顺序存储 defineMAX TREE SIZE100 二叉树的最大结点数typedefstruct TElemTypedata MAX TREE SIZE charflag MAX TREE SIZE SqBiTree 二叉树的顺序存储 适用于一般的二叉树 链式存储 二叉链表 二叉链表的结点结构 左指针域 指向当前结点的左子树 数据域 存储当前结点的取值信息 右指针域 指向当前结点的右子树 指向二叉树根结点 头指针 前述二叉树的二叉链表如下所示 A F E C D B root 链式存储 二叉链表 typedefstructBiTNode 结点结构TElemTypedata structBiTNode lchild rchild 左右孩子指针 BiTNode BiTree 结点结构 二叉链表的C语言类型描述如下 左指针域 数据域 右指针域 链式存储 二叉链表 三叉链表的结点结构 指向双亲结点的指针域 左指针域 数据域 右指针域 链式存储 三叉链表 root E 二叉树的三叉链表表示 链式存储 三叉链表 typedefstructTriTNode TElemTypedata structTriTNode lchild rchild structTriTNode parent TriTNode TriTree 三叉链表的C语言类型描述如下 结点结构 结点结构 左右孩子指针 双亲指针 链式存储 三叉链表 问题的提出 在实际应用中 经常需要在二叉树中查找具有某些特征的结点 或者对树中的全部结点逐一进行某种处理 这就提出了二叉树的遍历的问题 问题的提出 定义 顺着某一条搜索路径巡访二叉树中的结点 使得每个结点均被访问一次 而且仅被访问一次 作用 遍历的目的是线性化 使二叉树中的结点能够按照某种次序排列在一个线性队列上 便于处理 问题的提出 线性结构的遍历 因为每个结点均只有一个后继 所以只有一条搜索路径 二叉树的遍历 二叉树是非线性结构 每个结点有两个后继 则存在如何遍历即按什么样的搜索路径进行遍历的问题 问题的提出 二叉树存在下述三条搜索路径 1 先上后下的按层次遍历 2 先左 子树 后右 子树 的遍历 DLR LDR LRD3 先右 子树 后左 子树 的遍历 DRL RDL RLD 先序 根 遍历 根 左子树 右子树 若二叉树为空树 则空操作 否则 1 访问根结点 2 先序遍历左子树 3 先序遍历右子树 先序 根 遍历 A B C D E F G H K A B C D E F G H K A BCD EFGHK 课堂练习 写出先序遍历的结果 voidPreorder BiTreeT void visit TElemType 遍历右子树 先序遍历 中序 根 遍历 左子树 右子树 根 根 左子树 右子树 若二叉树为空树 则空操作 否则 1 中序遍历左子树 2 访问根结点 3 中序遍历右子树 中序 根 遍历 A B C D E F G H K A B C D E F G H K A BDC EHGKF 中序遍历 voidInorder BiTreeT void visit TElemType 遍历右子树 后序 根 遍历 左子树 右子树 根 根 左子树 右子树 若二叉树为空树 则空操作 否则 1 后序遍历左子树 2 后序遍历右子树 3 访问根结点 后序 根 遍历 A B C D E F G H K A DCB HKGFE voidPostorder BiTreeT void visit TElemType 访问结点 后序遍历 课堂练习 写出三种遍历的结果 先序序列 中序序列 后序序列 ABCDEFGHK BDCAEHGKF DCBHKGFEA 三种遍历的比较 1 如果不考虑visit 三种遍历的算法在结构上是一样的 因此 压栈和出栈的过程相同 三种遍历的比较 2 三种遍历的执行过程是不一样的 visit的位置不一样 3 由前序序列和中序序列 或者后序和中序序列可以唯一确定一颗二叉树 先序序列 中序序列 后序序列 ABCDEFGHK BDCAEHGKF DCBHKGFEA 三种遍历的比较 3 复制二叉树 4 建立二叉树 2 查询二叉树中某个结点 应用举例 1 统计二叉树中结点的个数 遍历访问了每个结点一次且仅一次 设置一个全局变量count 0 统计二叉树中结点的个数 将visit改为 count 统计二叉树中结点的个数 voidPreOrder BiTreeT if T return count Preorder T lchild Preorder T rchild voidPreorder BiTreeT void visit TElemType 遍历右子树 统计二叉树中结点的个数 intcount 0 main PreOrder T printf d count 递归思想 如果是空树 返回0 统计二叉树中结点的个数 求出左子树的结点的个数m 求出右子树的结点的个数n 返回m n 1 统计二叉树中结点的个数 intCountNode BiTreeT 返回指针T所指二叉树中所有叶子结点个数 if T return0 空树 m CountNode T lchild n CountNode T rchild return m n 1 求二叉树的深度 课堂练习 空树的深度为0 求二叉树的深度 intDepth BiTreeT 返回二叉树的深度 if T return 0 depthLeft Depth T lchild depthRight Depth T rchild depthval 1 depthLeft depthRight depthLeft depthRight returndepthval 查询二叉树中的某个结点 给定指向二叉树的根结点的指针T和x 在T中查找数据元素的值等于x的结点 如果找到 则返回一个指针 指向这个结点 否则 返回空指针 T X C 查询二叉树中的某个结点 1 在二叉树不空的前提下 和根结点的元素进行比较 若相等 则找到返回指向根结点的指针 2 否则在左子树中进行查找 若找到 则返回指针 3 否则继续在右子树中进行查找 若找到 则返回指针 否则返回空指针 查询二叉树中的某个结点 BiTreeSearch BiTreeT TElemTypex if T return NULL if T data x return T if p 返回值不是空指针 则表示x在左子树中return p elsereturn Search T rchild x p Search T lchild x 复制二叉树 练习 给定一棵二叉树 T指向其根结点 复制一棵二叉树 返回一个指向新树根结点的指针 根元素 T 右子树 NEWT 左子树 右子树 左子树 复制二叉树 1 如果T为空 则返回空指针 2 复制根结点 p指向新结点 3 复制左子树 pl指向左子树的根 4 复制右子树 pr指向右子树的根 5 p lchid pl p rchild pr 6 返回p 复制二叉树 BitreeCopy BitTreeT if T return NULL p newBiNode p data T data pl Copy T lchild pr Copy T rchild p lchild pl p rchild pr return p 以下列字符串表示 ABCD 建立二叉树 以字符串的形式 根左子树右子树 定义一棵二叉树 以空白字符 表示 1 空树 2 只含一个根结点的二叉树 A 以字符串 A 表示 3 建立二叉树 ABCD A B C D A T B C D 建立二叉树 StatusCreateBiTree BiTree T CopyTree scanf else T data ch 生成根结点 returnOK if T newBiTNode exit OVERFLOW if ch T NULL CreateBiTree T lchild 构造左子树 CreateBiTree T rchild 构造右子树 小结 1 二叉树的顺序存储表示 2 二叉树的二叉链表存储表示 二叉链表 双亲链表 三叉链表 3 二叉树的遍历 前序 先根 中序 中根 后序 后根 作业 作业 6 12 6 42 6 43 建立二叉树 由二叉树的先序和中序序列建树 二叉树的先序序列 二叉树的中序序列 左子树 左子树 右子树 右子树 根 根 建立二叉树 abcdefg cbdaegf a a b b c c d d e e f f g g a b c d e f g 先序 中序 建立二叉树 BiNode Bitree create T