求先序遍历序列中第(1<=k<=二叉树中结点个数)个结点的值-创新互联
创新互联建站是网站建设技术企业,为成都企业提供专业的做网站、成都做网站,网站设计,网站制作,网站改版等技术服务。拥有十载丰富建站经验和众多成功案例,为您定制适合企业的网站。十载品质,值得信赖!
标题名称:求先序遍历序列中第(1<=k<=二叉树中结点个数)个结点的值-创新互联
当前路径:http://pwwzsj.com/article/djjoig.html
本题本质上就是一个遍历算法的实现,只不过用一个全局变量的来记录访问的序号,求其他遍历序列的第k个结点也采用相似的方法。二叉树的遍历算法可以引申出大量的算法题,因此考生务必熟练掌握二叉树的遍历算法。
C语言代码:
//本题本质上就是一个遍历算法的实现,只不过用一个全局变量的
//来记录访问的序号,求其他遍历序列的第k个结点也采用相似的
//方法。二叉树的遍历算法可以引申出大量的算法题,因此考生务必
//熟练掌握二叉树的遍历算法。
#includeusing namespace std;
typedef char ElemType;
typedef struct BiNode {
ElemType data;
BiNode* lchild;
BiNode* rchild;
}BiNode, * BiTree;
//构建二叉树
BiNode* Create(BiNode* bt) {
static int i = 0;
char ch;
//string str = "AB#D##C##";
//string str = "124##56##7##3##";
string str = "ABD#G##E##CF###";
//string str = "ABD#GH##I##E##CF###";
//string str = "#";
ch = str[i++];
if (ch == '#')bt = NULL;//建立一棵空树
else {
bt = (BiTree)malloc(sizeof(BiNode)); bt->data = ch;//生成一个结点,数据域为ch
bt->lchild = Create(bt->lchild);//递归建立左子树
bt->rchild = Create(bt->rchild);//递归建立右子树
}
return bt;
}
int i = 1;//遍历序号的全局变量
ElemType PreNode(BiTree b,int k) {
char ch;
//本算法查找二叉树先序遍历中第k个结点的值
if (b == NULL) {//空结点,则返回特殊字符
return '#';
}
if (i == k) {
return b->data;
}
i++;//下一个结点
ch = PreNode(b->lchild, k);//左子树中递归寻找
if (ch != '#')//在左子树中,则返回该值
return ch;
ch = PreNode(b->rchild, k);//在右子树中递归寻找
return ch;
}
void PreOrder(BiTree T) {
if (T) {
printf("%c ", T->data);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
int main() {
BiTree T = (BiTree)malloc(sizeof(BiNode));
T = Create(T);
int num = 5;
ElemType ch;
ch = PreNode(T, num);
if (ch != '#') {
//递归先序遍历
printf("递归先序遍历序列:");
PreOrder(T);
printf("\n先序遍历序列中第%d个结点值为:%c ", num, ch);
}
else {
printf("该二叉树是一棵空树");
}
}
实验结果图:
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
标题名称:求先序遍历序列中第(1<=k<=二叉树中结点个数)个结点的值-创新互联
当前路径:http://pwwzsj.com/article/djjoig.html