《数据结构-树和二叉树2》由会员分享，可在线阅读，更多相关《数据结构-树和二叉树2（76页珍藏版）》请在金锄头文库上搜索。
1、写出下面二叉树的前序、中序和后序序列若已知一棵二叉树的前序序列和中序序列，能否 唯一确定这棵二叉树呢？怎样确定？ 例如：已知一棵二叉树的前序遍历序列和中序遍历 序列分别为ABCDEFGHI 和BCAEDGHFI，如何构 造该二叉树呢? 5.3 二叉树的逻辑结构二叉树的遍历操作 前序：A B C D E F G H I 中序：B C A E D G H F I前序：B C 中序：B C5.3 二叉树的逻辑结构B C D E F G H IA前序： D E F G H I 中序： E D G H F IABCDEFG HI前序：F G H I 中序：G H F I5.3 二叉树的逻辑结构前序： D
2、 E F G H I 中序： E D G H F IABCDEFG HIABCDEFIGH1. 根据前序序列的第一个元素建立根结点； 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遍历序列：AAB CBDCE F GD E F G层序遍历1. 队列Q初始化； 2. 如果二叉树非空，将根指针入队； 3. 循环直到队列Q为空3.1 q=队列Q的队头元素出队；3.2 访问结点q的数据域；3.3 若结点q存在左孩子，则将左孩子指针入队；3.4 若结点q存在右孩子，则将右孩子指针入队；5.4 二叉树的存储结构及实现二叉树算法设计练习设计算法按前序次序打印
4、二叉树中的叶子结点。 void PreOrder(BiNode *root) if (root) if (!root-lchild PreOrder(root-lchild);PreOrder(root-rchild); 二叉树算法设计练习设计算法求二叉树的叶子结点。 int Count(BiNode *root) if (root= =NULL) return 0;else if(root-rchild=NULL c1= Count(root -lchild);c2= Count(root -rchild);return c1+c2; 三叉链表5.4 二叉树的存储结构及实现GFEDBAABC
5、DEFGC在二叉链表中，如何求某结点的双亲？三叉链表lchild dataparent rchild在二叉链表的基础上增加了一个指向双亲的指针域。结点结构其中：data、lchild和rchild三个域的含义同二 叉链表的结点结构；parent域为指向该结点的双亲结点的指针。 5.4 二叉树的存储结构及实现ABCDEFGABDEFCG三叉链表5.4 二叉树的存储结构及实现线索链表5.4 二叉树的存储结构及实现如何保存二叉树的某种遍历序列？ABCDEFG中序遍历序列：D G B A E C F如果二叉树不改变，如何保存？顺序 存储D G B A F C F线索链表5.4 二叉树的存储结构及实现如
6、何保存二叉树的某种遍历序列？ABCDEFG中序遍历序列：D G B A E C F如果二叉树改变，如何保存？链接 存储D F 线索链表5.4 二叉树的存储结构及实现如何保存二叉树的某种遍历序列？ABCDEFG中序遍历序列：D G B A E C F如何将二叉链表与中序链表结合？链接 存储D F 线索链表线索：将二叉链表中的空指针域指向前驱结点和后继 结点的指针被称为线索； 线索化：使二叉链表中结点的空链域存放其前驱或后 继信息的过程称为线索化； 线索二叉树：加上线索的二叉树称为线索二叉树。5.4 二叉树的存储结构及实现如何保存二叉树的某种遍历序列？将二叉链表中的空指针域指向其前驱结点和后继结点
7、ltag lchild data child rtag0: lchild指向该结点的左孩子 1: lchild指向该结点的前驱结点 0: rchild指向该结点的右孩子 1: rchild指向该结点的后继结点ltag=rtag=5.4 二叉树的存储结构及实现结点结构线索链表enum flag Child, Thread; template struct ThrNode T data;ThrNode *lchild, *rchild;flag ltag, rtag; ;5.4 二叉树的存储结构及实现线索链表ltag lchild data child rtag结点结构二叉树的遍历方式有4种，故有
8、4种意义下的前驱和后 继，相应的有4种线索二叉树： 前序线索二叉树 中序线索二叉树 后序线索二叉树 层序线索二叉树5.4 二叉树的存储结构及实现线索二叉树FABDCEG中序线索二叉树5.4 二叉树的存储结构及实现线索二叉树中序序列：D G B A E C Ftemplate class InThrBiTree public:InThrBiTree(ThrNode * root); InThrBiTree( ); ThrNode *Net(ThrNode *p); void InOrder(ThrNode *root); private:ThrNode *root; void Creat(Thr
9、Node *root); void ThrBiTree(ThrNode *root); ;5.4 二叉树的存储结构及实现中 序 线 索 链 表 类 的 声 明分析：建立线索链表，实质上就是将二叉链表中的空 指针改为指向前驱或后继的线索，而前驱或后继的信 息只有在遍历该二叉树时才能得到。5.4 二叉树的存储结构及实现建立二叉链表遍历二叉树，将空指针改为线索中序线索链表的建立构造函数A头指针BCDEFG00000000000000中序线索链表 的建立过程5.4 二叉树的存储结构及实现已经建立起二叉链表A头指针BCDEFG00000000000000中序线索链表 的建立过程5.4 二叉树的存储结构及
10、实现中序遍历二叉链表 p为正在访问的结点 pre为刚访问的结点p1A头指针BCDEFG00000000000000中序线索链表 的建立过程5.4 二叉树的存储结构及实现中序遍历二叉链表 p为正在访问的结点 pre为刚访问的结点pre1p1A头指针BCDEFG00000000000000中序线索链表 的建立过程5.4 二叉树的存储结构及实现中序遍历二叉链表 p为正在访问的结点 pre为刚访问的结点pre11p1A头指针BCDEFG00000000000000中序线索链表 的建立过程5.4 二叉树的存储结构及实现中序遍历二叉链表 p为正在访问的结点 pre为刚访问的结点pre11p11A头指针BC
11、DEFG00000000000000中序线索链表 的建立过程5.4 二叉树的存储结构及实现中序遍历二叉链表 p为正在访问的结点 pre为刚访问的结点 pre11p 111A头指针BCDEFG00000000000000中序线索链表 的建立过程5.4 二叉树的存储结构及实现中序遍历二叉链表 p为正在访问的结点 pre为刚访问的结点pre11p1111A头指针BCDEFG00000000000000中序线索链表 的建立过程5.4 二叉树的存储结构及实现中序遍历二叉链表 p为正在访问的结点 pre为刚访问的结点pre 11p 11111A头指针BCDEFG00000000000000中序线索链表 的
12、建立过程5.4 二叉树的存储结构及实现中序遍历二叉链表 p为正在访问的结点 pre为刚访问的结点pre11111111在遍历过程中，访问当前结点root的操作为： 如果root的左、右指针域为空，则将相应标志置1； 若root的左指针域为空，则令其指向它的前驱，这 需要设指针pre始终指向刚刚访问过的结点，显然pre 的初值为NULL；若pre的右指针域为空，则令其指向 它的后继，即当前访问的结点root; 令pre指向刚刚访问过的结点root；5.4 二叉树的存储结构及实现中序线索链表的建立1. 建立二叉链表，将每个结点的左右标志置为0； 2. 遍历二叉链表，建立线索；2.1 如果二叉链表r
13、oot为空，则空操作返回；2.2 对root的左子树建立线索；2.3 对根结点root建立线索；2.3.1 若root没有左孩子，则为root加上前驱线索;2.3.2 若root没有右孩子，则将root右标志置为1；2.3.3 若结点pre右标志为1，则为pre加上后继线索；2.3.4 令pre指向刚刚访问的结点root；2.4 对root的右子树建立线索。5.4 二叉树的存储结构及实现中序线索链表的建立构造函数树的抽象数据类型定义ADT Tree Data树是由一个根结点和若干棵子树构成，树中结点具有相同数据类型及层次关系 OperationInitTree前置条件：树不存在输入：无功能：初
14、始化一棵树 输出：无后置条件：构造一个空树5.1 树的逻辑结构DestroyTree前置条件：树已存在输入：无功能：销毁一棵树输出：无后置条件：释放该树占用的存储空间Root 前置条件：树已存在输入：无功能：求树的根结点输出：树的根结点的信息后置条件：树保持不变 树的抽象数据类型定义5.1 树的逻辑结构Parent前置条件：树已存在输入：结点功能：求结点的双亲输出：结点的双亲的信息 后置条件：树保持不变 Depth前置条件：树已存在输入：无功能：求树的深度输出：树的深度 后置条件：树保持不变树的抽象数据类型定义5.1 树的逻辑结构PreOrder 前置条件：树已存在输入：无功能：前序遍历树输出
15、：树的前序遍历序列后置条件：树保持不变 PostOrder 前置条件：树已存在 输入：无功能：后序遍历树输出：树的后序遍历序列后置条件：树保持不变 endADT树的抽象数据类型定义5.1 树的逻辑结构树的遍历操作 树的遍历：从根结点出发，按照某种次序访问树中所 有结点，使得每个结点被访问一次且仅被访问一次。 如何理解访问?抽象操作，可以是对结点进行的各种处理，这里简 化为输出结点的数据。如何理解次序? 树通常有前序（根）遍历、后序（根）遍历和层序 （次）遍历三种方式。5.1 树的逻辑结构树结构（非线性结构）线性结构。遍历的实质?前序遍历 树的前序遍历操作定义为：若树为空，则空操作返回；否则 访问根结点； 按照从左到右的顺序前序遍历根结点的每一棵子树。 5.1 树的逻辑结构前序遍历序列： A B D E H I F C GACBGFEDHI后序遍历 树的后序遍历操作定义为：若树为空，则空操作返回；否则 按照从左到右的顺序后序遍历根结点的每一棵子树； 访问根结点。 5.1 树的逻辑结构后序遍历序列： D H I E F B G C AACBGFEDHI层序遍历 树的层序遍历操作定义为：从树的第一层（即根结点）开始，自上而下逐层遍历，在同一层中，按从左到右的 顺序对结点逐个访问。 5.1 树的逻辑结构层序遍历序列： A B C D
