二叉树的序列转换、二叉搜索树序列转换

发布于 / 数据结构与算法 / Comments Off on 二叉树的序列转换、二叉搜索树序列转换

前面说了那么多关于二叉树的,这篇来写个总结吧!主要是关于二叉树的序列转换。

分别是:已知先序、中序,转后序;    已知先序、中序,转层序;

                已知后序、中序,转先序;    已知后序、中序,转层序;

                已知二叉搜索树的任何序列,重建二叉搜索树。

其实上面的问题都可以归为:给定二叉树序列,在重新遍历二叉树。

关于二叉树的遍历可以在这篇文章:C语言-二叉树的遍历-斐斐のBlog

下面主要介绍如何重建二叉树。

在重建二叉树之前先定义一个查找函数,在序列中查找某数,然后返回该数的下标。

int find_index(int x, const int *arr){
    for(int i = 0; i < MAX_SIZE; i++)    //MAX_SIZE根据数组大小修改,防越界
        if(arr[i] == x) return i;
    return -1;
}

0x00、先序、中序 --> 还原二叉树

二叉树的先序序列特点为:{根部左子树右子树}

                中序序列特点为:{左子树根部右子树}

根据这一特点,我们的思路是:以先序序列第一个值为根,将根写入二叉树。接着在中序序列中找到根,根据中序序列起始位置与根节点的距离,递归还原左右子树。

递归的终点就是二叉树起始位置大于终止位置。

具体操作实现代码如下:

/*  *
    * 二叉树的还原方法
    * 参数preL:先序序列的起始位置
    * 参数preR:先序序列的结束位置
    * 参数inL:中序序列的起始位置
    * 参数inR:中序序列的结束位置
    * 即:先序序列区间为[preL, preR],中序序列区间为[inL, inR]
    */
node* void create(int preL, int preR, int inL, int inR){
    if(preL > preR) return NULL;    //递归终点(返回NULL代表树叶)
    node* root = new node;    //新建当前根节点
    root->data = pre[preL];    //先序序列第一个值就是根节点
    int index_inorder = find_index(root->data, in);//找到根节点在中序序列中的位置
    int sum_of_left_tree = index_inorder - inL;//计算左子树的大小
    /*下面开始确定左子树位置,并构建左子树*/
    int L_new_preL = preL + 1;    //新的左子树先序序列起始位置为原来起始位置+1。因为第一个位置是当前根节点
    int L_new_preR = preL + sum_of_left_tree; //新左子树先序序列终止位置为原来左子树起始位置+左子树大小
    int L_new_inL  = inL;    //新左子树中序序列起始位置为原左子树中序序列起始位置
    int L_new_inR  = index_inorder - 1; //新左子树中序序列终止位置为原左子树根节点位置-1
    root->lchild = create(L_new_preL, L_new_preR, L_new_inL, L_new_inR);//递归构建左子树
    /*下面开始确定右子树位置,并构建右子树*/
    int R_new_preL = L_new_preR + 1;    //左子树在先序序列结束位置往后都是右子树
    int R_new_preR = preR;
    int R_new_inL  = index_inorder + 1; //原中序序列根节点往后都是新右子树
    int R_new_inL  = inR;
    root->rchild = create(R_new_preL, R_new_preR, R_new_inL, R_new_inL);//递归构建右子树
    return root;    //返回新建二叉树的根节点
}

0x01、后序、中序 -->还原二叉树

二叉树的后序序列特点为:{左子树右子树根部}

                中序序列特点为:{左子树根部右子树}

根据这一特点,我们的思路是:以后序序列第一个值为根,将根写入二叉树。接着在中序序列中找到根,根据中序序列起始位置与根节点的距离,递归还原左右子树。

递归的终点就是二叉树起始位置大于终止位置。

具体操作实现代码如下:

/*  *
    * 二叉树的还原方法
    * 参数post_left:后序序列的起始位置
    * 参数post_right:后序序列的结束位置
    * 参数in_left:中序序列的起始位置
    * 参数in_right:中序序列的结束位置
    * 即:后序序列区间为[post_left, post_right],中序序列区间为[in_left, in_right]
    */
node* create(int post_left, int post_right, int in_left, int in_right){
    if(post_left > post_right) return NULL;
    node* root = new node;
    root->data = post_order[post_right];
    int root_position_inorder = find_index(in_order, root->data);
    int Lchild_sum = root_position_inorder - in_left;
    int Lchild_post_left = post_left,
        Lchild_post_right = post_left + Lchild_sum - 1,
        Lchild_in_left = in_left,
        Lchild_in_right = root_position_inorder - 1;
    int Rchild_post_left = post_left + Lchild_sum,
        Rchild_post_right = post_right - 1,
        Rchild_in_left = root_position_inorder + 1,
        Rchild_in_right = in_right;
    root->lchild = create(Lchild_post_left, Lchild_post_right, Lchild_in_left, Lchild_in_right);
    root->rchild = create(Rchild_post_left, Rchild_post_right, Rchild_in_left, Rchild_in_right);
    return root;
}

所以,"给出中序和其他序列,求另一序列"的还原方法通常是:判断是否达到递归终点、判断根节点、判断左右子树区间、递归构建左右字子树

0x02、给出二叉搜索树的序列,重建二叉搜索树

这个问题其实很好解决,因为二叉搜索树有一个重要的特性:二叉搜索树的中序序列是有序的。

无论给出什么序列,我们只需要进行排序,然后中序遍历并写入二叉树即可。

我们通常来使用静态二叉树来完成。

例如:

//假设前面已经使用sort函数排序好了序列input,现在将input插入到静态二叉树中
typedef struct{
    int data, lchild, rchild;
} node;

node tree[8];
int iterator = 0;   //迭代器
insert(0);    //从输入的第一个节点开始

void insert(int root){
    if(root == -1) return;
    insert(input[root].lchild);
    tree[iterator++] = input[root].data;
    insert(input[root].rchild);
}

转载原创文章请注明,转载自: 斐斐のBlog » 二叉树的序列转换、二叉搜索树序列转换
评论已关闭