Day 4编程任务：前序遍历序列中如何找到第k个结点的值？
- 内容介绍
- 文章标签
- 相关推荐
本文共计734个文字，预计阅读时间需要3分钟。
问题描述：假设使用二叉树采用二叉链表存储结构，设计一个算法，求前序遍历序列中第K个节点的节点值。
问题解决：如果对程序没有时间和空间上的要求，我们可以直接使用前序遍历二叉树，并记录遍历到的第K个节点。下面是具体的算法步骤：
1. 创建一个全局变量，用于记录当前遍历到的节点数。
2.定义一个递归函数，用于进行前序遍历。
3.在递归函数中，首先访问当前节点，并检查当前遍历到的节点数是否等于K。
4.如果等于K，则输出当前节点的值。
5.然后递归访问左子树和右子树。
具体代码如下：
python
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val=val self.left=left self.right=rightdef findKthNode(root, k): global count count=0 def preorder(node): nonlocal count if not node: return count +=1 if count==k: print(node.val) return preorder(node.left) preorder(node.right) preorder(root)
示例root=TreeNode(1)root.left=TreeNode(2)root.right=TreeNode(3)root.left.left=TreeNode(4)root.left.right=TreeNode(5)findKthNode(root, 3)
以上代码中，我们定义了一个二叉树节点类`TreeNode`，然后定义了一个`findKthNode`函数来找到前序遍历序列中的第K个节点。在递归函数`preorder`中，我们记录遍历到的节点数，并在找到第K个节点时输出其值。
问题描述
假设二叉树采用二叉链表存储结构，设计一个算法，求前序遍历序列中第K个结点的结点值。
问题解决
如果对程序没有时间和空间上的要求，处理前序遍历之类的问题我们一般采用递归的算法。
递归过程中计数：
静态局部变量 全局变量 引用参数
#include<stdio.h>
#include<stdlib.h>
#define OVERFLOW -2
#define OK 1
#define ERROR 0
typedef int Status;
typedef char TElemType;
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
Status CreateBiTree(BiTree *T)
{
char ch;
ch=getchar();
if(ch=='#')
*T=NULL;
else
{
(*T)=(BiTNode*)malloc(sizeof(BiTNode));
if(!*T)
exit(OVERFLOW);
(*T)->data=ch;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
return OK;
}
Status PreOrderTraverse(BiTree T,Status (*visit)(TElemType e))
{
if(T)
{
(*visit)(T->data);
PreOrderTraverse(T->lchild,visit);
PreOrderTraverse(T->rchild,visit);
}
else
return OK;
}
Status visit(TElemType e)
{
printf("%c\t",e);
return OK;
}
Status fun1(BiTree T,int k,BiTree *p)
{
static int n=0;
if(T)
{
n++;
if(n==k)
{
*p=T;
}
fun1(T->lchild,k,p);
fun1(T->rchild,k,p);
}
if(T)
printf("%c",T->data);
else
printf("NULL");
printf("%d\n",n);
return k;
}
int main()
{
BiTree T,p;
int k;
printf("请输入一个二叉链表：");
CreateBiTree(&T);
printf("先序遍历后的链表为：\n");
PreOrderTraverse(T,visit);
printf("\n请输入k的值：\n");
scanf("%d",&k);
fun1(T,k,&p);
printf("第%d个结点的结点值为%c",k,p->data);
return 0;
}
本文共计734个文字，预计阅读时间需要3分钟。
问题描述：假设使用二叉树采用二叉链表存储结构，设计一个算法，求前序遍历序列中第K个节点的节点值。
问题解决：如果对程序没有时间和空间上的要求，我们可以直接使用前序遍历二叉树，并记录遍历到的第K个节点。下面是具体的算法步骤：
1. 创建一个全局变量，用于记录当前遍历到的节点数。
2.定义一个递归函数，用于进行前序遍历。
3.在递归函数中，首先访问当前节点，并检查当前遍历到的节点数是否等于K。
4.如果等于K，则输出当前节点的值。
5.然后递归访问左子树和右子树。
具体代码如下：
python
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val=val self.left=left self.right=rightdef findKthNode(root, k): global count count=0 def preorder(node): nonlocal count if not node: return count +=1 if count==k: print(node.val) return preorder(node.left) preorder(node.right) preorder(root)
示例root=TreeNode(1)root.left=TreeNode(2)root.right=TreeNode(3)root.left.left=TreeNode(4)root.left.right=TreeNode(5)findKthNode(root, 3)
以上代码中，我们定义了一个二叉树节点类`TreeNode`，然后定义了一个`findKthNode`函数来找到前序遍历序列中的第K个节点。在递归函数`preorder`中，我们记录遍历到的节点数，并在找到第K个节点时输出其值。
问题描述
假设二叉树采用二叉链表存储结构，设计一个算法，求前序遍历序列中第K个结点的结点值。
问题解决
如果对程序没有时间和空间上的要求，处理前序遍历之类的问题我们一般采用递归的算法。
递归过程中计数：
静态局部变量 全局变量 引用参数
#include<stdio.h>
#include<stdlib.h>
#define OVERFLOW -2
#define OK 1
#define ERROR 0
typedef int Status;
typedef char TElemType;
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
Status CreateBiTree(BiTree *T)
{
char ch;
ch=getchar();
if(ch=='#')
*T=NULL;
else
{
(*T)=(BiTNode*)malloc(sizeof(BiTNode));
if(!*T)
exit(OVERFLOW);
(*T)->data=ch;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
return OK;
}
Status PreOrderTraverse(BiTree T,Status (*visit)(TElemType e))
{
if(T)
{
(*visit)(T->data);
PreOrderTraverse(T->lchild,visit);
PreOrderTraverse(T->rchild,visit);
}
else
return OK;
}
Status visit(TElemType e)
{
printf("%c\t",e);
return OK;
}
Status fun1(BiTree T,int k,BiTree *p)
{
static int n=0;
if(T)
{
n++;
if(n==k)
{
*p=T;
}
fun1(T->lchild,k,p);
fun1(T->rchild,k,p);
}
if(T)
printf("%c",T->data);
else
printf("NULL");
printf("%d\n",n);
return k;
}
int main()
{
BiTree T,p;
int k;
printf("请输入一个二叉链表：");
CreateBiTree(&T);
printf("先序遍历后的链表为：\n");
PreOrderTraverse(T,visit);
printf("\n请输入k的值：\n");
scanf("%d",&k);
fun1(T,k,&p);
printf("第%d个结点的结点值为%c",k,p->data);
return 0;
}