假设二叉树采用二叉链存储结构存储,设计一个算法,求先序遍历序列中第k个结点的值
#include <iostream>
#include <stack>
typedef struct treenode{
char data;
struct treenode *left;
struct treenode *right;
}treenode,*ptreenode;
ptreenode buytreenode(char x)
{
ptreenode n=(ptreenode) malloc(sizeof (treenode));
n->data=x;
n->left= nullptr,n->right= nullptr;
return n;
}
ptreenode build_tree()
{
ptreenode root= buytreenode('A');
root->left= buytreenode('B');
root->right= buytreenode('C');
root->left->left= buytreenode('D');
root->left->right= buytreenode('E');
return root;
}
ptreenode printnode(ptreenode root,int &x)
{
if(root== nullptr) return root;
if (x--==1) return root;
ptreenode ch=printnode(root->left,x);
if(ch) return ch;
ch=printnode(root->right,x);
return ch;
}
void print_prior(ptreenode root)
{
if(root== nullptr) return ;
printf("%3c",root->data);
print_prior(root->left);
print_prior(root->right);
}
int main() {
ptreenode root=build_tree();
print_prior(root);
puts("");
int number=0;
for(int i=1;i<=5;i++)
{
number=i;
printf("the %2dth element is:%3c",i,printnode(root,number)->data);
puts("");
}
return 0;
}