叉树的存储结构(顺序二叉三叉).ppt

数据结构（C+版） 2012 辽宁科技大学软件学院1 顺序存储结构 用一维数组存储二叉树中的结点，且结点的存储位置 （下标）应能体现结点之间的逻辑关系父子关系。 如何利用数组下标来反映结点之间的逻辑关系? 完全二叉树中结点的序号体现孩子、双亲之间 的逻辑关系 。 5.4 二叉树的存储结构及实现 数据结构（C+版） 2012 辽宁科技大学软件学院2 A B C D E F G H I J 数组下标 0 1 2 3 4 5 6 7 8 9 完全二叉树的存储 A 1 5 23 467 8910 BC DEFG HIJ 按编号 顺序存 5.4 二叉树的存储结构及实现 数据结构（C+版） 2012 辽宁科技大学软件学院3 一般二叉树的存储 ABC DE F G 数组下标 0 1 2 3 4 5 6 7 8 9 10 11 12 A BC DF GE 按编号 顺序存 A BC DF GE 1 2 3 56 10 13 按照完全 二叉树编号 5.4 二叉树的存储结构及实现 数据结构（C+版） 2012 辽宁科技大学软件学院4 一棵斜树的顺序存储会怎样呢？ 深度为k的右斜树，k个结点需分配2k1个存储单元。 一棵二叉树改造成完全 二叉树形态，需要增加 很多空结结点，造成存储 空间的浪费。 二叉树的顺序存储一般仅适合于存储完全二叉树 A B C D 1 3 7 15 5.4 二叉树的存储结构及实现 数据结构（C+版） 2012 辽宁科技大学软件学院5 二叉链表 基本思想： 令二叉树的每个结点对应一个二叉链表结点。 结点结构： lchild data rchild 其中，data：数据域，存放该结点的数据信息； lchild：左指针域，存放指向该结点左孩子的指针； rchild：右指针域，存放指向该结点右孩子的指针。 5.4 二叉树的存储结构及实现 数据结构（C+版） 2012 辽宁科技大学软件学院6 A B C D E F G 二叉链表 具有n个结点的二叉链表中，有多少个空指针？ n+1 A C 头指针root FE B D G 5.4 二叉树的存储结构及实现 数据结构（C+版） 2012 辽宁科技大学软件学院7 template struct BiNode DataType data; BiNode *lchild, *rchild; ; lchild data rchild 左孩子结点右孩子结点 二叉链表结点的描述 5.4 二叉树的存储结构及实现 数据结构（C+版） 2012 辽宁科技大学软件学院8 二叉链表存储结构的类声 明 template class BiTree public: /构造函数，建立一棵二叉树 BiTree( )root = Creat(root); /析构函数 BiTree( )Release(root); /前序遍历二叉树 void PreOrder( )PreOrder(root); /中序遍历二叉树 void InOrder( )InOrder(root); /后序遍历二叉树 void PostOrder( )PostOrder(root); /层序遍历二叉树 void LeverOrder( ); 5.4 二叉树的存储结构及实现 数据结构（C+版） 2012 辽宁科技大学软件学院9 二叉链表存储结构的类声 明 private: /指向根结点的头指针 BiNode *root; /构造函数调用 BiNode *Creat(BiNode *bt); /析构函数调用 void Release(BiNode *bt); /前序遍历函数调用 void PreOrder(BiNode *bt); /中序遍历函数调用 void InOrder(BiNode *bt); /后序遍历函数调用 void PostOrder(BiNode *bt); ; 5.4 二叉树的存储结构及实现 数据结构（C+版） 2012 辽宁科技大学软件学院10 前序遍历递归算法 template void BiTree : PreOrder(BiNode *bt) if (bt = NULL) return; /递归调用的结束条件 else cout data; /访问根结点bt的数据域 PreOrder(bt-lchild); /前序递归遍历bt的左子树 PreOrder(bt-rchild); /前序递归遍历bt的右子树 5.4 二叉树的存储结构及实现 数据结构（C+版） 2012 辽宁科技大学软件学院11 中序遍历递归算法 template void BiTree : InOrder (BiNode *bt) if (bt = NULL) return; /递归调用的结束条件 else InOrder(bt-lchild); /中序递归遍历bt的左子树 cout data; /访问根结点bt的数据域 InOrder(bt-rchild); /中序递归遍历bt的右子树 5.4 二叉树的存储结构及实现 数据结构（C+版） 2012 辽宁科技大学软件学院12 后序遍历递归算法 template void BiTree : PostOrder(BiNode *bt) if (bt = NULL) return; /递归调用的结束条件 else PostOrder(bt-lchild); /后序递归遍历bt的左子树 PostOrder(bt-rchild); /后序递归遍历bt的右子树 cout data; /访问根结点bt的数据域 5.4 二叉树的存储结构及实现 数据结构（C+版） 2012 辽宁科技大学软件学院13 层序遍历（广度优先遍历） A B C D E F G 遍历序列： A A B C B D C E F G D E F G 5.4 二叉树的存储结构及实现 数据结构（C+版） 2012 辽宁科技大学软件学院14 层序遍历 1. 队列Q初始化； 2. 如果二叉树非空，将根指针入队； 3. 循环直到队列Q为空 3.1 队列Q的队头元素出队，q指向队头结点； 3.2 访问结点q的数据域； 3.3 若q-lchild非空，则将其入队； 3.4 若q-rchild非空，则将其入队； 5.4 二叉树的存储结构及实现 数据结构（C+版） 2012 辽宁科技大学软件学院15 template void BiTree : LeverOrder( ) front = rear = -1; /采用顺序队列，并假定不会发生上溢 if (root = NULL) return; /二叉树为空，算法结束 Q+rear = root; /根结点入队 while (front != rear) /当队列非空时 q = Q+front; /出队 cout data; if (q-lchild != NULL) Q+rear = q-lchild; if (q-rchild != NULL) Q+rear = q-rchild; 5.4 二叉树的存储结构及实现 数据结构（C+版） 2012 辽宁科技大学软件学院16 二叉树的建立 为了建立一棵二叉树，将二叉树中每个结点的空指 针引出一个虚结点，其值为一特定值如“#”，以标 识其为空，（每个结点都有左右孩子）把这样处理 后的二叉树称为原二叉树的扩展二叉树。 为什么如此处理? 如何由一种遍历序列生成该二叉树？ 5.4 二叉树的存储结构及实现 数据结构（C+版） 2012 辽宁科技大学软件学院17 扩展二叉树的前序遍历序列: A B # D # # C # # D B A C # D B A C # # # 二叉树的建立 5.4 二叉树的存储结构及实现 数据结构（C+版） 2012 辽宁科技大学软件学院18 设二叉树中的结点均为一个字符。假设扩展二叉树的 前序遍历序列由键盘输入，root为指向根结点的头指针 ，二叉链表的建立过程是： 首先输入根结点，若输入的是一个“#”字符，则表明该 二叉树为空树，即bt=NULL；否则输入的字符应该赋 给bt-data，之后依次递归建立它的左子树和右子树 。 二叉树的建立 5.4 二叉树的存储结构及实现 数据结构（C+版） 2012 辽宁科技大学软件学院19 template BiTree : BiTree( ) root = Creat(root); template BiNode *BiTree:Creat(BiNode *bt) cin ch; /输入结点的数据信息，假设为字符 if (ch = # ) bt = NULL; /建立一棵空树 else bt = new BiNode; bt-data = ch; /生成一个结点，数据域为ch bt-lchild = Creat(bt-lchild); /递归建立左子树 bt-rchild = Creat(bt-rchild); /递归建立右子树 return bt; 建立二叉树递归算法 5.4 二叉树的存储结构及实现 数据结构（C+版） 2012 辽宁科技大学软件学院20 遍历二叉树是二叉树各种操作的基础，遍历算 法中对每个结点的访问操作可以是多种形式及多个 操作，根据遍历算法的框架，适当修改访问操作的 内容，可以派生出很多关于二叉树的应用算法。 void InOrder (BiNode *root) if (root=NULL) return; else InOrder(root-lchild); coutdata; InOrder(root-rchild); 5.4 二叉树的存储结构及实现 数据结构（C+版） 2012 辽宁科技大学软件学院21 设计算法求二叉树的结点个数。 int Count(BiNode *root) if (!root) return 0； else return Count(root-lchild) +Count(root-rchild)+1; 5.4 二叉树的存储结构及实现 数据结构（C+版） 2012 辽宁科技大学软件学院22 设计算法按前序次序打印二叉树中的叶子结点。 void PreOrder(BiNode *root) if (root) if (!root-lchild PreOrder(root-lchild); PreOrder(root-rchild); 5.4 二叉树的存储结构及实现 数据结构（C+版） 2012 辽宁科技大学软件学院23 设计算法求二叉树的深度。 int Depth(BiNode *root) if (root= =NULL) return 0; else hl= Depth(root-lchild); hr= Depth(root -rchild); return max(hl, hr)+1; 5.4 二叉树的存储结构及实现 数据结构（C+版） 2012 辽宁科技大学软件学院24 三叉链表 A B C D E F G 在二叉链表中，如何求某结点的双亲？ A C root FE B D G 5.4 二叉树的存储结构及实现 数据结构（C+版） 2012 辽宁科技大学软件学院25 三叉链表 lchild dataparent rchild 在二叉链表的基础上增加了一个指向双亲的指针域。 结点结构 其中：data、lchild和rchild三个域的含义同二叉链 表的结点结构； parent域为指向该结点的双亲结点的指针。 5.4 二叉树的存储结构及实现 数