当前位置:首页 > 开发 > 编程语言 > Java > 正文

java-1.二叉查找树转为双向链表

发表于: 2012-01-12   作者:bylijinnan   来源:转载   浏览:
摘要: import java.util.ArrayList; import java.util.List; public class BSTreeToLinkedList { /* 把二元查找树转变成排序的双向链表 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / \ 6 14 / \
import java.util.ArrayList;
import java.util.List;


public class BSTreeToLinkedList {
	
	/*
把二元查找树转变成排序的双向链表
题目:
输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点,只调整指针的指向。
10
/ \
6 14
/ \ / \
4 8 12 16
转换成双向链表
4=6=8=10=12=14=1
	 */
	public static void main(String[] args) {
		BSTreeToLinkedList bn=new BSTreeToLinkedList();
		int[] a={10,6,14,4,8,12,16};//这些数据是按二叉查找树的层次遍历存放
		Node head=bn.creatTree(a);
		bn.toTwoWayLinkedList(head);
		bn.printTwoLinkedList(head);
		
	}

	/*
	 * 思路:中序遍历二叉树,将上次访问的节点记为previous,当前访问的节点记为current;

           对于遍历过程中的每个当前节点,让该节点的左指针指向previous(current->left = previous),让previous的右指针

           指向当前节点(previous->right = current),然后将previous更新为current。当中序遍历结束时,二叉搜索树也

           被转化为双链表了。
           
          具体思路可参见:http://hi.baidu.com/gropefor/blog/item/d2144f8ce0325105b31bba11.html
           
         问题:这个previous只能作为类成员才能得到正确的结果,作为局部变量的话,我得不到正解。
              我尝试过这样写: toTwoWayLinkedList(Node node,Node previous),在main函数里面调用时候,用
			toTwoWayLinkedList(head,null),得不到正确答案
	 */
	private Node previous;
	public void toTwoWayLinkedList(Node node){
		if(node!=null){
			toTwoWayLinkedList(node.getLeft());
			if(previous!=null){
				previous.setRight(node);
				node.setLeft(previous);
			}
			previous=node;
			toTwoWayLinkedList(node.getRight());
		}
	}
	public void printTwoLinkedList(Node node){
		if(node!=null){
			//after converting to List,head=a[0]=10,but the head is not the actually head of list.
			//the true head is 4.
			while(node.getLeft()!=null){
				node=node.getLeft();//find the true Head.
			}
			while(node!=null){
				System.out.print(node.getData()+" ");
				node=node.getRight();
			}
		}
	}
	public Node creatTree(int[] data){
		List<Node> nodeList=new ArrayList<Node>();
		for(int each:data){
			Node node=new Node(each);
			nodeList.add(node);
		}
		int lastRootIndex=data.length/2-1;
		for(int i=lastRootIndex;i>=0;i--){
			int leftIndex=i*2+1;
			Node root=nodeList.get(i);
			Node left=nodeList.get(leftIndex);
			root.setLeft(left);
			if(leftIndex+1<data.length){
				Node right=nodeList.get(leftIndex+1);
				root.setRight(right);
			}
		}
		Node head=nodeList.get(0);
		return head;
		
	}
	
	
}

class Node{
	private int data;
	private Node left;
	private Node right;
	
	public Node(int i){
		data=i;
	}
	public int getData() {
		return data;
	}
	public void setData(int data) {
		this.data = data;
	}
	public Node getLeft() {
		return left;
	}
	public void setLeft(Node left) {
		this.left = left;
	}
	public Node getRight() {
		return right;
	}
	public void setRight(Node right) {
		this.right = right;
	}
}

java-1.二叉查找树转为双向链表

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
题目: 输入一颗二叉搜索树,将该二叉搜索树转换成一个排序的双向链表,要求不能创建任何新的节点,
一、题目   要求输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建新的
题目: 输入一颗二叉搜素树,将该树转换成一个排序的双向链表.要求不能创建新的结点,只能 调整树中结
分析: 1. 二叉树中,每个结点都有两个指向子结点的指针。 2. 在双向链表中,每个结点也有两个指针
分析: 1:由于要求链表是有序的,可以借助二叉树中序遍历,因为中序遍历算法的特点就是从小到大访
题目参看csdn上的一个很经典的帖子,http://topic.csdn.net/u/20101126/10/b4f12a00-6280-492f-b785
题目:输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求:不能创建任何新的结点
题意:不引入新节点,只允许指针操作,实现二元查找树转换为相应双向链表。 10 / / 6 14 / / / / 4
【试题描述】 将二叉搜索树转换为双向链表 对于二叉搜索树,可以将其转换为双向链表,其中,节点的
一、题目:二叉搜索树与双向链表 题目:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号