Java实现: 把二元查找树转变成排序的双向链表(树)

题目

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

10

/    \

6      14

/   \     /   \

4    8  12   16

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

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

struct BSTreeNode{

int m_nValue;
// value of node

BSTreeNode *m_pLeft;// left child of node

BSTreeNode *m_pRight;// right child of node

};

解题思路

        熟悉二叉树中序展示的同学都知道,对于当前节点,先展示左子结点,然后展示自己,最后展示有子节点,使用这样的递归就完成二叉树的中序展示。

同理,这个算法同样使用上述方式完成,但是需要明白以下三点:

1.当前节点的最小子节点,也就是当前节点构成的双向链表的头元素为,当前元素的左子叶子节点。

2.当前节点构造的双向链表的下一个元素为,当前节点的右子节点的最小节点,见1.

3.当前节点构造的双向链表的上一个元素为,上一次操作的节点。

代码如下:

public class BSTreeNode {
	private Integer value;
	private BSTreeNode leftNode;
	private BSTreeNode rightNode;

	/**
	 * 插入节点。
	 * @param value
	 */
	public void add(int value) {
		if (this.value == null) {
			this.value = value;
		} else if (this.value > value) {
			if (leftNode == null){
				leftNode = new BSTreeNode();
				leftNode.value = value;
			} else {
				leftNode.add(value);
			}
		} else if (this.value < value) {
			if (rightNode == null){
				rightNode = new BSTreeNode();
				rightNode.value = value;
			} else {
				rightNode.add(value);
			}
		}
	}

	/**
	 * 中序遍历所有节点
	 */
	public List<BSTreeNode> list(){
		List<BSTreeNode> result = new ArrayList<BSTreeNode>();
		if (this.value == null){
			return result;
		}
		if (leftNode != null){
			result.addAll(leftNode.list());
		}
		result.add(this);
		if (rightNode != null){
			result.addAll(rightNode.list());
		}
		return result;
	}

	public BSTreeNode convertLinkedList(){
		Map<String, BSTreeNode> map = new HashMap<String, BSTreeNode>();
		doConvertLinkedList(map);
		return map.get("headNode");
	}

	private void doConvertLinkedList(Map<String, BSTreeNode> map){
		if (leftNode != null){
			leftNode.doConvertLinkedList(map);
		}
		handleCurrentNode(map);
		if (rightNode != null){
			rightNode.doConvertLinkedList(map);
		}
	}

	private void handleCurrentNode(Map<String, BSTreeNode> map){
		BSTreeNode lastNode = map.get("lastNode");
		this.leftNode = lastNode;
		if (lastNode == null){
			map.put("headNode", this);
		} else {
			lastNode.rightNode = this;
		}
		map.put("lastNode", this);
	}

	public Integer getValue(){
		return this.value;
	}

	public BSTreeNode getLeftNode(){
		return this.leftNode;
	}

	public BSTreeNode getRightNode(){
		return this.rightNode;
	}
}

jUnit测试如下

public class BSTreeNodeTest {

	@Test
	public void testAdd(){
		BSTreeNode root = new BSTreeNode();
		root.add(10);
		assertEquals(root.getValue(), Integer.valueOf(10));
		root.add(20);
		assertEquals(root.getRightNode().getValue(), Integer.valueOf(20));
		root.add(30);
		assertEquals(root.getRightNode().getRightNode().getValue(), Integer.valueOf(30));
		root.add(25);
		assertEquals(root.getRightNode().getRightNode().getLeftNode().getValue(), Integer.valueOf(25));
	}

	@Test
	public void testList() {
		BSTreeNode root = new BSTreeNode();
		List<Integer> valueList = new ArrayList<Integer>();
		valueList.add(10);
		valueList.add(20);
		valueList.add(30);
		valueList.add(25);
		for (Integer value : valueList){
			root.add(value.intValue());
		}
		List<BSTreeNode> nodeList = root.list();
		Collections.sort(valueList);
		for (int i = 0; i < nodeList.size(); i++){
			BSTreeNode node = nodeList.get(i);
			assertEquals(node.getValue(), valueList.get(i));
		}
	}

	@Test
	public void testConvertLinkedList(){
		BSTreeNode root = new BSTreeNode();
		int count = 100;
		Random random = new Random();
		List<Integer> valueList = new ArrayList<Integer>();
		for (int i = 0; i < count; i++){
			int value = random.nextInt(1000);
			if (!valueList.contains(value)){
				valueList.add(value);
			}
		}
		for (Integer value : valueList){
			root.add(value.intValue());
		}
		Collections.sort(valueList);
		BSTreeNode currentNode = root.convertLinkedList();
		for (int i = 0; i < valueList.size(); i++){
			assertEquals(currentNode.getValue(), valueList.get(i));
			currentNode = currentNode.getRightNode();
		}
	}

}

