public class TreeNode {
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
this.data=data;
left=null;
right=null;
}
}
public class Tree {
public TreeNode root;
//排序二叉树中插入节点
public void add(int data)
{
TreeNode node=new TreeNode(data);
if(root==null)
root=node;
else
{
TreeNode current=root;
TreeNode parent=root;
boolean isLeft=true;
while(current!=null)
{
parent=current;
if(data<current.data)
{
isLeft=true;
current=current.left;
}
else
{
isLeft=false;
current=current.right;
}
}
if(isLeft)
parent.left=node;
else
parent.right=node;
}
}
//将两个链表合并
public TreeNode append(TreeNode node1,TreeNode node2)
{
if(node1==null)
return node2;
if(node2==null)
return node1;
TreeNode tail=node1;
while(tail.right!=null)
tail=tail.right;
tail.right=node2;
node2.left=tail;
return node1;
}
//转换
public TreeNode convertoList(TreeNode node)
{
if(node==null)
return null;
TreeNode left=convertoList(node.left);
TreeNode right=convertoList(node.right);//将父节点独立
node.left=null;
node.right=null;
left=append(left,node);
left=append(left,right);
return left;
}
public void display(TreeNode head)
{
TreeNode current=head;
TreeNode parent=head;
while(current!=null)
{
System.out.print(current.data+" ");
parent=current;
current=current.right;
}
System.out.println();
while(parent!=null)
{
System.out.print(parent.data+" ");
parent=parent.left;
}
}
}
public class Test {
/**
* @param args
*/
public static void main(String[] args) {
Tree tree=new Tree();
tree.add(49);
tree.add(25);
tree.add(55);
tree.add(10);
tree.add(51);
tree.add(65);
TreeNode head=tree.convertoList(tree.root);
tree.display(head);
}
}
关于排序二叉树转换为双向链表的问题，以前自己做过，只是用了一个栈，后来在金山的笔试题目里面碰到了，而且不能使用任何额外的空间，就没想起来怎么办。前些天就在网上看一些常规的算法的运算，发现了有人将算法上传了，是将排序二叉树转换为双向循环链表，貌似比现在讨论的这个问题更复杂哈。其实是比目前这个容易解决的，因为头和尾能直接找到，而对于双向链表，要找尾节点还是需要从头遍历到尾的。废话少说，先说这个算法的思路，就是先把一个节点的左右孩子分别转换为双向链表，将父节点独立之后，先将左子树的链表与父节点连在一起，然后就上面的链表跟右子树的链表连接在一起，两个链表合并的操作是，将头一个链表的尾节点与第二个链表的头节点连在一起，就可以了。
我还做了一个测试，就是从前到后从后到前来输出链表的内容，结果证明是正确的。