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

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

eryarfly · 2018-4-30 01:48:26

好像就是线索二叉树，
下面是二叉树创建、遍历程序，没有线索二叉树。仅供参考。。。
//------------------------------------------------------------------------------
// 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
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

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

1 个回复