FunctionGHW

立志成为真正程序员的码农,伪全栈,目前主要写C#

根据二叉树的中序和后序序列重新生成二叉树

FunctionGHW posted @ 2013年4月17日 22:37 in 算法学习 with tags Binary Tree 遍历二叉树 递归 , 9555 阅读

今日无闲扯。难得发一篇新的,所以没有旧文链接。

正文

题目是这样的:如果已知二叉树的中序遍历序列和后序遍历序列, 能否构造出这个树并输出其先序序列?假设序列中不存在重复的值。

首先要知道,一棵二叉树的中序遍历序列中,其根节点分布在序列的"中间" ——在序列中,其任何左子树上的节点的位置都在根节点的左侧,任何右子树上的节点都在右侧, 因此找出中序序列中的根节点的位置就能确定其左子树和右子树的子(中序)序列。 而后序遍历的一个明显特点就是: 根节点始终在后序序列的末尾,即最右端的那个。 同一棵树(子树也是一棵树),不管中序后序,序列长度都是一样的。根据这些条件, 我们就能够得到一棵二叉树的根节点,以及左右两棵子树的中序序列和后续序列, 然后递归地找出左右子树的根节点。

对于叶子结点,把它看成是单节点的树,它的左右子树都是空树。

Code

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> //C99.

typedef struct TreeNode TreeNode;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
};

//按后序遍历顺序 释放节点.
void delete_tree(TreeNode* root)
{
    if (root != NULL)
    {
        delete_tree(root->left);
        delete_tree(root->right);
        free(root);
    }
}

//输出先序遍历序列.
void pre_order_print(TreeNode* root)
{
    if (root != NULL)
    {
        printf("%d, ", root->val);
        pre_order_print(root->left);
        pre_order_print(root->right);
    }
}

//一个线性搜索函数,返回val在in_order_seq[len]中的索引.
int index_at_inseq(int in_order_seq[], int len, int val)
{
    int i;
    for (i = 0; i < len; ++i)
    {
        if(in_order_seq[i] == val) return i;
    }
    return -1;
}

//递归构造二叉树,最后一个参数用于指示构造是否成功.
TreeNode* ConstructBTree(int in_order_seq[], int post_order_seq[], int len, bool* is_success)
{
    if (len < 1 || (*is_success) == false)//空树或构造过程已经出错.
    {
        return NULL;
    }

    int root_index = index_at_inseq(in_order_seq, len, post_order_seq[len - 1]);
    if (root_index < 0)//根节点的值不匹配,停止构造.
    {
        (*is_success) = false;
        fprintf(stderr, "Wrong sequences.\n");
        return NULL;
    }

    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    if (root == NULL)//内存不足.
    {
        (*is_success) = false;
        fprintf(stderr, "Out of memory.\n");
        return NULL;
    }
    root->val = post_order_seq[len - 1];

    int left_subtree_len = root_index;
    int right_subtree_len = len - (left_subtree_len + 1);

    root->left = ConstructBTree(in_order_seq,
                                post_order_seq,
                                left_subtree_len,
                                is_success);

    root->right = ConstructBTree(in_order_seq + left_subtree_len + 1,
                                 post_order_seq + left_subtree_len,
                                 right_subtree_len,
                                 is_success);
    return root;
}

//使用时应该使用这个函数,如果构造失败,需要清理内存.
TreeNode* GetBTree(int in_seq[], int post_seq[], int len)
{
    bool is_success = true;
    TreeNode* p = ConstructBTree(in_seq, post_seq, len, &is_success);
    if (is_success)
    {
        return p;
    }
    else
    {//构造失败,清理所有已创建的节点.
        delete_tree(p);
        return NULL;
    }
}

int main()
{
    int in_order_seq[] = {2,1,3, 4};
    int post_order_seq[] = {1,2,3, 4};
    int len = sizeof(in_order_seq) / sizeof(in_order_seq[0]);

    TreeNode* theTree = GetBTree(in_order_seq, post_order_seq, len);

    pre_order_print(theTree);
    puts("");
    delete_tree(theTree);

    getchar();
    return 0;
}
                
                

如果觉得那个bool参数太碍眼,可以考虑改成迭代实现, 这样在一个同一个函数里即可完成出错后的删除操作,不过递归实现我觉得更加简洁易懂。

简单的分析下复杂度,单纯的递归的过程相当于遍历了所有的节点, 所以时间复杂度是O(n),但是每一次递归过程都有一次和序列长度相关的线性搜索过程, 时间复杂度也是O(n)。所以最终的时间复杂度变成了\(O(n^2)\)。 递归过程必须要遍历所有的节点,因此时间复杂度难以优化。那么,能不能在优化搜索函数呢? 呵呵,跑题了,问题转移到 搜索算法上去了。

我想到一种方法:首先改用迭代实现,然后在开始的时候建立一个二元组数组, 其中存放中序序列数组的所有值(value)及其对应的索引值(index)构成的二元组,之后使用归并排序按value排序二元组, 这样以后就能使用二分搜索查找结点的index。因为二分搜索的复杂度是\(O(\log n)\),因此生成过程的时间复杂度就控制在\(O(n\log n)\)级别。而前面的排序时间复杂度也是\(O(n\log n)\),这样整体的时间复杂度就变成了\(O(n\log n)\)级别。缺点就是会多一个O(n)级别的空间复杂度, 即额外内存开销会大很多。也可以改用快速排序,但是不推荐,尽管能降低空间复杂度的常数 但是如果是有序二叉树的话,排序的时间复杂度更接近\(O(n^2)\),时间复杂度降低不了多少。

不过,其他同学给似乎给出了更好的优化方法——使用哈希表(Hash Table)。具体实现就不去弄了(其实我也不会,呵呵), 有兴趣的可以试试。

 

 

Kingsley Chen 说:
2013年4月18日 16:24

说个C syntax的问题

<pre>
typedef struct TreeNode TreeNode;

typedef struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
};
</pre>

把第二个typedef去掉,或者直接 typedef struct _TreeNode {} TreeNode;

Avatar_small
FunctionGHW 说:
2013年4月19日 09:24

额。。擦,改代码留下的,没注意到,不过这个居然没出事。。

Avatar_small
FunctionGHW 说:
2013年4月19日 09:36

可能是要<pre class="brush: cpp;">int num = 0;</pre>

Avatar_small
FunctionGHW 说:
2013年4月19日 13:01

貌似is-Programmer不支持评论里差代码。。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter