Java算法系列10 — 二叉树转换为双向链表

Java算法系列10 — 二叉树转换为双向链表

实现思路：
1、先用前面学到的方法将一个有序数组转换成二叉树
2、假设当前遍历的结点为root，root的左子树已经被转换为双向链表
* 使用两个变量pHead与pEnd分别指向链表的头结点与尾节点
* 在遍历root结点时只需要将root结点的lchild指向pEnd，把pEnd的rchild指向root，root进入链表成为新 的pEnd

代码实现：

public static BITNode arrayToTree(int[] arr,int start,int end){BITNode root = null;if(end >= start){root = new BITNode();int mid = (start + end + 1)/2;//二叉树根节点为数组中间的元素root.data = arr[mid];//递归方法用左半部分数组构造root的左子树root.lchild = arrayToTree(arr,start,mid-1);//递归方法用右半部分数组构造root的右子树hild = arrayToTree(arr,mid+1,end);}else{root = null;}return root;}

    //双向链表头结点private static BITNode pHead = null;//双向链表尾结点private static BITNode pEnd = null;/*** 方法功能：把二叉树转换为双向链表* @param root 二叉树的根节点*/public static void inOrderBSTree(BITNode root){if(root == null){return;}//转换root的左子树inOrderBSTree(root.lchild);//使当前结点的左孩子指向双向链表中最后一个结点root.lchild = pEnd;//双向链表为空，当前遍历的结点为双向链表的头结点if(pEnd == null){pHead = root;}//使双向链表中最后一个结点的右孩子指向当前结点else {hild = root;}//将当前结点设为双向链表中最后一个结点pEnd = root;//转换root的右子树hild);}

最后遍历链表测试

public static void main(String[] args) {int[] arr = {1,2,3,4,5,6,7};BITNode root;root = arrayToTree(arr, 0, arr.length - 1);inOrderBSTree(root);BITNode cur;System.out.println("转换后双向链表正向遍历：");for(cur = pHead; cur != null; cur = hild){System.out.print(cur.data+" ");}System.out.println();System.out.println("转换后双向链表逆向遍历：");for(cur = pEnd; cur != null; cur = cur.lchild){System.out.print(cur.data+" ");}}