。

我们很清楚可以看出来能用中序遍历递归的方式实现#xff0c;因为第一个叶子结点在整棵树的最左下…2024王道408数据结构P144

T16

首先看题目要求我们把二叉树的叶子结点求出来并且用链表的方式存储链接时用叶结点的右指针来存放单链表指针。

我们很清楚可以看出来能用中序遍历递归的方式实现因为第一个叶子结点在整棵树的最左下角。

我们先思考一下怎么把二叉树的叶子结点给求出来假设有一颗二叉树t只要t-lchildNULL

t-rchild

NULL;就能说明此结点为叶子结点然后还要判断该结点是否是第一个叶子结点

如果是第一个叶子结点的话我们就要用一个head头结点和pre指针来存放第一个叶子结点head

pre

t;如果不是的话我们就按链表的方式存储就可以了就是pre-rchild

t;pre

首先请出我们的老演员二叉树我们需要一个头结点head和指针prestruct

TreeNode*

NULL;pre指针我们就先赋值NULL。

然后我们直接开始递归到最左边的结点也就是结点DInorder(t-lchild);因为是中序遍历先访问左子树。

访问到D之后判断该结点是叶子结点此时D是第一个叶子结点所以把head和pre都赋值为D然后我们都第一个叶子结点就成功加入到链表当中了。

然后代码回溯到结点B再去找B到右子树E。

当找到E时判断该结点是否是第一个叶子结点发现不是第一个结点所以我们就可以直接把它加入进链表当中

完整代码

NULL;CreateTree(t-lchild);CreateTree(t-rchild);}

struct

t;CreateTree(t);//ABD##E##CF##G##Inorder(t);while

(head){printf(%c