FunctionGHW

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

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

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

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

正文

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

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

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

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不支持评论里差代码。。

satta 说:
2022年1月31日 16:44

I think this is a better than average article. You make this data intriguing and locks in. You give perusers a considerable measure to consider and I welcome that sort of composing

matka 说:
2022年2月01日 00:25

I appreciate everything you have added to my knowledge base.Admiring the time and effort you put into your blog and detailed information you offer.Thanks.

sattamatka 说:
2022年2月13日 18:24

Yes i am totally agreed with this article and i just want say that this article is very nice and very informative article.I will make sure to be reading your blog more. You made a good point but I can't help but wonder, what about the other side? !!!!!!Thanks

matka guessing 说:
2022年2月14日 18:43

Every year, thousands of customers around the world choose MaroCar for a cheap car hire in Morocco. The platform operates in the main cities of the kingdom (Casablanca, Marrakech, Tangiers, Rabat …) and delivers its cars to the address of your choice or directly to the main airports in the country.

Car Show Display Ide 说:
2022年2月22日 15:26

thank you for substitute invincible article. where else may want to all of us collect that saintly of make public in any such obtain quirk of writing? i've a presentation adjacent week, and i am concerning the see for such facts.

Digital Global Times 说:
2022年2月22日 22:01

Every year, thousands of customers around the world choose MaroCar for a cheap car hire in Morocco. The platform operates in the main cities of the kingdom (Casablanca, Marrakech, Tangiers, Rabat ...) and delivers its cars to the address of your choice or directly to the main airports in the country.

kroger hr express 说:
2022年2月24日 15:14

The software says exclusively relevant. Each of reduced attributes happen to be formulated with various capture certification. I like the application many.

car show signs 说:
2022年2月28日 19:53

thank you for substitute invincible article. where else may want to all of us collect that saintly of make public in any such obtain quirk of writing? i've a presentation adjacent week, and i am concerning the see for such facts.

Free Converter 说:
2022年3月05日 21:15

As always your articles do inspire me. Every single detail you have posted was great.

satta matka 说:
2022年3月07日 14:40

We are really grateful for your blog post. You will find a lot of approaches after visiting your post. I was exactly searching for. Thanks for such post and please keep it up. Great work.

sattamatka 说:
2022年3月12日 23:55

I also wrote an article on a similar subject will find it at write what you think.

satta 说:
2022年3月14日 15:33

Thank you a bunch for sharing this with all of us you actually realize what you are talking about! Bookmarked. Please also seek advice from my site =). We could have a hyperlink change contract between us!

Hyll on Holland 说:
2022年3月17日 14:30

Every year, thousands of customers around the world choose MaroCar for a cheap car hire in Morocco. The platform operates in the main cities of the kingdom (Casablanca, Marrakech, Tangiers, Rabat …) and delivers its cars to the address of your choice or directly to the main airports in the country.

Riviere 说:
2022年3月18日 14:52

I definitely enjoying every little bit of it. It is a great website and nice share. I want to thank you. Good job! You guys do a great blog, and have some great contents. Keep up the good work

Biotechnolabs 说:
2022年3月22日 21:49

Thanks for your valuable post, Really nice and very informative.

Kingpure 说:
2022年4月05日 15:06

Thank you for taking the time to publish this information very useful!

Lentor Modern Brochu 说:
2022年4月05日 17:40

I think this is a better than average article. You make this data intriguing and locks in. You give perusers a considerable measure to consider and I welcome that sort of composing

Vending Machine Serv 说:
2022年4月07日 22:35

Hi there! Nice stuff do keep me posted when you post again something like this

prime advantage 说:
2022年4月10日 22:28

thank you for substitute invincible article. where else may want to all of us collect that saintly of make public in any such obtain quirk of writing? i've a presentation adjacent week, and i am concerning the see for such facts.

Digital Global Times 说:
2022年4月15日 04:44

Thank you for taking the time to publish this information very useful!

Midtown Bay Brochure 说:
2022年4月19日 01:18

I wanted to thank you for this in your liking ensnare!! I particularly enjoying all tiny little bit of it I have you ever bookmarked to check out delivered stuff you pronounce.

yoyo 说:
2022年5月02日 05:25

You have a good point here!I totally agree with what you have said!!Thanks for sharing your views...hope more people will read this article!!! transmit error code 1231

yoyo 说:
2022年5月08日 00:30

I have a hard time describing my thoughts on content, but I really felt I should here. Your article is really great. I like the way you wrote this information. Updated Ideas

