你好，请帮忙编写递归和非递归算法,在二叉树中求位于先序序列中第K个位置的结点，用c语言写？？

Question

如题所述

Answer 1

#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -1

typedef struct _Tree{
char data;
struct _Tree *lchild, *rchild;
}Tree;

typedef struct _List{
Tree *data;
struct _List *next;
}List;

typedef struct _stack{
List *top;
int size;
}Stack;

Tree* getTop(Stack stack)
{
if (stack.size > 0)
return (stack.top)->data;
return NULL;
}

int Pop(Stack *stack)
{
if (stack->size > 0){
List *top = stack->top;
stack->top = top->next;
stack->size--;
free(top);
return OK;
}
return ERROR;
}

int Push(Stack *stack, Tree *tree)
{
List *node = (List*)malloc(sizeof(List));
if (!node) exit(OVERFLOW);
node->data = tree;
node->next = stack->top;
stack->top = node;
stack->size++;
return OK;
}

void init(Tree **tree)
{
//输入一个字符作为该节点的数据，
//如果输入空格，'_'代表节点为NULL，先序输入字符
char data;
*tree = NULL;
data = getchar();
if (data != '_'){
*tree = (Tree*)malloc(sizeof(Tree));
(*tree)->data = data;
init(&(*tree)->lchild); //初始化左子树
init(&(*tree)->rchild); //初始化右子树
}
}

Tree* findPreKey1(Tree *tree, int K)
{
//二叉树中求位于先序序列中第K个位置的结点
//如果函数返回的结果为NULL, 则说明不存在
//递归版本
Tree* _findPreKey1(Tree *tree, int *p);
int p[1] = {K};
Tree *node;
node = _findPreKey1(tree, p);
return node;
}

Tree* _findPreKey1(Tree *tree, int *p)
{
Tree *node;
if (tree != NULL){
if (*p == 1) //当*p == 1时，则这个节点就是需要查找的节点
return tree;
else{
if (tree->lchild != NULL){
//如果tree的左子树不为NULL，结果即为左子树的先序序列的第*p-1个元素
(*p)--;
node = _findPreKey1(tree->lchild, p);
}
if (*p == 1) //在左子树中找到第K个元素,返回结果
return node;
//当在左子树已经遍历完，此时有*p != 1，即还没遍历到第K个元素
if (tree->rchild != NULL){
//如果右子树不为NULL，此时已经遍历了K-*p + 1个元素，那么结果即为右子树的先序
//序列的第*p-1个元素
(*p)--;
node = _findPreKey1(tree->rchild, p);
}
return node;
}
}
return NULL;
}

Tree* findPreKey2(Tree *tree, int K)
{
//二叉树中求位于先序序列中第K个位置的结点
//如果函数返回的结果为NULL, 则说明不存在
//非递归版本
Stack s = {top:NULL, size:0};
List *top;
Tree *node;
f(tree == NULL)
return NULL;
else{
Push(&s, tree);
while(K != 1 && s.size > 0){
node = getTop(s);
Pop(&s);
if (node->rchild)
Push(&s, node->rchild);
if (node->lchild)
Push(&s, node->lchild);
K--;
}
if (K == 1)
return getTop(s);
else
return NULL;
}
}

int main()
{
Tree *tree, *node1, *node2;
int K;
printf("按先序建立二叉树，'_'(下画线)代表节点为NULL:\n");
init(&tree);
printf("请输入先序序列中的第K个位置（注意不要超过树的节点数）：\n");
scanf("%d", &K);
node1 = findPreKey1(tree, K);
if (node1 != NULL)
printf("(递归版本)先序序列中的第%d个位置元素的值为：%c\n", K,node1->data);
else
printf("(递归版本)先序序列中不存在第%d个位置元素\n", K);
node2 = findPreKey2(tree, K);
if (node2 != NULL)
printf("(非递归版本)先序序列中的第%d个位置元素的值为：%c\n", K,node2->data);
else
printf("(非递归版本)先序序列中不存在第%d个位置元素\n", K);
return 0;

}

测试结果：
按先序建立二叉树，'_'(下画线)代表节点为NULL:
ABC__DE_G__F___
请输入先序序列中的第K个位置（注意不要超过树的节点数）：
6
(递归版本)先序序列中的第6个位置元素的值为：G
(非递归版本)先序序列中的第6个位置元素的值为：G

虽然代码显得有点冗余，不过还望楼主采纳！！追问

好长，不好意思，我觉得看不大懂，高手。。

本回答被网友采纳

Answer 2

，