IT公司100题-1-二叉树转换为双链表
IT公司100题-1-二叉树转换为双链表
关西大汉弹琵琶 发表于2年前
IT公司100题-1-二叉树转换为双链表
  • 发表于 2年前
  • 阅读 92
  • 收藏 8
  • 点赞 0
  • 评论 0

腾讯云 技术升级10大核心产品年终让利>>>   

问题描述:

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

    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


共有 人打赏支持
粉丝 8
博文 40
码字总数 14221
×
关西大汉弹琵琶
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: