中国建设银行官网站黄金部王毅,哈尔滨市人社app,hao123网址下载到桌面,excel+表格+做的网站一、已知一颗二叉树如下图#xff0c;试求#xff1a; (1)该二叉树前序、中序和后序遍历的结果。 (2)该二叉树是否为满二叉树#xff1f;是否为完全二叉树#xff1f; (3)将它转换成对应的树或森林。 (4)这颗二叉树的深度为多少? (5)试对该二叉树进行前序线索化。 (6)试对… 一、已知一颗二叉树如下图试求 (1)该二叉树前序、中序和后序遍历的结果。 (2)该二叉树是否为满二叉树是否为完全二叉树 (3)将它转换成对应的树或森林。 (4)这颗二叉树的深度为多少? (5)试对该二叉树进行前序线索化。 (6)试对该二叉树极性中序线索化。 (1) 前序遍历(根左右): a-b-d-g-e-c-f-h 中序遍历(左根右): d-g-b-e-a-f-h-c 后序遍历(左右根): g-d-e-b-h-f-c-a (2) 该二叉树不是满二叉树也不是完全二叉树。 (3) 二叉树到树和森林的转换,步骤如下 (1)首先将二叉树按照逆时针方向旋转45°。 (2)若某结点是其双亲的左子女则把该结点的右子女、右子女的右子女…都与该结点的双亲用线连起来。 (3)最后去掉原二叉树中所有双亲到齐右子女的连线。 对于上面这棵树我们首先将其旋转将并用线连接
然后我们删除所有双亲到其右子女的连线也就是红色的线 这样我们就把一颗二叉树转换成为森林了。 (4)这棵树的深度为4。 (5)对这颗二叉树进行前序线索化 穿线二叉树 所谓穿线二叉树即在一般二叉树的基础上对每个结点进行考察。 若其左子树为非空则其左指针不变仍指向左子女 若其左子树为空则让其左指针指向某种遍历顺序下该结点的前驱结点 若其右子树非空则其右指针不变仍指向右子女 若其右子树为空则让右子树指向某种遍历顺序下该节点的后继结点。 前序线索化: a-b-d-g-e-c-f-h (6)中序线索化 d-g-b-e-a-f-h-c 二、试描述树和二叉树的主要区别 一、性质不同树是一种数据结构二叉树是每个结点最多有两个子树的一种树结构。 二、结点不同树的每个结点有零个或多个子结点二叉树每个结点最多有两个子树。 三、种类不同树的种类包括无序树、有序树、二叉树和霍夫曼树等二叉树的种类包括完全二叉树、满二叉树和平衡二叉树。 三、试分别画出来具有3个结点的树和具有3个结点的二叉树的所有不同形态。 这里主要考察树和二叉树的区别树是无序的而二叉树是有序的。 树 二叉树 四、已知一颗二叉树的中序遍历结果为ABCEFGHD,后序遍历结果为ABFHGEDC,试画出此二叉树。 中序遍历即 左子树-根-右子树 后序遍历即 左子树-右子树-根 故由此我们首先可以根据后序遍历得知这棵树的根节点为C。 我们可以得知左子树的结点为AB右子树包含结点为 EFGHD。 对于左子树中序(左根右)和后序(左右根)一样那么可以推断A为左子树结点的左孩子B为根。 对于右子树后序遍历结果 FHGED 我们可以得知右子树的根节点为D。确定之后再根据前序遍历 EFGHD可以得知 EFGH 全部为 左子树上的结点。 根据基本判断先得出 中序 EFGH和后序 FHGE 可以得知 FGH为E的右子树然后根据后序 可以得之G为结点。 G为子树的结点根据中序可以得知F为左结点H为右结点。 五、已知一颗二叉树的前序遍历结果为ABCDEF中序遍历的结果为CBAEDF试画出此二叉树。 前序根左右ABCDEF 中序左根右CBAEDF 这个题给出前序和中序中序其实就是将所有的结点压下去压在同一水平线上然后进行排序。 (前序遍历其实就是顺着结点沿着左线而下。) 根据前序确定这棵树的根节点为A。 然后确定左子树和右子树
