【数据结构】二叉树经典例题—＜你真的掌握二叉树了吗？＞(第一弹)

admin • 2023-11-12 20:36 • 5G

一、已知一颗二叉树如下图，试求：

(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为右结点。