yoyo 说:
2022年5月12日 02:21

I learn some new stuff from it too, thanks for sharing your information. 출장안마

yoyo 说:
2022年5月18日 23:27

Thanks for taking the time to discuss this, I feel strongly about it and love learning more on this topic. If possible, as you gain expertise, would you mind updating your blog with more information? It is extremely helpful for me. https://helvetia-umzug.ch/

yoyo 说:
2022年5月23日 01:55

I haven’t any word to appreciate this post.....Really i am impressed from this post....the person who create this post it was a great human..thanks for shared this with us. 출장안마

arsi 说:
2022年5月28日 19:32

Thank you for writing this tremendous top quality article. The information in this material confirms my point of view and you really laid it out well. I could never have written an article this good. betting sites in south africa

arsi 说:
2022年5月29日 04:47

Previously you must have highly effective web business strategies get you started of getting into topics suitable for their web-based organization. educational betting sites in south africa

arsi 说:
2022年5月29日 18:11

This design is spectacular! You obviously know how to keep a reader amused. Between your wit and your videos, I was almost moved to start my own blog (well, almost…HaHa!) Fantastic job. I really enjoyed what you had to say, and more than that, how you presented it. Too cool! betting sites in switzerland

yoyo 说:
2022年6月06日 02:53

Awesome blog. I enjoyed reading your articles. This is truly a great read for me. I have bookmarked it and I am looking forward to reading new articles. Keep up the good work! 레깅스룸

yoyo 说:
2022年6月18日 02:02

New Port Residences EC @ Tengah Garden Walk by CDL & MCL Land. Showflat Hotline 61009266. Get Discounts, Direct Developer Price, Discount, Brochure, Floor Plan, & More. New Port Residences Pricing

yoyo 说:
2022年6月21日 19:54

I recently found many useful information in your website especially this blog page. Among the lots of comments on your articles. Thanks for sharing. Updated Ideas

yoyo 说:
2022年6月23日 21:11

Yes i am totally agreed with this article and i just want say that this article is very nice and very informative article.I will make sure to be reading your blog more. You made a good point but I can't help but wonder, what about the other side? !!!!!!Thanks Air Queen breeze

updatedverse 说:
2022年7月19日 16:42

<a href='https://updatedverse.com/10-best-android-cleaner-apps-to-clear-ram-and-cache-in-2021/' title='10 Best Android Cleaner Apps 2021' target='_blank'>10 Best Android Cleaner Apps 2021</a>
<a href='https://updatedverse.com/10-best-app-locks-for-android-to-secure-your-device-in-2022/' title='Best App Locks For Android in 2022' target='_blank'>Best App Locks For Android in 2022</a>
<a href='https://updatedverse.com/10-best-pdf-reader-apps-for-iphone-ipad-view-and-edit-pdfs-in-2022/' title='Best PDF Reader For iPhone' target='_blank'>Best PDF Reader For iPhone</a>
<a href='https://updatedverse.com/10-fail-proof-email-marketing-tips-for-small-businesses/' title='email marketing tips' target='_blank'>email marketing tips</a>
<a href='https://updatedverse.com/10-most-secure-and-secure-messaging-apps-for-android-and-ios-2022/' title='10 Most Secure and Secure messaging apps for (Android and iOS)' target='_blank'>10 Most Secure and Secure messaging apps for (Android and iOS)</a>
<a href='https://updatedverse.com/10-top-iphone-browsers-top-safari-alternatives-for-2022/' title='Ten Best iPhone Web Browser Apps For 2022' target='_blank'>Ten Best iPhone Web Browser Apps For 2022</a>
<a href='https://updatedverse.com/12-best-android-camera-apps-in-2022/' title='Best Android Camera Apps' target='_blank'>Best Android Camera Apps</a>
<a href='https://updatedverse.com/11-best-linux-distros-for-programming-and-development-2022-edition/' title='11 Best Linux Distros For Programming In 2022' target='_blank'>11 Best Linux Distros For Programming In 2022</a>

uaecarpet 说:
2022年7月19日 19:02

<a href='https://uaecarpet.com/dubai-carpet-cleaning-services/' title=' carpet shop in deira dubai' target='_blank'> carpet shop in deira dubai</a>
<a href=' https://uaecarpet.com/carpet-shops-and-stores-in-dubai-and-uae/' title=' carpet shops and stores in dubai and uae' target='_blank'> carpet shops and stores in dubai and uae</a>
<a href='https://uaecarpet.com/modern-building-curtain-selection-in-dubai/' title='Modern building curtain selection in dubai' target='_blank'>Modern building curtain selection in dubai</a>
<a href='https://uaecarpet.com/roman-curtain-and-know-about-this-curtain/' title='Roman curtain and know about this curtain' target='_blank'>Roman curtain and know about this curtain</a>

