文档章节

IT公司100题-1-二叉树转换为双链表

关西大汉弹琵琶
 关西大汉弹琵琶
发布于 2015/10/19 18:29
字数 357
阅读 97
收藏 8

问题描述:

输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点,只调整指针的指向。

    10
   /   \
  6      14
/  \    /   \
4   8 12    16

转换成双向链表
4=6=8=10=12=14=16。

分析:

首先我们定义的二元查找树 节点的数据结构如下:

private static class BSTreeNode{
   BSTreeNode(int x, BSTreeNode lt, BSTreeNode rt)
   {value = x; left = lt; right = rt;}

   int value;
   BSTreeNode left;
   BSTreeNode right;
}

代码实现:

package oschina.IT100;

/**
 * @project: oschina
 * @filename: IT1.java
 * @version: 0.10
 * @author: JM Han
 * @date: 14:55 2015/10/19
 * @comment: 将该二元查找树转换成一个排序的双向链表
 * @result:
 */
class BSTree1 {
   private static class BSTreeNode{
      BSTreeNode(int x, BSTreeNode lt, BSTreeNode rt)
      {value = x; left = lt; right = rt;}

      int value;
      BSTreeNode left;
      BSTreeNode right;
   }

   private BSTreeNode root;
   private BSTreeNode head;
   private BSTreeNode last;

   public BSTree1(){root = null; head = null; last = null;}

   public void insert(int value){
      root = insert(root, value);
   }

   private BSTreeNode insert(BSTreeNode t, int value) {
      if (null == t)
         return new BSTreeNode(value, null, null);

      if (t.value > value)
         t.left = insert(t.left, value);
      else if (t.value < value)
         t.right = insert(t.right, value);
      else
         System.out.println("already exist");
      return t;
   }

   public void treeToList(){
      treeToList(root);
   }

   private void treeToList(BSTreeNode root){
      if(null == root)
         return;
      treeToList(root.left);
      //previous pointer
      root.left = last;
      if(null == last)
         head = root;
      else
         //next pointer
         last.right = root;
      //last is the current root node
      last = root;
      treeToList(root.right);
   }

   public void printList(){
      if(null == head)
         return;
      while(head != null) {
         System.out.println(head.value);
         head = head.right;
      }
   }
}

public class IT1 {
   public static void main(String[] args) {
      BSTree1 bsTree = new BSTree1();
      bsTree.insert(10);
      bsTree.insert(6);
      bsTree.insert(14);
      bsTree.insert(4);
      bsTree.insert(8);
      bsTree.insert(12);
      bsTree.insert(16);
      bsTree.treeToList();
      bsTree.printList();
   }
}

输出:

4
6
8
10
12
14
16


© 著作权归作者所有

共有 人打赏支持
关西大汉弹琵琶
粉丝 7
博文 41
码字总数 14221
作品 0
浦东
程序员
私信 提问
【程序猿必备】数据结构与算法精选面试题

有很多计算机科学技术专业的毕业生和程序员申请在Uber和Netflix这样的初创公司、谷歌和阿里巴巴这样的大公司以及Infosys或Luxsoft等以服务为基础的公司从事编程、编码和软件开发工作,但他们...

【方向】
10/07
0
0
2015年1月9日XX大学XX学院考试题

复习 一、选择题 1.计算机算法指的是 。 A.计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 2. 下面关于算法说法正确的是( ) A.算法最终必须由计算机程序实现 B. 为解决某问题的...

请叫我赵小宝
2015/01/09
0
0
微软等公司数据结构+算法面试100题

1.把二元查找树转变成排序的双向链表(树) 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / / 6 14 / / / / 4 ...

chambai
2012/08/05
0
0
二叉树常见面试题

树是一种比较重要的数据结构,尤其是二叉树。二叉树是一种特殊的树,在二叉树中每个节点最多有两个子节点,一般称为左子节点和右子节点(或左孩子和右孩子),并且二叉树的子树有左右之分,其...

笨拙的小Q
2016/09/22
34
0
Android 面试文档分享

一、概述 最近在准备面试的东西,整理了一些读书笔记分享给各位 百度网盘地址,大家可以自由下载,以下内容完全原创。 前两部分是对于一些 经典书籍的读书笔记 和 面试题,都是上学看书的时候...

泽毛
2017/11/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

使用 React 和 Vue 创建相同的应用,他们有什么差异?

在工作中应用 Vue 之后,我对它有了相当深刻的理解。 不过,俗话说「外国的月亮比较圆」,我好奇「外国的」 React 是怎么样的。 我阅读了 React 文档并观看了一些教程视频,虽然它们很棒,但...

阿K1225
28分钟前
0
0
如何使用Kubernetes的configmap通过环境变量注入到pod里

在Kubernetes官网里,有这样一篇文章,提到了Kubernetes里的一个最佳实践就是把应用代码同配置信息分开,一种方式就是使用Kubernetes 1.2里引入的configmap概念。 https://kubernetes.io/bl...

JerryWang_SAP
43分钟前
0
0
2天闭门培训|以太坊智能合约从入门到实战(北京)

2天培训 16个课时 探寻技术原理,精通以太坊智能合约开发 以太坊智能合约是现在应用的最广泛的区块链应用开发方式,HiBlock区块链社区针对以太坊智能合约的学习特别推出2天闭门研修班,通过2...

HiBlock
46分钟前
0
0
限定某个目录禁止解析php,限制user_agent,php相关配置

11月20日任务 11.28 限定某个目录禁止解析php 11.29 限制user_agent 11.30/11.31 php相关配置 1.限定某个目录禁止解析php 核心配置文件内容 <Directory /data/wwwroot/www.123.com/upload> p...

hhpuppy
57分钟前
3
0
Spring的好文章

孤傲苍狼 https://www.cnblogs.com/xdp-gacl/p/4249939.html 跟我学spring http://jinnianshilongnian.iteye.com/blog/1413846 SpringIoc 和Spring Aop 代理模式: 静态代理 动态代理 cglib代......

wangwei2134
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部