求代码：编写递归算法，在二叉树中求位于先序序列中第k个位置的结点的值

Question

数据结构：（c语言）自行设计二叉树;要求二叉树用二叉链表存储结构。

Answer 1

好像就是线索二叉树，
下面是二叉树创建、遍历程序，没有线索二叉树。仅供参考。。。
//------------------------------------------------------------------------------
// Copyright (c) 2009 eryar All rights reserved.
//
// File : BinTree.h
// Author : eryar@163.com
// Date : 2009-9-13 19:07
// Version : 1.0v
//
// Description : Binary tree declaration
//
//==============================================================================

#ifndef _BINTREE_H_
#define _BINTREE_H_

#include <iostream>
using namespace std;

typedef char ElemType;

typedef struct Node{
ElemType data;
struct Node* lChild;
struct Node* rChild;
}Node;

typedef struct Node* BinTree;

//------------------------------------------------------------------------
bool InitBinTree(BinTree* T);
void CreateBinTree(BinTree* T);
void PreOrderTraverse(BinTree T);
void InOrderTraverse(BinTree T);
void PostOrderTraverse (BinTree T);
void LevelOrderTraverse(BinTree T);
bool isEmpty(BinTree T);
//========================================================================

#endif // _BINTREE_H_

//------------------------------------------------------------------------------
// Copyright (c) 2009 eryar All rights reserved.
//
// File : BinTree.cpp
// Author : eryar@163.com
// Date : 2009-9-13 19:11
// Version : 1.0v
//
// Description : Binary tree definition
//
//==============================================================================

#include "BinTree.h"

/*
Parameter : BinTree*
Return : true or false
Description : initialize the binary tree
*/
bool InitBinTree(BinTree* T) {
*T = NULL;
return true;
} // InitBinTree

/*
Parameter : BinTree*
Return : none
Description : create a binary tree in preorder
*/
void CreateBinTree(BinTree* T) {
ElemType elem;

cin>>elem;

if (elem == '#') {
*T = NULL;
}
else {
*T = new Node;
(*T)->data = elem;
CreateBinTree(&(*T)->lChild);
CreateBinTree(&(*T)->rChild);
}

} // CreateBinTree

/*
Parameter : BinTree*
Return : true or false
Description : PreOrder visit binary tree
*/
void PreOrderTraverse(BinTree T) {
if (T) {
cout<<"node is : "<<T->data<<endl;
PreOrderTraverse(T->lChild);
PreOrderTraverse(T->rChild);
}

} // PreOrderTraverse

/*
Parameter : BinTree
Return : true or false
Description : inorder traverse binary tree
*/
void InOrderTraverse(BinTree T) {

if (T) {
InOrderTraverse(T->lChild);
cout<<"node is : "<<T->data<<endl;
InOrderTraverse(T->rChild);
}

} // InOrderTraverse

/*
Parameter : BinTree
Return : true or false
Description : PostOrder traverse binary tree
*/
void PostOrderTraverse(BinTree T) {

if (T) {
PostOrderTraverse(T->lChild);
PostOrderTraverse(T->rChild);
cout<<"node is : "<<T->data<<endl;
}

} // PostOrderTraverse

/*
Parameter : BinTree
Return : none
Description : Level order traverse the binary tree
*/
void LevelOrderTraverse(BinTree T) {
} // LevelOrderTraverse

/*
Parameter : BinTree
Return : true or false
Description : if tree is empty return true
*/
bool isEmpty(BinTree T) {
if (T) {
return false;
}
else {
return true;
}

} // isEmpty
//------------------------------------------------------------------------------
// Copyright (c) 2009 eryar All rights reserved.
//
// File : main.cpp
// Author : eryar@163.com
// Date : 2009-9-13 19:04
// Version : 1.0v
//
// Description : Binary tree use C to implemention
//
//==============================================================================

#include "BinTree.h"

int main(int argc, char *argv[])
{
BinTree tree;

InitBinTree(&tree);

cout<<"先序遍历法创建二叉树:";
CreateBinTree(&tree);

BinTree visit = tree;
cout<<"先序遍历:"<<endl;
PreOrderTraverse(visit);

cout<<"中序遍历:"<<endl;
visit = tree;
InOrderTraverse(visit);

cout<<"后序遍历:"<<endl;
visit = tree;
PostOrderTraverse(visit);

return 0;
}