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

## 1. 把二元查找树转变成排序的双向链表 ##
### 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 ###
要求不能创建任何新的结点,只调整指针的指向。

10
       /   \
      6     14
     /  \  /  \
    4   8 12  16 
转换成双向链表 4=6=8=10=12=14=16。
首先我们定义的二元查找树节点的数据结构如下:

1 struct BSTreeNode
2     {
3         int m_nValue; // value of node
4         BSTreeNode *m_pLeft; // left child of node
5         BSTreeNode *m_pRight; // right child of node
6     };

下面是使用C++泛型写的一种算法:

  1 #include "stdafx.h"
  2 #include <string>
  3 #include <iostream>
  4 using namespace std;
  5
  6 template<typename T>
  7 struct BSTTreeNode
  8 {
  9     BSTTreeNode(T v, BSTTreeNode* lNode = NULL, BSTTreeNode* rNode=NULL)
 10         :m_Value(v), m_pLeft(lNode), m_pRight(rNode){}
 11     T m_Value;
 12     BSTTreeNode* m_pLeft;
 13     BSTTreeNode* m_pRight;
 14 };
 15
 16
 17 template<typename T>
 18 void TravelBSTree(BSTTreeNode<T> *root)
 19 {
 20     if (NULL == root)
 21     {
 22         return;
 23     }
 24
 25     TravelBSTree(root->m_pLeft);
 26
 27     printf("%d ", root->m_Value);
 28
 29     TravelBSTree(root->m_pRight);
 30
 31 }
 32
 33 template<typename T>
 34 void TravelBSTreeAsList(BSTTreeNode<T> *head, bool bReverseTravel = false)
 35 {
 36     BSTTreeNode<T>* pNode = head;
 37     while (pNode)
 38     {
 39         printf("%d ", pNode->m_Value);
 40         if (!bReverseTravel)
 41         {
 42             pNode = pNode->m_pRight;
 43         }
 44         else
 45         {
 46             pNode = pNode->m_pLeft;
 47         }
 48     }
 49 }
 50
 51 //思路:
 52 //查找树,中序遍历得到的节点排序即为排序的链表,而要求排序的双向链表,
 53 //1. 假设lt为左子树的中序遍历的尾结点,rh为右子树中序遍历的头结点
 54 //2. 化繁为简,如果只有root, lt, rh三个节点,此时只须然这几个节点连接起来即可。
 55 //3. 分别遍历左右子树,重复上述过程。
 56 template<typename T>
 57 void BSTreeHelper(BSTTreeNode<T>* &head, BSTTreeNode<T>* &tail, BSTTreeNode<T>* root)
 58 {
 59     //step 1.
 60     BSTTreeNode<T>* lt = NULL;//左子树尾结点
 61     BSTTreeNode<T>* rh = NULL;//右子树头结点
 62
 63     if (NULL == root)
 64     {
 65         head = nullptr;
 66         tail = nullptr;
 67         return;
 68     }
 69
 70     //step 3.
 71     BSTreeHelper(head, lt, root->m_pLeft);
 72     BSTreeHelper(rh, tail, root->m_pRight);
 73
 74     //step 2.
 75     if (NULL != lt)
 76     {
 77         lt->m_pRight = root;
 78         root->m_pLeft = lt;
 79     }
 80     else
 81     {
 82         head = root;
 83     }
 84
 85     if (NULL != rh)
 86     {
 87         root->m_pRight = rh;
 88         rh->m_pLeft = root;
 89     }
 90     else
 91     {
 92         tail = root;
 93     }
 94 }
 95
 96 template<typename T>
 97 BSTTreeNode<T>* TreeToLinkedList(BSTTreeNode<T>* root)
 98 {
 99     BSTTreeNode<T>* head = NULL;
100     BSTTreeNode<T>* tail = NULL;
101
102     BSTreeHelper(head, tail, root);
103
104     return head;
105 }
106
107 int _tmain(int argc, _TCHAR* argv[])
108 {
109     int arr[] = {4, 6, 8, 10, 12, 14, 16};
110
111     BSTTreeNode<int> node4(4);
112     BSTTreeNode<int> node8(8);
113     BSTTreeNode<int> node6(6, &node4, &node8);
114     BSTTreeNode<int> node12(12);
115     BSTTreeNode<int> node16(16);
116     BSTTreeNode<int> node14(14, &node12, &node16);
117     BSTTreeNode<int> node10(10, &node6, &node14);
118     BSTTreeNode<int>* pRoot = &node10;
119
120     printf("Travel BSTree: \n");
121     TravelBSTree<int>(pRoot);
122     printf("\n");
123
124     TreeToLinkedList<int>(pRoot);
125
126     printf("Travel BSTree: \n");
127     TravelBSTreeAsList<int>(&node4, false);
128     printf("\n");
129
130     TravelBSTreeAsList<int>(&node16, true);
131     printf("\n");
132
133     return 0;
134 }
时间: 06-30

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

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

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

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

转载请注明出处:http://www.cnblogs.com/wuzetiandaren/p/4256355.html  声明:现大部分文章为寻找问题时在网上相互转载,此博是为自己做个记录记录,方便自己也方便有类似问题的朋友,本文的思想也许有所借鉴,但源码均为本人实现,如有侵权,请发邮件表明文章和原出处地址,我一定在文章中注明.谢谢. 题目:输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表.要求不能创建任何新的结点,只调整指针的指向. 题目分析: 1.二叉树的节点有左右孩子指针,而双向

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

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