首页 > 代码库 > Java实现: 把二元查找树转变成排序的双向链表(树)
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 =http://www.mamicode.com/= null) {>
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 = http://www.mamicode.com/random.nextInt(1000);>
Java实现: 把二元查找树转变成排序的双向链表(树)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。