yoyo 说:
2022年7月21日 01:38 Nice post. I was checking constantly this blog and I’m impressed! Extremely useful info specially the last part I care for such information a lot. I was seeking this certain info for a long time. Thank you and good luck. Updated Ideas
yoyo 说:
2022年8月07日 18:48

Thanks for posting this info. I just want to let you know that I just check out your site and I find it very interesting and informative. I can't wait to read lots of your posts. Info Redar

yoyo 说:
2022年8月10日 03:38

Your work is truly appreciated round the clock and the globe. It is incredibly a comprehensive and helpful blog. Digital Business Time

yoyo 说:
2022年8月11日 14:11

Pretty good post. I just stumbled upon your blog and wanted to say that I have really enjoyed reading your blog posts. Any way I'll be subscribing to your feed and I hope you post again soon. Big thanks for the useful info. Wiki business now

ayan 说:
2022年8月14日 20:53

It is truly a well-researched content and excellent wording. I got so engaged in this material that I couldn’t wait reading. I am impressed with your work and skill. Thanks. Digital Global Times

ayan 说:
2022年8月15日 22:00

En matière de formation à la gestion d'entreprise, les options ne manquent pas. Cependant, tous les programmes de formation ne sont pas créés égaux. Startupo est largement reconnu comme le meilleur centre de formation en ligne en France, et pour de bonnes raisons. Notre programme complet couvre tout, de la comptabilité et de la finance au marketing et aux ventes, donnant aux étudiants les compétences et les connaissances dont ils ont besoin pour réussir dans le monde des affaires compétitif d'aujourd'hui. De plus, nos professeurs expérimentés ont une grande expérience du monde réel à partager, garantissant que les étudiants reçoivent les informations les plus récentes et les plus pertinentes possibles. Avec Startupo, vous pouvez être sûr que vous recevez une formation en gestion d'entreprise de la plus haute qualité qui soit. formation gestion d'entreprise

rajmandir 说:
2022年8月17日 18:06

Very Nice Website, I really Appreciate your contents, this is very meaning for us.
<a href="https://rajmandirhypermarket.com">Rajmandir Hyper Market</a>

yoyo 说:
2022年8月25日 12:56

Your work is truly appreciated round the clock and the globe. It is incredibly a comprehensive and helpful blog. 먹튀폴리스

yoyo 说:
2022年8月27日 23:10

You have beaten yourself this time, and I appreciate you and hopping for some more informative posts in future. Thank you for sharing great information to us. Digital Global Times

yoyo 说:
2022年9月01日 22:29

I have read a few of the articles on your website now, and I really like your style of blogging. I added it to my favorites blog site list and will be checking back soon. Please check out my site as well and let me know what you think. wiki business now

yoyo 说:
2022年9月07日 23:50

Your work is truly appreciated round the clock and the globe. It is incredibly a comprehensive and helpful blog. https://www.simplybuzzes.com/angel-number-903/

yoyo 说:
2022年9月08日 23:22

New web site is looking good. Thanks for the great effort. Digital Global Times

yoyo 说:
2022年9月11日 03:00

You have noted very interesting points ! ps nice internet site . Updated Ideas

yoyo 说:
2022年9月12日 15:58

Great post, and great website. Thanks for the information! buy crypto

yoyo 说:
2022年9月12日 16:00

Great post, and great website. Thanks for the information! buy crypto

yoyo 说:
2022年9月22日 20:13

Great article mate, keep the great work, just shared this with ma friendz NagaPoker88 Asia

yoyo 说:
2022年9月24日 19:12

Great article mate, keep the great work, just shared this with ma friendz Naga303 Asia

ali 说:
2022年9月29日 00:41

This is a great inspiring article.I am pretty much pleased with your good work.You put really very helpful information... online shop

yoyo 说:
2022年9月29日 00:50

Great post, and great website. Thanks for the information! icon group

yoyo 说:
2022年9月29日 22:41

Great post, and great website. Thanks for the information! 토토사이트

yoyo 说:
2022年9月30日 19:39

my family would always like to go on ski holidays because it is very enjoyable; <a href="https://www.translinkexp.com/International-Courier-Service/Courier-To-Usa-From-Mumbai">Courier to USA from Mumbai</a>


登录 *


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