《叉树的存储结构(顺序二叉三叉).ppt》由会员分享，可在线阅读，更多相关《叉树的存储结构(顺序二叉三叉).ppt（27页珍藏版）》请在金锄头文库上搜索。
1、数据结构（C+版）2012辽宁科技大学软件学院1顺序存储结构顺序存储结构用一维数组存储二叉树中的结点，且结点的用一维数组存储二叉树中的结点，且结点的存储位存储位置置（下标）应能体现结点之间的（下标）应能体现结点之间的逻辑关系逻辑关系父子关系。父子关系。 如何利用数组下标来反映结点之间的逻辑关系如何利用数组下标来反映结点之间的逻辑关系? ?完全二叉树完全二叉树中结点的序号体现孩子、双亲之间中结点的序号体现孩子、双亲之间的逻辑关系的逻辑关系 。5.4 二叉树的存储结构及实现二叉树的存储结构及实现数据结构（C+版）2012辽宁科技大学软件学院2 A B C D E F G H I J数组下标数组下标
2、 0 1 2 3 4 5 6 7 8 9 完完全全二二叉叉树树的的存存储储A15234678910BCDEFGHIJ按编号按编号顺序存顺序存5.4 二叉树的存储结构及实现二叉树的存储结构及实现数据结构（C+版）2012辽宁科技大学软件学院3一一般般二二叉叉树树的的存存储储ABC DE F G数组下标数组下标 0 1 2 3 4 5 6 7 8 9 10 11 12ABCDFGE按编号按编号顺序存顺序存ABCDFGE123561013按照完全按照完全二叉树编号二叉树编号5.4 二叉树的存储结构及实现二叉树的存储结构及实现数据结构（C+版）2012辽宁科技大学软件学院4一棵斜树的顺序存储会怎样呢？
3、一棵斜树的顺序存储会怎样呢？深度为深度为k的右斜树，的右斜树，k个结点需分配个结点需分配2k1个存储单元。个存储单元。 一棵二叉树改造成完全一棵二叉树改造成完全二叉树形态，二叉树形态，需要增加需要增加很多空很多空结点点，造成存储，造成存储空间的浪费。空间的浪费。二叉树的顺序存储一般仅适合于存储二叉树的顺序存储一般仅适合于存储完全完全二叉树二叉树ABCD137155.4 二叉树的存储结构及实现二叉树的存储结构及实现数据结构（C+版）2012辽宁科技大学软件学院5二叉链表二叉链表基本思想：基本思想： 令二叉树的每个结点对应一个二叉链表结点令二叉树的每个结点对应一个二叉链表结点。 结点结构：结点结构
4、： lchild data rchild其中，其中，data：数据域，存放该结点的数据信息；：数据域，存放该结点的数据信息； lchild：左指针域，存放指向该结点左孩子的指针；：左指针域，存放指向该结点左孩子的指针； rchild：右指针域，存放：右指针域，存放指向该结点右孩子指向该结点右孩子的指针。的指针。 5.4 二叉树的存储结构及实现二叉树的存储结构及实现数据结构（C+版）2012辽宁科技大学软件学院6ABCDEFG二叉链表二叉链表具有具有n个结点的二叉链表中，有多少个空指针？个结点的二叉链表中，有多少个空指针？n+1头指针头指针root5.4 二叉树的存储结构及实现二叉树的存储结构及
5、实现数据结构（C+版）2012辽宁科技大学软件学院7template struct BiNode DataType data; BiNode *lchild, *rchild;lchild data rchild左孩子结点左孩子结点右孩子结点右孩子结点二叉链表结点的描述二叉链表结点的描述5.4 二叉树的存储结构及实现二叉树的存储结构及实现数据结构（C+版）2012辽宁科技大学软件学院8二二叉叉链链表表存存储储结结构构的的类类声声明明template class BiTree public: /构造函数，建立一棵二叉树构造函数，建立一棵二叉树 BiTree( )root = Creat(root
6、); /析构函数析构函数 BiTree( )Release(root); /前序遍历二叉树前序遍历二叉树 void PreOrder( )PreOrder(root); /中序遍历二叉树中序遍历二叉树 void InOrder( )InOrder(root); /后序遍历二叉树后序遍历二叉树 void PostOrder( )PostOrder(root); /层序遍历二叉树层序遍历二叉树 void LeverOrder( ); 5.4 二叉树的存储结构及实现二叉树的存储结构及实现数据结构（C+版）2012辽宁科技大学软件学院9二二叉叉链链表表存存储储结结构构的的类类声声明明private:
7、/指向根结点的头指针指向根结点的头指针 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辽宁科技大学软件学院
8、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中序遍历中序遍历递归算法递归算法
9、 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 BiTre
10、e : PostOrder(BiNode *bt) if (bt = NULL) return; /递归调用的结束条件递归调用的结束条件 else PostOrder(bt-lchild); /后序递归遍历后序递归遍历bt的左子树的左子树 PostOrder(bt-rchild); /后序递归遍历后序递归遍历bt的右子树的右子树 cout data; /访问根结点访问根结点bt的数据域的数据域 5.4 二叉树的存储结构及实现二叉树的存储结构及实现数据结构（C+版）2012辽宁科技大学软件学院13层序遍历层序遍历（广度优先遍历）（广度优先遍历）ABCDEFG遍历序列：遍历序列：AAB CBDCE
11、 F GD E F G5.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 二叉树的存储结构及实现二叉树的存储结构及实现数据结构
12、（C+版）2012辽宁科技大学软件学院15template 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-rc
13、hild != NULL) Q+rear = q-rchild; 5.4 二叉树的存储结构及实现二叉树的存储结构及实现数据结构（C+版）2012辽宁科技大学软件学院16二叉树的建立二叉树的建立为为了了建建立立一一棵棵二二叉叉树树，将将二二叉叉树树中中每每个个结结点点的的空空指指针针引引出出一一个个虚虚结结点点，其其值值为为一一特特定定值值如如“#”，以以标标识识其其为为空空，（每每个个结结点点都都有有左左右右孩孩子子）把把这这样样处处理后的二叉树称为原二叉树的扩展理后的二叉树称为原二叉树的扩展二叉树。二叉树。 为什么如此处理为什么如此处理? ?如何由一种遍历序列生成该二叉树？如何由一种遍历序列
14、生成该二叉树？5.4 二叉树的存储结构及实现二叉树的存储结构及实现数据结构（C+版）2012辽宁科技大学软件学院17扩展二叉树的前序遍历序列扩展二叉树的前序遍历序列: A B # D # # C # #DBAC#DBAC#二叉树的建立二叉树的建立5.4 二叉树的存储结构及实现二叉树的存储结构及实现数据结构（C+版）2012辽宁科技大学软件学院18设设二二叉叉树树中中的的结结点点均均为为一一个个字字符符。假假设设扩扩展展二二叉叉树树的的前前序序遍遍历历序序列列由由键键盘盘输输入入，root为为指指向向根根结结点点的的头头指指针针，二叉链表的建立过程是：二叉链表的建立过程是：首首先先输输入入根根结
15、结点点，若若输输入入的的是是一一个个“#”字字符符，则则表表明明该该二二叉叉树树为为空空树树，即即bt=NULL；否否则则输输入入的的字字符符应应该该赋赋给给bt-bt-data，之之后后依依次次递递归归建建立立它它的的左左子子树树和和右右子子树树 。二叉树的建立二叉树的建立5.4 二叉树的存储结构及实现二叉树的存储结构及实现数据结构（C+版）2012辽宁科技大学软件学院19template BiTree : BiTree( ) root = Creat(root); template BiNode *BiTree:Creat(BiNode *bt) cin ch; /输入结点的数据信息，假设
16、为字符输入结点的数据信息，假设为字符 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 遍历二叉树是二叉树
17、各种操作的基础，遍历算遍历二叉树是二叉树各种操作的基础，遍历算法中对每个结点的访问操作可以是多种形式及多个法中对每个结点的访问操作可以是多种形式及多个操作，根据遍历算法的框架，适当修改访问操作的操作，根据遍历算法的框架，适当修改访问操作的内容，可以派生出很多关于二叉树的应用算法。内容，可以派生出很多关于二叉树的应用算法。 void InOrder (BiNode *root) if (root=NULL) return; else InOrder(root-lchild); coutdata; InOrder(root-rchild); 5.4 二叉树的存储结构及实现二叉树的存储结构及实现数据
18、结构（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
19、& !root-rchild) coutdata; 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 二叉树的存储结构及实现二叉树的存储结构及实
20、现数据结构（C+版）2012辽宁科技大学软件学院24三叉链表三叉链表ABCDEFG在二叉链表中，如何求某结点的双亲？在二叉链表中，如何求某结点的双亲？root5.4 二叉树的存储结构及实现二叉树的存储结构及实现数据结构（C+版）2012辽宁科技大学软件学院25三叉链表三叉链表 lchild dataparent rchild在二叉链表的基础上增加了一个指向双亲的指针域。在二叉链表的基础上增加了一个指向双亲的指针域。结点结构结点结构其中：其中：data、lchild和和rchild三个域的含义同二叉链三个域的含义同二叉链表的结点结构；表的结点结构；parent域为域为指向该结点的双亲结点的指针。指向该结点的双亲结点的指针。 5.4 二叉树的存储结构及实现二叉树的存储结构及实现数据结构（C+版）2012辽宁科技大学软件学院26ABCDEFG三叉链表三叉链表5.4 二叉树的存储结构及实现二叉树的存储结构及实现数据结构（C+版）2012辽宁科技大学软件学院27ABCDEFG三叉链表的静态链表形式三叉链表的静态链表形式0123456data parent lchild rchildABCDEFG-1 0 0 1 2 2 3 1 3 4-1-1-1-1 2-1 5 6-1-1-15.4 二叉树的存储结构及实现二叉树的存储结构及实现
