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

《叉树的存储结构(顺序二叉三叉)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2012辽宁科技大学软件学院1顺序存储结构用一维数组存储二叉树中的结点，且结点的存储位置（下标）应能体现结点之间的逻辑关系—父子关系。如何利用数组下标来反映结点之间的逻辑关系?完全二叉树中结点的序号体现孩子、双亲之间的逻辑关系。5.4二叉树的存储结构及实现2012辽宁科技大学软件学院2ABCDEFGHIJ数组下标0123456789完全二叉树的存储A15234678910BCDEFGHIJ按编号顺序存5.4二叉树的存储结构及实现2012辽宁科技大学软件学院3一般二叉树的存储ABC∧DE∧∧∧F∧∧G数组下标0123456789101112ABCDFGE按编号顺序存ABCDFGE12356

2、1013按照完全二叉树编号5.4二叉树的存储结构及实现2012辽宁科技大学软件学院4一棵斜树的顺序存储会怎样呢？深度为k的右斜树，k个结点需分配2k－1个存储单元。一棵二叉树改造成完全二叉树形态，需要增加很多空结点，造成存储空间的浪费。二叉树的顺序存储一般仅适合于存储完全二叉树ABCD137155.4二叉树的存储结构及实现2012辽宁科技大学软件学院5二叉链表基本思想：令二叉树的每个结点对应一个二叉链表结点。结点结构：lchilddatarchild其中，data：数据域，存放该结点的数据信息；lchild：左指针域，存放指向该结点左孩子的指针；rchild：右指针域，存放指向该结点右孩

3、子的指针。5.4二叉树的存储结构及实现2012辽宁科技大学软件学院6ABCDEFG二叉链表具有n个结点的二叉链表中，有多少个空指针？n+1AC头指针rootF∧∧E∧∧B∧DG∧∧∧5.4二叉树的存储结构及实现2012辽宁科技大学软件学院7templatestructBiNode{DataTypedata;BiNode*lchild,*rchild;};lchilddatarchild左孩子结点右孩子结点二叉链表结点的描述5.4二叉树的存储结构及实现2012辽宁科技大学软件学院8二叉链表存储结构的类声明template

4、Type>classBiTree{public://构造函数，建立一棵二叉树BiTree(){root=Creat(root);}//析构函数~BiTree(){Release(root);}//前序遍历二叉树voidPreOrder(){PreOrder(root);}//中序遍历二叉树voidInOrder(){InOrder(root);}//后序遍历二叉树voidPostOrder(){PostOrder(root);}//层序遍历二叉树voidLeverOrder();5.4二叉树的存储结构及实现2012辽宁科技大学软件学院9二叉链表存储结构的类声明private://指向根结

5、点的头指针BiNode*root;//构造函数调用BiNode*Creat(BiNode*bt);//析构函数调用voidRelease(BiNode*bt);//前序遍历函数调用voidPreOrder(BiNode*bt);//中序遍历函数调用voidInOrder(BiNode*bt);//后序遍历函数调用voidPostOrder(BiNode*bt);};5.4二叉树的存储结构及实现2012辽宁科技大学软件学院10前序遍历——递归算法tem

6、platevoidBiTree::PreOrder(BiNode*bt){if(bt==NULL)return;//递归调用的结束条件else{cout<data;//访问根结点bt的数据域PreOrder(bt->lchild);//前序递归遍历bt的左子树PreOrder(bt->rchild);//前序递归遍历bt的右子树}}5.4二叉树的存储结构及实现2012辽宁科技大学软件学院11中序遍历——递归算法templatevoidBiTree::InOrd

7、er(BiNode*bt){if(bt==NULL)return;//递归调用的结束条件else{InOrder(bt->lchild);//中序递归遍历bt的左子树cout<data;//访问根结点bt的数据域InOrder(bt->rchild);//中序递归遍历bt的右子树}}5.4二叉树的存储结构及实现2012辽宁科技大学软件学院12后序遍历——递归算法template