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 = 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 = 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

时间: 01-27

1.把二元查找树转变成排序的双向链表的相关文章

MS - 把二元查找树转变成排序的双向链表

## 1. 把二元查找树转变成排序的双向链表 ## ### 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表. ### 要求不能创建任何新的结点,只调整指针的指向. 10        /   \       6     14      /  \  /  \     4   8 12  16  转换成双向链表 4=6=8=10=12=14=16. 首先我们定义的二元查找树节点的数据结构如下: 1 struct BSTreeNode 2 { 3 int m_nValue; //

【编程题目】把二元查找树转变成排序的双向链表(树)

1.把二元查找树转变成排序的双向链表(树)题目:输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表.要求不能创建任何新的结点,只调整指针的指向. 10 / \ 6 14 / \ / \ 4 8 12 16转换成双向链表4=6=8=10=12=14=16.首先我们定义的二元查找树 节点的数据结构如下:struct BSTreeNode{int m_nValue; // value of nodeBSTreeNode *m_pLeft; // left child of nodeBSTree

二元查找树转化成排序的双向链表——要求不创建新的节点

码完第一次编译运行居然就成功了...高兴~ 问题描述: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表.要求不能创建任何新的结点,只调整指针的指向.例如: 10 /    \ 6     14 / \      /  \ 4   8  12  16 转换成双向链表 4=6=8=10=12=14=16 算法: 如果没有"不能创建任何新的结点"的限制,只需进行一次中序遍历,对每个节点的data值构造一个新节点即可. 由于条件限制,现在我们只能用现有的节点,调整他们的指针指向,把

Java实现: 把二元查找树转变成排序的双向链表(树)

题目 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表.要求不能创建任何新的结点,只调整指针的指向. 10 /    \ 6      14 /   \     /   \ 4    8  12   16 转换成双向链表4=6=8=10=12=14=16. 首先我们定义的二元查找树 节点的数据结构如下: struct BSTreeNode{ int m_nValue; // value of node BSTreeNode *m_pLeft;// left child of node

算法-1.把二元查找树转变成排序的双向链表

输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表. 要求不能创建任何新的结点,只调整指针的指向. 如下图.    10 /\ 6    14 /\     /\ 4 8 12 16 转换成双向链表 4=6=8=10=12=14=16. 这是一种二叉树的中序遍历. typedef struct BSTreeNode { int data; struct BSTreeNode *m_pLeft; struct BSTreeNode *m_pRight; }BSTreeNode,*pBSTr

把二元查找树转变成排序的双向链表

中序遍历 void ConvertNode(BSTreeNode* pNode, BSTreeNode*& pLastNodeInList){ if(pNode == NULL) return; BSTreeNode *pCurrent = pNode; // Convert the left sub-tree if (pCurrent->m_pLeft != NULL) ConvertNode(pCurrent->m_pLeft, pLastNodeInList); // Put t

[1]输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表

输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表.要求不能创建任何新的结点,只调整指针的指向.          10        /     \       6     14      / \     /  \     4  8 12  16转换成双向链表4=6=8=10=12=14=16 解: 二元查找树: 它首先要是一棵二元树,在这基础上它或者是一棵空树:或者是具有下列性质的二元树: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值: (2)若右子树不空,则右子树

二元查找树转换成一个排序的双向链表

输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表.要求不能创建任何新的结点,只调整指针的指向. 最直观的一种思路就是每次从二分查找树中找到最小的数,加到链表中 </pre><pre name="code" class="cpp">// BST2list.cpp : 定义控制台应用程序的入口点. // #include "stdafx.h" #include<iostream> using namesp

15.输入一颗二元查找树,将该树转换为它的镜像, 即在转换后的二元查找树中,左子树的结点都大于右子树的结点, 用递归和循环两种方法完成树的镜像转换

转载请注明出处:http://www.cnblogs.com/wuzetiandaren/p/4260432.html  声明:现大部分文章为寻找问题时在网上相互转载,此博是为自己做个记录记录,方便自己也方便有类似问题的朋友,本文的思想也许有所借鉴,但源码均为本人实现,如有侵权,请发邮件表明文章和原出处地址,我一定在文章中注明.谢谢. 题目:输入一颗二元查找树,将该树转换为它的镜像, 即在转换后的二元查找树中,左子树的结点都大于右子树的结点, 用递归和循环两种方法完成树的镜像转换. 题目分析: