怎样保证网站的安全性,免费行情软件app网站大全入口,企业解决方案英文,wordpress 嵌入地图2024王道408数据结构P144 T16
思考过程
首先看题目#xff0c;要求我们把二叉树的叶子结点求出来并且用链表的方式存储#xff0c;链接时用叶结点的右指针来存放单链表指针。我们很清楚可以看出来能用中序遍历递归的方式实现#xff0c;因为第一个叶子结点在整棵树的最左下…2024王道408数据结构P144 T16
思考过程
首先看题目要求我们把二叉树的叶子结点求出来并且用链表的方式存储链接时用叶结点的右指针来存放单链表指针。我们很清楚可以看出来能用中序遍历递归的方式实现因为第一个叶子结点在整棵树的最左下角。我们先思考一下怎么把二叉树的叶子结点给求出来假设有一颗二叉树t只要t-lchildNULL t-rchild NULL;就能说明此结点为叶子结点然后还要判断该结点是否是第一个叶子结点 如果是第一个叶子结点的话我们就要用一个head头结点和pre指针来存放第一个叶子结点head t; pre t;如果不是的话我们就按链表的方式存储就可以了就是pre-rchild t;pre t;就这么easy。
举个例子
首先请出我们的老演员二叉树我们需要一个头结点head和指针prestruct TreeNode* head (struct TreeNode*)sizeof(struct TreeNode), *pre NULL;pre指针我们就先赋值NULL。然后我们直接开始递归到最左边的结点也就是结点DInorder(t-lchild);因为是中序遍历先访问左子树。访问到D之后判断该结点是叶子结点此时D是第一个叶子结点所以把head和pre都赋值为D然后我们都第一个叶子结点就成功加入到链表当中了。然后代码回溯到结点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主吸血小金鱼
