首页 > 代码库 > 1.把二元查找树转变成排序的双向链表
1.把二元查找树转变成排序的双向链表
转载请注明出处：http://www.cnblogs.com/wuzetiandaren/p/4256355.html
声明：现大部分文章为寻找问题时在网上相互转载，此博是为自己做个记录记录，方便自己也方便有类似问题的朋友，本文的思想也许有所借鉴，但源码均为本人实现，如有侵权，请发邮件表明文章和原出处地址，我一定在文章中注明。谢谢。
题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。
题目分析：
1.二叉树的节点有左右孩子指针，而双向链表的节点有前驱和后继指针。
树节点的数据结构：
1 //创建一个树节点类 2 class Node<E> { 3 public int data; 4 public Node left; //指向左孩子的指针 5 public Node right; //指向右孩子的指针 6 public Node() { 7 super(); 8 } 9 public Node(int data, Node left, Node right) {10 super();11 this.data =http://www.mamicode.com/ data;12 this.left = left;13 this.right = right;14 }15 }
2.二叉排序树的中序遍历 结果刚好是升序的，改造时按照中序遍历的顺序重新改变节点的指针就行了，使其 左孩子指向前驱，右孩子指向后继。
java实现源码：
1 package com.interview; 2 3 import java.util.LinkedList; 4 5 /** 6 * 题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。 7 * 要求不能创建任何新的结点，只调整指针的指向。 8 * 分析：二叉树的节点有左右孩子指针，而双向链表有前驱和后继，二叉排序树的中序遍历 9 * 是升序的结果，改造时按照中序遍历的顺序重新改变节点的指针就行了，使其 10 * 左孩子指向前驱，有孩子指向后继 11 * @author wjh 12 * 13 */ 14 public class _14TreeToDList { 15 16 /** 17 * @param args 18 */ 19 public static void main(String[] args) { 20 _14TreeToDList builder= new _14TreeToDList(); 21 int[] a = {56,45,47,67,35,76,22,89,91,27,11,21,19,87}; 22 Node tree = null; 23 LinkedList<Node> nodelist = new LinkedList<Node>(); //保存二叉树的中序遍历结果 24 tree = builder.buildTree(tree, a); //1)建二叉排序树 25 System.out.println("\n二叉排序树的中序遍历结果："); 26 nodelist = builder.inOrder(tree,nodelist);//2)得到二叉树的中序遍历结果 27 Node first = builder.translate(nodelist); //3)将二叉排序树转换成双链表 28 builder.printList(first); //4)打印双链表 29 } 30 31 //将二叉排序树改造为双向排序链表,左孩子指针指向前去，右孩子指针指向后继 32 private Node translate(LinkedList<Node> nodelist){ 33 int size = nodelist.size(); 34 if(size==0){ 35 return null; 36 } 37 Node first = nodelist.get(0); //链表的第一个节点，也是链表的入口 38 if(size==1){ //只有一个节点的双链表 39 first.left = null; //因为是双链表而非双循环链表,不能first.left=first; 40 first.right = null; 41 } 42 else if(size>1){ //有两个及以上节点的双链表 43 first.left = null; 44 first.right = nodelist.get(1); 45 for(int i=1;i<size-1;i++){ 46 nodelist.get(i).left = nodelist.get(i-1); 47 nodelist.get(i).right = nodelist.get(i+1); 48 } 49 nodelist.get(size-1).left = nodelist.get(size-2); 50 nodelist.get(size-1).right = null; 51 } 52 return first; 53 } 54 55 //打印双链表 56 private void printList(Node first){ 57 Node temp = first; //temp 保存最后一个节点,以方便逆序打印 58 System.out.println("\n\n这是正向打印双链表："); 59 while(first!=null){ 60 if(first.right!=null){ 61 System.out.print(first.data+"<->"); 62 } 63 else{ 64 System.out.print(first.data); 65 temp = first; //最后一个节点 66 } 67 first = first.right; 68 } 69 first = temp; 70 System.out.println("\n\n这是逆向打印双链表："); 71 while(first!=null){ 72 if(first.left!=null){ 73 System.out.print(first.data+"<->"); 74 } 75 else 76 System.out.print(first.data); 77 first = first.left; 78 } 79 } 80 81 //二叉树的中序遍历 82 private LinkedList<Node> inOrder(Node root,LinkedList<Node> nodelist){ 83 Node temp = root; 84 if(root==null){ 85 return null; 86 } 87 else{ 88 inOrder(root.left,nodelist); 89 System.out.print(root.data+" "); 90 nodelist.add(root); 91 inOrder(root.right,nodelist); 92 } 93 return nodelist; 94 } 95 96 //建树 97 private Node buildTree(Node root, int[] data) { 98 System.out.println("建树过程(a<--b表示想a的左边插入b;a-->b表示想a的右边插入b):"); 99 for (int i = 0; i < data.length; i++) {100 root=insert(root, data[i]);101 }102 return root;103 }104 105 //一次插入节点106 private Node insert(Node node, int data) {107 if (node == null) {108 node = new Node(data,null,null);109 System.out.println(node.data);110 }else{ 111 if(data <= node.data) {112 System.out.print(node.data+"<--");113 node.left = insert(node.left, data);114 } else {115 System.out.print(node.data+"-->");116 node.right = insert(node.right, data);117 }118 }119 return node;120 }121 122 //创建一个树节点类123 class Node<E> {124 public int data;125 public Node left; //指向左孩子的指针 126 public Node right; //指向右孩子的指针 127 public Node() {128 super();129 }130 public Node(int data, Node left, Node right) {131 super();132 this.data =http://www.mamicode.com/ data;133 this.left = left;134 this.right = right;135 }136 }137 }
运行结果：
建树过程(a<--b表示想a的左边插入b;a-->b表示想a的右边插入b):
56
56<--45
56<--45-->47
56-->67
56<--45<--35
56-->67-->76
56<--45<--35<--22
56-->67-->76-->89
56-->67-->76-->89-->91
56<--45<--35<--22-->27
56<--45<--35<--22<--11
56<--45<--35<--22<--11-->21
56<--45<--35<--22<--11-->21<--19
56-->67-->76-->89<--87
二叉排序树的中序遍历结果：
11 19 21 22 27 35 45 47 56 67 76 87 89 91
这是正向打印双链表：
11<->19<->21<->22<->27<->35<->45<->47<->56<->67<->76<->87<->89<->91
这是逆向打印双链表：
91<->89<->87<->76<->67<->56<->47<->45<->35<->27<->22<->21<->19<->11
1.把二元查找树转变成排序的双向链表
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。