2024王道408数据结构 P144 T10
思考过程
- 这题也比较简单,首先看题目,要求我们用先序遍历求二叉树中第k个结点的值。那道理我们都懂直接开始敲代码。
- 先建立一个计数器i和一个char类型的值ch,用来暂时存放data值
- 当i==k时就说明已经找到第k个结点了,我们只需要返回当前二叉树的data值就好了
if (i==k) return t->data;
- 当i不等于k时就说明没有找到第k个结点,此时先让
i++
,然后再去用递归去遍历当前结点的左子树,PreNode(t->lchild, k);
- 在遍历右子树之前先判断ch的值
- 如果此时ch不等于’#',也就是该结点不为空,就说明左子树还没有遍历完,我们就已经找到了第k个结点,那我们直接
return ch;
就好了。
- 如果ch=='#'就说明左子树已经遍历完了,我们依然没有找到第k个结点,那我们就递归开始遍历右子树
ch = PreNode(t->rchild, k);
- 整个代码逻辑就是这样了。
举个例子
- 假设我们此时的二叉树长这个样子先序遍历序列时ABDECFG,再假设此时k=3,也就是结点D。
- 先是建立一个变量i=1,此时i不等于k,i++,用该函数递归调用去遍历A的左子树B,再用一个变量ch去暂时存储B的值,再去判断此时i仍然不等于k,i++。
- 再去遍历B的左子树D,这就是用递归去先序遍历二叉树,此时发现i==k,则返回ch值。
完整代码
//
// Created by 黎圣 on 2023/8/17.
//
#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);
}
}
int i = 1;
char ch;
char PreNode(tree &t, int k)
{
if (t == NULL)
return '#';
if (i == k)
return t->data;
else
i++;
ch = PreNode(t->lchild, k);
if (ch != '#')
return ch;
ch = PreNode(t->rchild, k);
return ch;
}
int main()
{
tree t;
CreateTree(t);
//ABD##E##CF##G##
printf("%c", PreNode(t, 4));
return 0;
}
这题也不难嗷,感谢b站up主@吸血小金鱼