二叉树遍历的应用

佚名 6年前 (2019-05-07) 随笔 993人围观抢沙发百度已收录

1.由两种遍历确定二叉树

必须要有中序遍历才能确定一颗二叉树

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

以先序和中序遍历序列确定二叉树为例：

node *create(char *pre, char *in, int num)
{
    if (num==0) return NULL;
    int i;
    while (i<num&&in[i]!=pre[0]) i++;//查找根节点在中序的位置 
    int lnum = i, rnum = num-i-1;
    node *root = (node*)malloc(sizeof(node));
    root->data = pre[0];
    root->lch = create(&pre[1], &in[0], lnum);
    root->rch = create(&pre[i+1], &in[i+1], rnum);
    return root;
}