叉树的存储结构(顺序二叉三叉
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：数据域，存放该结点的数据信息； lchild：左指针域，存放指向该结点左孩子的指针； 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); /层序遍历二叉树 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); /前序递归遍历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,层序遍历（广度优先遍历）,遍历序列：,A,A,B,C,B,D,C,E,F,G,D,E,F,G,5.4 二叉树的存储结构及实现,2012,辽宁科技大学软件学院,14,层序遍历,队列Q初始化； 2. 如果二叉树非空，将根指针入队； 3. 循环直到队列Q为空 3.1 队列Q的队头元素出队，q指向队头结点； 3.2 访问结点q的数据域； 3.3 若q-lchild非空，则将其入队； 3.4 若q-rchild非空，则将其入队；,5.4 二叉树的存储结构及实现,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 二叉树的存储结构及实现,2012,辽宁科技大学软件学院,16,二叉树的建立,为了建立一棵二叉树，将二叉树中每个结点的空指针引出一个虚结点，其值为一特定值如“#”，以标识其为空，（每个结点都有左右孩子）把这样处理后的二叉树称为原二叉树的扩展二叉树。,为什么如此处理?,如何由一种遍历序列生成该二叉树？,5.4 二叉树的存储结构及实现,2012,辽宁科技大学软件学院,17,扩展二叉树的前序遍历序列: A B # D # # C # #,二叉树的建立,5.4 二叉树的存储结构及实现,2012,辽宁科技大学软件学院,18,设二叉树中的结点均为一个字符。假设扩展二叉树的前序遍历序列由键盘输入，root为指向根结点的头指针，二叉链表的建立过程是： 首先输入根结点，若输入的是一个“#”字符，则表明该二叉树为空树，即bt=NULL；否则输入的字符应该赋给bt-data，之后依次递归建立它的左子树和右子树 。,二叉树的建立,5.4 二叉树的存储结构及实现,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 二叉树的存储结构及实现,2012,辽宁科技大学软件学院,20,遍历二叉树是二叉树各种操作的基础，遍历算法中对每个结点的访问操作可以是多种形式及多个操作，根据遍历算法的框架，适当修改访问操作的内容，可以派生出很多关于二叉树的应用算法。,void InOrder (BiNode *root) if (root=NULL) return; else InOrder(root-lchild); coutdata; InOrder(root-rchild); ,5.4 二叉树的存储结构及实现,2012,辽宁科技大学软件学院,21,设计算法求二叉树的结点个数。,int Count(BiNode *root) if (!root) return 0； else return Count(root-lchild) +Count(root-rchild)+1; ,5.4 二叉树的存储结构及实现,2012,辽宁科技大学软件学院,22,设计算法按前序次序打印二叉树中的叶子结点。,void PreOrder(BiNode *root) if (root) if (!root-lchild ,5.4 二叉树的存储结构及实现,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 二叉树的存储结构及实现,2012,辽宁科技大学软件学院,24,三叉链表,在二叉链表中，如何求某结点的双亲？,5.4 二叉树的存储结构及实现,2012,辽宁科技大学软件学院,25,三叉链表,在二叉链表的基础上增加了一个指向双亲的指针域。,结点结构,其中：data、lchild和rchild三个域的含义同二叉链表的结点结构； parent域为指向该结点的双亲结点的指针。,5.4 二叉树的存储结构及实现,2012,辽宁科技大学软件学院,26,三叉链表,5.4 二叉树的存储结构及实现,2012,辽宁科技大学软件学院,27,三叉链表的静态链表形式,5.4 二叉树的存储结构及实现,
