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

Question

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

Answer 1

#include<iostream>
#include<stdlib.h>
#include<stdio.h>
static int n=0;
typedef struct tree
{
struct tree *left;
int date;
struct tree *right;
}treenode,*b_tree;
///////插入节点/////////////////////

b_tree insert(b_tree root,int node)
{
b_tree newnode;
b_tree currentnode;
b_tree parentnode;

newnode=(b_tree)malloc(sizeof(treenode));

newnode->date=node;
newnode->right=NULL;
newnode->left=NULL;

if(root==NULL)
return newnode;
else
{
currentnode=root;
while(currentnode!=NULL)
{
parentnode=currentnode;
if(currentnode->date>node)
currentnode=currentnode->left;
else
currentnode=currentnode->right;
}
if(parentnode->date>node)
parentnode->left=newnode;
else
parentnode->right=newnode;
}
return root;
}

//////建立树///////////////////
b_tree creat(int *date,int len)
{
b_tree root=NULL;
int i;
for(i=0;i<len;i++)
root=insert(root,date[i]);
return root;
}

//////前序打印第K个数////////////////
void print3(b_tree root,int k)
{
if(root!=NULL)
{ n++;
if(n==k)
printf("%d\n",root->date);
print3(root->left,k);
print3(root->right,k);

}
}

//////前序打印////////////////
void print(b_tree root)
{
if(root!=NULL)
{

printf("%d->",root->date);
print(root->left);
print(root->right);

}
}
///////测试函数//////////////////
void main()
{
b_tree root=NULL;
int i,index;
int value;
int nodelist[20];

cout<<"输入树的节点，输入0结束\n";
index=0;
cin>>value;
while(value!=0)
{
nodelist[index]=value;
index=index+1;
cin>>value;
}
root=creat(nodelist,index);
printf("\n前序打印\n");
print(root);
printf("\n打印问位置数\n");
cin>>i;
printf("\n前序打印第K个数\n");

print3(root,i); }

Answer 2

#include<iostream>
#include<stdlib.h>
#include<stdio.h>
static
int
n=0;
typedef
struct
tree
{
struct
tree
*left;
int
date;
struct
tree
*right;
}treenode,*b_tree;
///////插入节点/////////////////////
b_tree
insert(b_tree
root,int
node)
{
b_tree
newnode;
b_tree
currentnode;
b_tree
parentnode;
newnode=(b_tree)malloc(sizeof(treenode));
newnode->date=node;
newnode->right=NULL;
newnode->left=NULL;
if(root==NULL)
return
newnode;
else
{
currentnode=root;
while(currentnode!=NULL)
{
parentnode=currentnode;
if(currentnode->date>node)
currentnode=currentnode->left;
else
currentnode=currentnode->right;
}
if(parentnode->date>node)
parentnode->left=newnode;
else
parentnode->right=newnode;
}
return
root;
}
//////建立树///////////////////
b_tree
creat(int
*date,int
len)
{
b_tree
root=NULL;
int
i;
for(i=0;i<len;i++)
root=insert(root,date[i]);
return
root;
}
//////前序打印第K个数////////////////
void
print3(b_tree
root,int
k)
{
if(root!=NULL)
{
n++;
if(n==k)
printf("%d
",root->date);
print3(root->left,k);
print3(root->right,k);
}
}
//////前序打印////////////////
void
print(b_tree
root)
{
if(root!=NULL)
{
printf("%d->",root->date);
print(root->left);
print(root->right);
}
}
///////测试函数//////////////////
void
main()
{
b_tree
root=NULL;
int
i,index;
int
value;
int
nodelist[20];
cout<<"输入树的节点，输入0结束
";
index=0;
cin>>value;
while(value!=0)
{
nodelist[index]=value;
index=index+1;
cin>>value;
}
root=creat(nodelist,index);
printf("
前序打印
");
print(root);
printf("
打印问位置数
");
cin>>i;
printf("
前序打印第K个数
");
print3(root,i);
}