将二叉搜索树转换为排序的双向链表

步骤&＃xff1a;
1.找链表的首节点----就是树中最小的节点---->最小的节点就是树中最左侧节点。
2.按照中序遍历的规则来修改每个节点左右孩子的指向。
分析:每拿到- -个节点—只能修改当前节点的左指针域–原因:因为按照中序规则进行遍历&＃xff0c;肯定知道当前节点的前一个节点是那个节点(因为其前一个节点刚刚遍历过)&＃xff0c;当前节点的后序还没有遍历。

public class BSTree {public static class BSTNode{BSTNode left &＃61; null;BSTNode right &＃61; null;int val;BSTNode(int val){this.val &＃61; val;}}private BSTNode root &＃61; null;BSTNode prev &＃61; null;//标记中序遍历刚刚遍历过的节点。public BSTNode BSTree2DList(){if (null &＃61;&＃61; root){return null;}//1.找树中最左侧的节点&＃xff0c;即双向链表的头BSTNode head &＃61; root;while (null !&＃61; head.left){head &＃61; head.left;}//2.修改每个节点left和right的指向BSTree2DList(root);return head;}public void BSTree2DList(BSTNode root){if (null &＃61;&＃61; root){return;}//转化根节点的左子树BSTree2DList(root.left);//转化根节点root.left &＃61; prev;if (null !&＃61; prev){prev.right &＃61; root;}//用prev将刚刚遍历的节点保存起来。prev &＃61; root;BSTree2DList(root.right);}public static void TestBSTree2(){int[] array &＃61; {5,3,4,1,7,8,2,6,0,9};BSTree t &＃61; new BSTree();for (int e:array){t.put(e);}BSTNode head &＃61; t.BSTree2DList();BSTNode cur &＃61; head;while (cur!&＃61;null){System.out.print(cur.val &＃43; "----->");cur &＃61; cur.right;}System.out.println("NULL");}public static void main(String[] args) {TestBSTree2();}
}
/*
打印结果&＃xff1a;
0----->1----->2----->3----->4----->5----->6----->7----->8----->9----->NULL
*/