时间: 01-31

Java实现: 把二元查找树转变成排序的双向链表(树)的相关文章

【编程题目】把二元查找树转变成排序的双向链表(树)

1.把二元查找树转变成排序的双向链表(树)题目:输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表.要求不能创建任何新的结点,只调整指针的指向. 10 / \ 6 14 / \ / \ 4 8 12 16转换成双向链表4=6=8=10=12=14=16.首先我们定义的二元查找树 节点的数据结构如下:struct BSTreeNode{int m_nValue; // value of nodeBSTreeNode *m_pLeft; // left child of nodeBSTree

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

## 1. 把二元查找树转变成排序的双向链表 ## ### 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表. ### 要求不能创建任何新的结点,只调整指针的指向. 10        /   \       6     14      /  \  /  \     4   8 12  16  转换成双向链表 4=6=8=10=12=14=16. 首先我们定义的二元查找树节点的数据结构如下: 1 struct BSTreeNode 2 { 3 int m_nValue; //

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

转载请注明出处:http://www.cnblogs.com/wuzetiandaren/p/4256355.html  声明:现大部分文章为寻找问题时在网上相互转载,此博是为自己做个记录记录,方便自己也方便有类似问题的朋友,本文的思想也许有所借鉴,但源码均为本人实现,如有侵权,请发邮件表明文章和原出处地址,我一定在文章中注明.谢谢. 题目:输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表.要求不能创建任何新的结点,只调整指针的指向. 题目分析: 1.二叉树的节点有左右孩子指针,而双向

二元查找树转化成排序的双向链表——要求不创建新的节点

码完第一次编译运行居然就成功了...高兴~ 问题描述: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表.要求不能创建任何新的结点,只调整指针的指向.例如: 10 /    \ 6     14 / \      /  \ 4   8  12  16 转换成双向链表 4=6=8=10=12=14=16 算法: 如果没有"不能创建任何新的结点"的限制,只需进行一次中序遍历,对每个节点的data值构造一个新节点即可. 由于条件限制,现在我们只能用现有的节点,调整他们的指针指向,把

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

输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表. 要求不能创建任何新的结点,只调整指针的指向. 如下图.    10 /\ 6    14 /\     /\ 4 8 12 16 转换成双向链表 4=6=8=10=12=14=16. 这是一种二叉树的中序遍历. typedef struct BSTreeNode { int data; struct BSTreeNode *m_pLeft; struct BSTreeNode *m_pRight; }BSTreeNode,*pBSTr

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

中序遍历 void ConvertNode(BSTreeNode* pNode, BSTreeNode*& pLastNodeInList){ if(pNode == NULL) return; BSTreeNode *pCurrent = pNode; // Convert the left sub-tree if (pCurrent->m_pLeft != NULL) ConvertNode(pCurrent->m_pLeft, pLastNodeInList); // Put t

将二叉搜索树转变成排序的双向链表

将二叉搜索树转变成排序的双向链表: 点击链接: http://blog.csdn.net/l_tudou/article/details/51753921

二叉查找树转换成排序的双向链表

题目:输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表.要求不能创建任何 新的结点,只调整指针的指向. 比如将二元查找树 10 / \ 6 14 / \ / \ 4 8 12 16 转换成双向链表 4=6=8=10=12=14=16. 思路:对于树的很多题目,都可以使用递归的方法来处理.这道题目也不例外.我们从最基本的思路来考虑这个题目. 把一个二叉树编程双向链表,最终是一个有序的序列,也就是中序遍历之后的结果,那么当我们采用中序遍历的方式遍历二叉树时,遍历到某个节点,是的前序节点的右

C语言强化(一)二叉排序树转成排序的双向链表

几乎每一位码士的编程起点都是C,在玩过了Java.C#.PHP.Python之后,重回C语言,又是什么样的一种感觉呢? 此篇博文作为 [C语言强化]系列文章的第一篇,来聊聊曾让许多码士抓耳挠腮的二叉树. 通过这道题,你可以掌握 如何创建二叉树 如何遍历二叉树 如何创建二叉链表 怎样使用递归算法 这是一道非常老土但又十分经典的数据结构题,或许很多人会说自己之前已经做过了,但又有多少人回过头来做的时候,可以不借助任何参考资料把解题思路写出来? 题目要求:二叉排序树->双向链表排序 不能新增结点,只能