《微软面试100题 In Java》01.二元查寻树转变成排序的双向链表

《微软面试100题 In Java》01.二元查找树转变成排序的双向链表

大三下学期了，也到了找暑假实习工作的时间了，所以最近准备刷一些面试题，首先我是从July的《微软面试100题系列》开始刷起，刷完这个之后，我会再找一些题继续练习。这些题我都是用java解的。

1.把二元查找树转变成排序的双向链表

题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。
比如将二元查找树
10
/ \
6 14
/ \ /　 \
　4 8 12 　 16
转换成双向链表

4=6=8=10=12=14=16。

分析：本题是微软的面试题。很多与树相关的题目都是用递归的思路来解决，本题也不例外。我们可以中序遍历整棵树。按照这个方式遍历树，比较小的结点先访问。如果我们每访问一个结点，假设之前访问过的结点已经调整成一个排序双向链表，我们再把调整当前结点的指针将其链接到链表的末尾。当所有结点都访问过之后，整棵树也就转换成一个排序双向链表了。

java实现的代码

下面用到的二查找树的中序遍历和元素的插入可以参照我前面的博客：Binary search tree（二叉查找树）

还用到了双链表的输入输出可参照：Stacks,Queues,Linked Lists

import java.util.ListIterator;
import java.util.NoSuchElementException;

class BSTnode<K>{
	private K nodeValue ;
	private BSTnode<K> nodeLeft ;
	private BSTnode<K> nodeRight ;
	
	public BSTnode(K nodeValue,BSTnode<K> nodeLeft,BSTnode<K> nodeRight){
		this.nodeValue = nodeValue ;
		this.nodeLeft = nodeLeft ;
		this.nodeRight = nodeRight ;
	}
	
	public K getNode(){ return nodeValue ; } 
	public BSTnode<K> getLeft(){ return nodeLeft ;}
	public BSTnode<K> getRight(){ return nodeRight ;}
	
	public void setNode(K nodeValue){ this.nodeValue = nodeValue ;}
	public void setLeft(BSTnode<K> nodeLeft){ this.nodeLeft = nodeLeft ;}
	public void setRight(BSTnode<K> nodeRight){ this.nodeRight = nodeRight ;}
	
}
class BST{
	private BSTnode<Integer> root ;
	private DoubleLinkedList<Integer> list = new DoubleLinkedList<Integer>() ;
	public BST(){ root = null ;}
	public BSTnode<Integer> getRoot(){ return root ;}
	public void setRoot(BSTnode<Integer> root){this.root = root ; }
	
	/****insert*****/
	public void insert(BSTnode<Integer> newNode){
		BSTnode<Integer> y = null ;
		BSTnode<Integer> x = this.getRoot() ;
		
		while(x!=null){
			y = x ;
			if(newNode.getNode()<x.getNode()){
				x = x.getLeft() ;
			}else{
				x = x.getRight() ;
			}
		}
		if(y==null){
			this.setRoot(newNode) ;
		}else if(newNode.getNode()<y.getNode()){
			y.setLeft(newNode) ;
		}else{
			y.setRight(newNode) ;
		}
	}
	
	/*******tree Traversal********/
	public DoubleLinkedList<Integer> inorder(BSTnode<Integer> x){
		
		if(x!=null){
			inorder(x.getLeft()) ;
			list.add(x.getNode()) ;
			//System.out.println(x.getNode()) ;
			inorder(x.getRight()) ;
		}
		return list ;
	}
	
}
public class Bstolist{
	public static void main(String args[])throws Exception{
		BST bst1 = new BST() ;
		BSTnode<Integer> bstnode1 = new BSTnode<Integer>(10,null,null) ;
		BSTnode<Integer> bstnode2 = new BSTnode<Integer>(6,null,null) ;
		BSTnode<Integer> bstnode3 = new BSTnode<Integer>(14,null,null) ;
		BSTnode<Integer> bstnode4 = new BSTnode<Integer>(4,null,null) ;
		BSTnode<Integer> bstnode5 = new BSTnode<Integer>(8,null,null) ;
		BSTnode<Integer> bstnode6 = new BSTnode<Integer>(12,null,null) ;
		BSTnode<Integer> bstnode7 = new BSTnode<Integer>(16,null,null) ;
		bst1.insert(bstnode1) ;
		bst1.insert(bstnode2) ;
		bst1.insert(bstnode3) ;
		bst1.insert(bstnode4) ;
		bst1.insert(bstnode5) ;
		bst1.insert(bstnode6) ;
		bst1.insert(bstnode7) ;
		//中序遍历
		DoubleLinkedList<Integer> list1 = bst1.inorder(bstnode1) ;
		System.out.println(list1) ;
	}
}


class DoubleLinkedList<Item>{
    private int N=0 ;        // number of elements on list
    private Node pre;     // sentinel before first item
    private Node post;    // sentinel after last item

	public int getN(){ return N ;}
    public DoubleLinkedList() {
        pre  = new Node();
        post = new Node();
        pre.next = post;
        post.prev = pre;
    }

    // linked list node helper data type
    class Node {
        private Item item;
        private Node next;
        private Node prev;
    }
	
    public boolean isEmpty()    { return N == 0; }
    public int size()           { return N;      }

    // add the item to the list
    public void add(Item item) {
		Node n = new Node() ;
		n.item = item ;
		if(isEmpty()){
			this.pre = n ;
			this.post = n ;
			n.prev = null ;
			n.next = null ;
		}else{
			n.prev = this.post ;
			n.next = this.post.next ;
			this.post.next = n ;
			this.post = n ;
		}
		N++ ;
    }
	//print doublylinkedlist
	public String toString() {
		StringBuilder s = new StringBuilder();
		Node n = this.pre ;
		while(n!=null){
			s.append(n.item + " ");
			n = n.next ;
		}
       return s.toString();
    }
}

总结：用到的知识点有 1.二叉树的建立 2.二叉查找树的中序遍历 3.二叉查找树的元素插入4.双链表的建立5.双链表元素的插入6.双链表的输出

《微软面试100题 In Java》01.二元查寻树转变成排序的双向链表

相关推荐