2024王道408数据结构P144 T16

2024王道408数据结构P144 T16

思考过程

1. 首先看题目，要求我们把二叉树的叶子结点求出来并且用链表的方式存储，链接时用叶结点的右指针来存放单链表指针。我们很清楚可以看出来能用中序遍历+递归的方式实现，因为第一个叶子结点在整棵树的最左下角。
2. 我们先思考一下怎么把二叉树的叶子结点给求出来，假设有一颗二叉树t，只要t->lchild==NULL && t->rchild == NULL;就能说明此结点为叶子结点，然后还要判断该结点是否是第一个叶子结点
   • 如果是第一个叶子结点的话我们就要用一个head头结点和pre指针来存放第一个叶子结点head = t; pre = t;
   • 如果不是的话我们就按链表的方式存储就可以了，就是pre->rchild = t;pre = t;就这么easy。

举个例子

1. 首先请出我们的老演员二叉树我们需要一个头结点head和指针prestruct TreeNode* head = (struct TreeNode*)sizeof(struct TreeNode), *pre = NULL;pre指针我们就先赋值NULL。
2. 然后我们直接开始递归到最左边的结点也就是结点D，Inorder(t->lchild);因为是中序遍历，先访问左子树。访问到D之后判断该结点是叶子结点，此时D是第一个叶子结点，所以把head和pre都赋值为D然后我们都第一个叶子结点就成功加入到链表当中了。
3. 然后代码回溯到结点B，再去找B到右子树E。当找到E时判断该结点是否是第一个叶子结点，发现不是第一个结点所以我们就可以直接把它加入进链表当中
   让代码一直按中序遍历递归下去，这样题目就写完啦。

完整代码

//
// Created by 黎圣  on 2023/8/25.
//
#include "iostream"
typedef struct TreeNode
{char data;struct TreeNode *lchild, *rchild;
}*tree;
void CreateTree(tree &t)
{char ch = getchar();if (ch == '#')t = NULL;else{t = (struct TreeNode *)malloc(sizeof(struct TreeNode));t->data = ch;t->lchild = NULL;t->rchild = NULL;CreateTree(t->lchild);CreateTree(t->rchild);}
}
struct TreeNode *pre = NULL, *head = (struct TreeNode*)malloc(sizeof(struct TreeNode));
tree Inorder(tree &t)
{if (t){Inorder(t->lchild);if (t->lchild == NULL && t->rchild == NULL){//是否是第一个//是if (pre == NULL){head = t;pre = t;}//不是第一个else{pre->rchild = t;pre = t;}}Inorder(t->rchild);}return head;
}
int main()
{tree t;CreateTree(t);//ABD##E##CF##G##Inorder(t);while (head){printf("%c ", head->data);head = head->rchild;}return 0;
}

最后感谢b站up主@吸血小金鱼