# 二叉查找树转双向链表JAVA实现

2016/11/28 10:00

1. /**
2. public class TreeNode {
3.     int val = 0;
4.     TreeNode left = null;
5.     TreeNode right = null;
6.
7.     public TreeNode(int val) {
8.         this.val = val;
9.
10.     }
11.
12. */
13. public class Solution {
15.     private TreeNode tail=null;
16.     public TreeNode Convert(TreeNode pRootOfTree) {
17.         visit(pRootOfTree);
19.     }
20.     public void visit(TreeNode root) {
21.         if (root == null) {
22.             return;
23.         }
24.         visit(root.left);
25.         createList(root);
26.         visit(root.right);
27.     }
28.     public void createList(TreeNode cur){
29.         cur.left=tail;//把当前的节点接到链表的尾部
30.         if(tail!=null){//双向连接
31.             tail.right=cur;
32.         }else{
34.         }
35.         tail=cur;//更新尾结点为当前结点，或者说：尾结点后移
36.     }

public static BinaryTreeNode baseconvert(BinaryTreeNode root, BinaryTreeNode lastNode) {

if (root == null)

return lastNode;

BinaryTreeNode current = root;

if (current.leftNode != null)

lastNode=baseconvert(current.leftNode, lastNode);

current.leftNode = lastNode;

if (lastNode != null)

lastNode.rightNode = current;

lastNode = current;

if (current.rightNode != null)

lastNode=baseconvert(current.rightNode, lastNode);

return lastNode;

}

current为当前子树的根节点

6和4的双向连接就完成了，由于6的右子树存在，又会递归到右边子树去，由于8不存在左右子树，递归下去一层之后current就是8这个节点，但它的左孩子为空，所以不会左边递归下去，将8的左连接与之前的lastNode连接起来，建立双向连接的一条连接，然后由于lastNode不为空，所以又把lastNode的右连接与8连接起来，至此双向连接建立，此时lastNode为8

public static BinaryTreeNode convert(BinaryTreeNode root) {

BinaryTreeNode lastNode = null;

lastNode=baseconvert(root, lastNode);

}

public static void main(String[] args) {

// TODO Auto-generated method stub

BinaryTreeNode root = new BinaryTreeNode(10);

BinaryTreeNode six=new BinaryTreeNode(6);

BinaryTreeNode four=new BinaryTreeNode(4);

BinaryTreeNode eight=new BinaryTreeNode(8);

BinaryTreeNode fourteen=new BinaryTreeNode(14);

BinaryTreeNode twelve=new BinaryTreeNode(12);

BinaryTreeNode sixteen=new BinaryTreeNode(16);

root.leftNode=six;

root.rightNode=fourteen;

six.leftNode=four;

six.rightNode=eight;

four.leftNode=null;

four.rightNode=null;

eight.leftNode=null;

eight.rightNode=null;

fourteen.leftNode=twelve;

fourteen.rightNode=sixteen;

twelve.leftNode=null;

twelve.rightNode=null;

sixteen.rightNode=null;

sixteen.leftNode=null;

BinaryTreeNode result=convert(root);

//                BinaryTreeNode result=baseconvert(root, null);

while (result!=null) {

System.out.println(result.data);

result=result.rightNode;

}

0
0 收藏

0 评论
0 收藏
0