数据结构-树和二叉树2.ppt

《数据结构-树和二叉树2.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、写出下面二叉树的前序、中序和后序序列若已知一棵二叉树的前序序列和中序序列，能否唯一确定这棵二叉树呢？怎样确定？例如：已知一棵二叉树的前序遍历序列和中序遍历序列分别为ABCDEFGHI和BCAEDGHFI，如何构造该二叉树呢?5.3二叉树的逻辑结构二叉树的遍历操作前序：ABCDEFGHI中序：BCAEDGHFI前序：BC中序：BC5.3二叉树的逻辑结构BCDEFGHIA前序：DEFGHI中序：EDGHFIABCDEFGHI前序：FGHI中序：GHFI5.3二叉树的逻辑结构前序：DEFGHI中序：EDGHFIAB

2、CDEFGHIABCDEFIGH1.根据前序序列的第一个元素建立根结点；2.在中序序列中找到该元素，确定根结点的左右子树的中序序列；3.在前序序列中确定左右子树的前序序列；4.由左子树的前序序列和中序序列建立左子树；5.由右子树的前序序列和中序序列建立右子树。5.3二叉树的逻辑结构已知一棵二叉树的前序序列和中序序列，构造该二叉树的过程如下：二叉树的遍历操作作业一棵深度为5的满二叉树有个分支结点和个叶子。一棵具有1234个结点的完全二叉树，它的深度为。设一棵完全二叉树有1000个结点，则共有个叶子结点。作业给定

3、二叉树的两种遍历序列，分别是：前序遍历序列：D，A，C，E，B，H，F，G，I；中序遍历序列：D，C，B，E，H，A，G，I，F，试画出二叉树B层序遍历5.4二叉树的存储结构及实现ABCDEFG遍历序列：AABCBDCEFGDEFG层序遍历队列Q初始化；2.如果二叉树非空，将根指针入队；3.循环直到队列Q为空3.1q=队列Q的队头元素出队；3.2访问结点q的数据域；3.3若结点q存在左孩子，则将左孩子指针入队；3.4若结点q存在右孩子，则将右孩子指针入队；5.4二叉树的存储结构及实现二叉树算法设计练习设计算法

4、按前序次序打印二叉树中的叶子结点。voidPreOrder(BiNode*root){if(root){if(!root->lchild&&!root->rchild)cout<data;PreOrder(root->lchild);PreOrder(root->rchild);}}二叉树算法设计练习设计算法求二叉树的叶子结点。intCount(BiNode*root){if(root==NULL)return0;else{if(root->rchild==NULL&&root->rchild=

5、=NULL)return1;c1=Count(root->lchild);c2=Count(root->rchild);returnc1+c2;}}三叉链表5.4二叉树的存储结构及实现GFEDBAABCDEFG∧∧∧∧∧∧∧∧C在二叉链表中，如何求某结点的双亲？三叉链表lchilddataparentrchild在二叉链表的基础上增加了一个指向双亲的指针域。结点结构其中：data、lchild和rchild三个域的含义同二叉链表的结点结构；parent域为指向该结点的双亲结点的指针。5.4二叉树的存储结构及实

6、现ABCDEFGA∧B∧D∧E∧F∧CG∧∧∧∧三叉链表5.4二叉树的存储结构及实现线索链表5.4二叉树的存储结构及实现如何保存二叉树的某种遍历序列？ABCDEFG中序遍历序列：DGBAECF如果二叉树不改变，如何保存？顺序存储DGBAFCF线索链表5.4二叉树的存储结构及实现如何保存二叉树的某种遍历序列？ABCDEFG中序遍历序列：DGBAECF如果二叉树改变，如何保存？链接存储DF线索链表5.4二叉树的存储结构及实现如何保存二叉树的某种遍历序列？ABCDEFG中序遍历序列：DGBAECF如何将二叉链表与中

7、序链表结合？链接存储DF线索链表线索：将二叉链表中的空指针域指向前驱结点和后继结点的指针被称为线索；线索化：使二叉链表中结点的空链域存放其前驱或后继信息的过程称为线索化；线索二叉树：加上线索的二叉树称为线索二叉树。5.4二叉树的存储结构及实现如何保存二叉树的某种遍历序列？将二叉链表中的空指针域指向其前驱结点和后继结点ltaglchilddatachildrtag0:lchild指向该结点的左孩子1:lchild指向该结点的前驱结点0:rchild指向该结点的右孩子1:rchild指向该结点的后继结点ltag=

8、rtag=5.4二叉树的存储结构及实现结点结构线索链表enumflag{Child,Thread};templatestructThrNode{Tdata;ThrNode*lchild,*rchild;flagltag,rtag;};5.4二叉树的存储结构及实现线索链表ltaglchilddatachildrtag结点结构二叉树的遍历方式有4种，故有4种意义下的前驱和后继，相应