【IT笔试面试题整理】给定二叉树先序中序,建立二叉树的递归算法

时间:2022-12-24 22:03:04

【试题描述】:  给定二叉树先序中序,建立二叉树的递归算法

其先序序列的第一个元素为根节点,接下来即为其左子树先序遍历序列,紧跟着是右子树先序遍历序列,固根节点已可从先序序列中分离。在中序序列中找到 确定的根节点,根据中序遍历特性,在巾序序列中,根节点前面的序列即为左子树的中序遍历序列,根节点后面的即为右子树的中序遍历序列。由左右子树的中序序列长度,在该二又树的先序序列中即可找到左右子树的先序序列的分界点,从而得到二叉树的左右子树的先序序列。

递归实现:
递归函数输入:二叉树的先序序列和中序序列;返回-、建好的二叉树的根节点。
算法思想:
1)若二叉树空,返回空;
2)若不空,取先序序列第一个元素,建立根节点;
3)在中序序列中查找根节点,以此确定左右子树的先序序列和中序序列;
4)递归调用自己,建左子树;
5)递归调用自己,建右子树。

【参考代码】

 1 public static TreeNode createBT(String pres, String ins)
2 {
3 int inpos = 0;
4 TreeNode root;
5 String leftPres, leftIns, rightPres, rightIns;
6
7 if (pres.length() == 0 || ins.length() == 0)
8 return null;
9 else
10 {
11 root = new TreeNode(pres.charAt(0));
12 while (ins.charAt(inpos) != root.value)
13 inpos++;
14 leftPres = pres.substring(1, inpos + 1);
15 leftIns = ins.substring(0, inpos);
16
17 root.left = createBT(leftPres, leftIns);
18 rightPres = pres.substring(inpos + 1, pres.length());
19 rightIns = ins.substring(inpos + 1, ins.length());
20 root.right = createBT(rightPres, rightIns);
21 }
22 return root;
23 }
24
25 class TreeNode
26 {
27 public char value;
28 public TreeNode left;
29 public TreeNode right;
30
31 public TreeNode(char value)
32 {
33 this.value = value;
34 }
35 }

【IT笔试面试题整理】给定二叉树先序中序,建立二叉树的递归算法的更多相关文章

  1. 【IT笔试面试题整理】删除无序链表中重复的节点

    [试题描述]定义一个函数,输入一个链表,删除无序链表中重复的节点 [参考代码] 方法一: Without a buffer, we can iterate with two pointers: &qu ...

  2. Java笔试面试题整理第六波(修正版)

    转载至:http://blog.csdn.net/shakespeare001/article/details/51330745 作者:山代王(开心阳) 本系列整理Java相关的笔试面试知识点,其他几 ...

  3. Java笔试面试题整理第三波

    转载至:http://blog.csdn.net/shakespeare001/article/details/51247785 作者:山代王(开心阳) 本系列整理Java相关的笔试面试知识点,其他几 ...

  4. Java笔试面试题整理第八波

    转载至:http://blog.csdn.net/shakespeare001/article/details/51388516 作者:山代王(开心阳) 本系列整理Java相关的笔试面试知识点,其他几 ...

  5. Java笔试面试题整理第五波

    转载至:http://blog.csdn.net/shakespeare001/article/details/51321498 作者:山代王(开心阳) 本系列整理Java相关的笔试面试知识点,其他几 ...

  6. Java笔试面试题整理第四波

    转载至:http://blog.csdn.net/shakespeare001/article/details/51274685 作者:山代王(开心阳) 本系列整理Java相关的笔试面试知识点,其他几 ...

  7. Java笔试面试题整理第二波

    转载至:http://blog.csdn.net/shakespeare001/article/details/51200163 作者:山代王(开心阳) 本系列整理Java相关的笔试面试知识点,其他几 ...

  8. Java笔试面试题整理第一波

    转载至:http://blog.csdn.net/shakespeare001/article/details/51151650 作者:山代王(开心阳) 本系列整理Java相关的笔试面试知识点,其他几 ...

  9. SDUT OJ 数据结构实验之二叉树四:(先序中序)还原二叉树

    数据结构实验之二叉树四:(先序中序)还原二叉树 Time Limit: 1000 ms Memory Limit: 65536 KiB Submit Statistic Discuss Problem ...

随机推荐

  1. div 纯数字很长时无法折行解决

    <div style="width:100%;word-wrap:break-word;word-spacing:normal;"> </div> 加上红色 ...

  2. 【Codefoces487E&sol;UOJ&num;30】Tourists Tarjan 点双连通分量 &plus; 树链剖分

    E. Tourists time limit per test: 2 seconds memory limit per test: 256 megabytes input: standard inpu ...

  3. http 请求类

    1.httpclient请求类 代理demo:http://hc.apache.org/httpcomponents-client-4.3.x/httpclient/examples/org/apac ...

  4. 关于回波损耗 和 驻波比的摘要 Return Loss and VSWR

    关于回波损耗 和 驻波比的摘要 以下摘自:http://www.soontai.com/cal_rtvswr.html RL = 20log((VSWR+1) / (VSWR-1)) VSWR = ( ...

  5. &lbrack;Ext JS 4&rsqb; 布局之实战一 - 中间区块不会自动伸展 (tab)

    前言 [Ext JS 4] 布局之实战一 - 中间区块不会自动伸展 (tab) 在上一篇中,中间的tab 区块无法自动伸展的原因一句话说就是: 使用contentEL的方式,相关HTML元素不会参与组 ...

  6. UVA 439 Knight Moves&lpar;BFS&rpar;

    Knight Moves option=com_onlinejudge&Itemid=8&category=11&page=show_problem&problem=3 ...

  7. C&num;复习资料

    C#期末考试复习题 一.单项选择题(每小题2分,共20分) 1.在类作用域中能够通过直接使用该类的(   )成员名进行访问. A. 私有      B. 公用      C. 保护      D. 任 ...

  8. jq点击事件不生效,效果只闪现一次又立马消失的原因?

    出现的问题:jq点击事件不生效,点击的时候效果实现但又立马消失,页面重新刷新了一次 可能出现的原因: a标签href属性的原因,虽然点击事件生效,但页面又刷新了一次,所以没有效果,只闪了一次 解决方案 ...

  9. iOS开发简记(4):录音AVAudioRecorder

    录音,声音的采集,一般有两种实现办法,一是使用AVAudioRecorder,一是使用AudioUnit.如果只是简单的录音,使用AVAudioRecorder就可以了,如果想更灵活地处理刚录到的声音 ...

  10. xv6&sol;sh&period;c

    // Shell. #include "types.h" #include "user.h" #include "fcntl.h" // P ...