叉树的存储结构(顺序二叉三叉
27页1、2012,辽宁科技大学软件学院,1,顺序存储结构,用一维数组存储二叉树中的结点,且结点的存储位置(下标)应能体现结点之间的逻辑关系父子关系。,如何利用数组下标来反映结点之间的逻辑关系?,完全二叉树中结点的序号体现孩子、双亲之间的逻辑关系 。,5.4 二叉树的存储结构及实现,2012,辽宁科技大学软件学院,2,完全二叉树的存储,A,B,C,D,E,F,G,H,I,J,按编号 顺序存,5.4 二叉树的存储结构及实现,2012,辽宁科技大学软件学院,3,一般二叉树的存储,A,B,C,D,F,G,E,按编号 顺序存,按照完全 二叉树编号,5.4 二叉树的存储结构及实现,2012,辽宁科技大学软件学院,4,一棵斜树的顺序存储会怎样呢?,深度为k的右斜树,k个结点需分配2k1个存储单元。,一棵二叉树改造成完全二叉树形态,需要增加很多空结点,造成存储空间的浪费。,二叉树的顺序存储一般仅适合于存储完全二叉树,5.4 二叉树的存储结构及实现,2012,辽宁科技大学软件学院,5,二叉链表,基本思想: 令二叉树的每个结点对应一个二叉链表结点。,结点结构:,其中,data:数据域,存放该结点的数据信息; lc
2、hild:左指针域,存放指向该结点左孩子的指针; rchild:右指针域,存放指向该结点右孩子的指针。,5.4 二叉树的存储结构及实现,2012,辽宁科技大学软件学院,6,二叉链表,具有n个结点的二叉链表中,有多少个空指针?,n+1,5.4 二叉树的存储结构及实现,2012,辽宁科技大学软件学院,7,template struct BiNode DataType data; BiNode *lchild, *rchild; ;,二叉链表结点的描述,5.4 二叉树的存储结构及实现,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); /
3、层序遍历二叉树 void LeverOrder( );,5.4 二叉树的存储结构及实现,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 二叉树的存储结构及实现,2012,辽宁科技大学软件学院,10,前序遍历递归算法,template void BiTree : PreOrder(BiNode *bt) if (bt = NULL) return; /递归调用的结束条件 else cout data; /访问根结点bt的数据域 PreOrder(bt-lchild); /前序递归遍历bt的左子树 PreOrder(bt-rchild); /前
4、序递归遍历bt的右子树 ,5.4 二叉树的存储结构及实现,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 二叉树的存储结构及实现,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 二叉树的存储结构及实现,2012,辽宁科技大学软件学院,13,层序遍历(广度
《叉树的存储结构(顺序二叉三叉》由会员san****019分享,可在线阅读,更多相关《叉树的存储结构(顺序二叉三叉》请在金锄头文库上搜索。
高中化学实验方案的设计第一节制备实验方案设计
高中生物实验室配置
高中体育与健康课程田径必修模块单元教学方案
高中通用技术方案的构思方法-设计分析教案苏教版必修
高中生物室配置
高中信息技术网络技术应用选修模块教学评价方案
骆小学教师戏曲知识培训方案(I)
麻村小学阳光体育活动计划及实施方案
高桥小学幼小衔接活动方案
马摆小学控辍保学实施方案
金阳街道中心小学未成年人思想道德建设实施方案
龙扬小学第32个爱国卫生月活动方案
魏家井联小学度控辍保学工作方案
高区第九届初中骨干教师课堂教学能力展示活动
长沙县2018年度小学生课外阅读知识竞赛及书目
阳江中心小学一月一事之五月主题活动方案
长营小学校园体育活动实施方案
高考历史备考方案-陈军
高考语文第5课父亲课前预案苏教版选修现代散文选读
高考语文第9课铃兰花课前预案苏教版选修现代散文选读
2024-04-11 25页
2024-04-11 37页
2024-04-11 28页
2024-04-11 31页
2024-04-11 36页
2024-04-11 29页
2024-04-11 22页
2024-04-11 27页
2024-04-11 34页
2024-04-11 32页