17 将二叉排序树转换为有序双链表

本文主要是介绍17 将二叉排序树转换为有序双链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言

本博文部分图片, 思路来自于剑指offer 或者编程珠玑

问题描述

这里写图片描述

思路

思路 : 因为要将二叉排序树更新各个结点的引用更新为一个有序双链表, 所以必然需要将左子树的最大结点和根节点和右子树的最小结点连在一起, 这样的话将左右子树看成一个整体, 整个链表就变成了”左子树 - 根节点 - 右子树”, 有序, 然后对于左右子树递归处理

参考代码

/*** file name : Test10BinarySortedTreeAndSortedLinkedList.java* created at : 5:36:06 PM Jun 7, 2015* created by 970655147*/package com.hx.test05;import com.hx.test04.Test17BinarySortTree.BinarySortTree;
import com.hx.test04.Test17BinarySortTree.Node;
import com.hx.util.Log;public class Test10BinarySortedTreeAndSortedLinkedList {// 将一颗二叉排序树 转化为一个有序双链表public static void main(String []args) {BinarySortTree bst = new BinarySortTree();int[] data = new int[] {10, 6, 14, 4, 8, 12, 16 };for(int i=0; i<data.length; i++) {bst.add(data[i]);}Log.log(bst.toString() );Log.horizon();//      Log.log(bst);transferBinarySortedTreeToSortedLinkedList(bst.root() );Node head = getMinNode(bst.root(), bst.root() );Node tmp = head;while(tmp != null) { Log.log(tmp);tmp = tmp.getRight();}Log.horizon();}// 先更新各个结点的指向// 最后 特殊处理  max.right, min.leftpublic static void transferBinarySortedTreeToSortedLinkedList(Node node) {transferBinarySortedTreeToSortedLinkedList0(node);getMaxNode(node, node).setRight(null);getMinNode(node, node).setLeft(null);}// 思路 : 获取node左边的最大的结点, 以及node右边的最小的结点// 设置这三个结点的关系, node.left = leftMax, node.right = rightMin, leftMax.right = node, rightMin.left = node// 如果leftMax 不为left  则递归transferBinarySortedTreeToSortedLinkedList0// 如果rightMax 不为right   则递归transferBinarySortedTreeToSortedLinkedList0private static void transferBinarySortedTreeToSortedLinkedList0(Node node) {if(node == null) {return ;}Node left = node.getLeft(), right = node.getRight();Node leftMax = getMaxNode(node.getLeft(), node);Node rightMin = getMinNode(node.getRight(), node);node.setLeft(leftMax);if(leftMax != null) {leftMax.setRight(node);}node.setRight(rightMin);if(rightMin != null) {rightMin.setLeft(node);}if((left != null) && (left != leftMax) ) {transferBinarySortedTreeToSortedLinkedList0(left);}if((right != null) && (right != rightMin) ) {transferBinarySortedTreeToSortedLinkedList0(right);}}// 获取node节点下最小的结点   并且不能小于unexpectedprivate static Node getMinNode(Node node, Node unexpected) {if(node == null) {return null;}Node tmp = node;while(tmp.getLeft() != null && tmp.getLeft() != unexpected) {tmp = tmp.getLeft();}return tmp;}// 获取node节点下 最大的结点   并且不能超过unexpectedprivate static Node getMaxNode(Node node, Node unexpected) {if(node == null) {return null;}Node tmp = node;while(tmp.getRight() != null && tmp.getRight() != unexpected) {tmp = tmp.getRight();}return tmp;}}