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

1.把二元查找树转变成排序的双向链表(树)
题目:
输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点,只调整指针的指向。
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
BSTreeNode *m_pRight; // right child of node
};

我的思路:找到最小元素做头结点,不断的找其后继,调整指针的指向。写了一个半小时!

  1 /*
  2 1.把二元查找树转变成排序的双向链表(树)
  3 题目:
  4 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。
  5 要求不能创建任何新的结点,只调整指针的指向。
  6      10
  7     /   8    6   14
  9   / \  /  10   4 8 12 16
 11 转换成双向链表
 12 4=6=8=10=12=14=16。
 13 首先我们定义的二元查找树  节点的数据结构如下:
 14 struct BSTreeNode
 15 {
 16 int m_nValue; // value of node
 17 BSTreeNode *m_pLeft; // left child of node
 18 BSTreeNode *m_pRight; // right child of node
 19 };
 20 start time = 14:31
 21 end time = 16:04
 22 */
 23 #include <iostream>
 24 #include <stdlib.h>
 25 using namespace std;
 26
 27 typedef struct BSTreeNode
 28 {
 29 int m_nValue; // value of node
 30 BSTreeNode *m_pLeft; // left child of node
 31 BSTreeNode *m_pRight; // right child of node
 32 }BSTreeNode;
 33
 34 int addBSTreeNode(BSTreeNode * &T, int data)  //把data加入的以T为根的树中
 35 {
 36     if(T == NULL) //根节点单独处理
 37     {
 38         T = (BSTreeNode *)malloc(sizeof(BSTreeNode));
 39         T->m_nValue = data;
 40         T->m_pLeft = NULL;
 41         T->m_pRight = NULL;
 42     }
 43     else
 44     {
 45         BSTreeNode * x = T;
 46         BSTreeNode * px = NULL;
 47         while(x != NULL)
 48         {
 49             if(data >= x->m_nValue)
 50             {
 51                 px = x;
 52                 x = x->m_pRight;
 53             }
 54             else
 55             {
 56                 px = x;
 57                 x = x->m_pLeft;
 58             }
 59         }
 60
 61         if(data >= px->m_nValue)
 62         {
 63             px->m_pRight = (BSTreeNode *)malloc(sizeof(BSTreeNode));
 64             px->m_pRight->m_nValue = data;
 65             px->m_pRight->m_pLeft = NULL;
 66             px->m_pRight->m_pRight = NULL;
 67         }
 68         else
 69         {
 70             px->m_pLeft = (BSTreeNode *)malloc(sizeof(BSTreeNode));
 71             px->m_pLeft->m_nValue = data;
 72             px->m_pLeft->m_pLeft = NULL;
 73             px->m_pLeft->m_pRight = NULL;
 74         }
 75     }
 76     return 1;
 77 }
 78
 79 BSTreeNode * findMin(BSTreeNode * z)
 80 {
 81     BSTreeNode * x = z;
 82     while(x->m_pLeft != NULL)
 83     {
 84         x = x->m_pLeft;
 85     }
 86     return x;
 87 }
 88
 89 BSTreeNode * findMax(BSTreeNode * z)
 90 {
 91     BSTreeNode * x = z;
 92     while(x->m_pRight != NULL)
 93     {
 94         x = x->m_pRight;
 95     }
 96     return x;
 97 }
 98
 99 BSTreeNode * findparent(BSTreeNode * T,BSTreeNode * z)
100 {
101     BSTreeNode * x = T;
102     BSTreeNode * px = NULL;
103     while(x != NULL)
104     {
105         if(z->m_nValue > x->m_nValue)
106         {
107             px = x;
108             x = x->m_pRight;
109         }
110         else if(z->m_nValue < x->m_nValue)
111         {
112             px = x;
113             x = x->m_pLeft;
114         }
115         else
116         {
117             if(z == x) //对数值相同的情况做判断
118             {
119                 return px;
120             }
121             else
122             {
123                 px = x;
124                 x = x->m_pRight;
125             }
126         }
127     }
128     return NULL;
129 }
130
131 BSTreeNode * BSTreefindSuccessor(BSTreeNode * T, BSTreeNode * z) //找二元查找树某个节点的后继
132 {
133     if(z->m_pRight != NULL)
134     {
135         return  findMin(z->m_pRight);
136     }
137     else
138     {
139         BSTreeNode * y = findparent(T, z);
140         while(y != NULL && z == y->m_pRight)
141         {
142             z = y;
143             y = findparent(T, z);
144         }
145         return y;
146     }
147 }
148
149 BSTreeNode * BSTree2OrderedList(BSTreeNode * T) //把二元查找树转换为排序的双向链表
150 {
151     BSTreeNode * start = findMin(T);
152     BSTreeNode * end = findMax(T);
153     BSTreeNode * x = start;
154     BSTreeNode * root = T;
155     while(x != NULL)
156     {
157         BSTreeNode * xs = BSTreefindSuccessor(root, x);
158         if(xs == root && root != NULL) //当root 左右子树的指向改变的时候 要更新找后继的树根 否则根的右子树变化了 用找后继会出错
159         {
160             root = root->m_pRight;
161         }
162         if(xs != NULL)
163         {
164             x->m_pRight = xs;  //向右指向下一个比它大的值
165             xs->m_pLeft = x;   //向左指向下一个比它小的值
166         }
167         x = xs;
168     }
169     return start;
170 }
171
172
173 int main()
174 {
175     BSTreeNode * T = NULL;
176     addBSTreeNode(T, 10);
177     addBSTreeNode(T, 6);
178     addBSTreeNode(T, 6);
179     addBSTreeNode(T, 4);
180     addBSTreeNode(T, 8);
181     addBSTreeNode(T, 12);
182     addBSTreeNode(T, 16);
183
184     BSTreeNode * ans = BSTree2OrderedList(T);
185
186     return 0;
187
188 }

之后上网看看别人的 结果人家一个中序遍历就搞定了啊!

来源:http://blog.csdn.net/wcyoot/article/details/6428297

 1 template<typename T>
 2 struct TreeNode
 3 {
 4     T data;
 5     TreeNode* pLChild;
 6     TreeNode* pRChild;
 7 };
 8
 9 // 要求两个输出参数要初始化为NULL
10 template<typename T>
11 void ConvertBSTree2List(TreeNode<T>* pTreeRoot/*树的根节点*/, TreeNode<T>*& pListHead/*双向链表的头指针*/, TreeNode<T>*& pListLast/*双向链表的尾指针*/)
12 {
13     if(pTreeRoot == NULL)
14     {
15         return;
16     }
17
18     // 中序遍历左子树
19     ConvertBSTree2List(pTreeRoot->pLChild, pListHead, pListLast);
20
21     // 处理当前节点,把节点链到双向链表尾部
22
23     // 修改当前节点左指针,指向双向链表尾部
24     pTreeRoot->pLChild = pListLast;
25     if(pListLast)        // 非第一个节点
26     {
27         pListLast->pRChild = pTreeRoot;
28     }
29     else                // 第一个节点
30     {
31         pListHead = pTreeRoot;
32     }
33
34     pListLast = pTreeRoot;
35
36     // 中序遍历右子树
37     ConvertBSTree2List(pTreeRoot->pRChild, pListHead, pListLast);
38 }

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

时间: 08-03

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

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

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.把二元查找树转变成排序的双向链表

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

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

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

算法-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

【编程题目】二元树的深度

52.二元树的深度(树).题目:输入一棵二元树的根结点,求该树的深度.从根结点到叶结点依次经过的结点(含根.叶结点)形成树的一条路径,最长路径的长度为树的深度.例如:输入二元树: 10/ \6 14/ / \4 12 16输出该树的深度 3.二元树的结点定义如下:struct SBinaryTreeNode // a node of the binary tree{int m_nValue; // value of nodeSBinaryTreeNode *m_pLeft; // left ch

【编程题目】输入一个已经按升序排序过的数组和一个数字,在数组中查找两个数,使得它们的和正好是输入的那个数字。

第 14 题(数组):题目:输入一个已经按升序排序过的数组和一个数字,在数组中查找两个数,使得它们的和正好是输入的那个数字.要求时间复杂度是 O(n).如果有多对数字的和等于输入的数字,输出任意一对即可.例如输入数组 1.2.4.7.11.15 和数字 15.由于 4+11=15,因此输出 4 和 11. 要求时间是O(n)肯定就只能扫描一遍. 又有两个数字要找,那就只能一个从头向后找 一个从后向前找 初始把大值设为最后一个数, 小值设为第一个数,如果数字和大于和,则减小大数的数值, 反之增大小

将二叉搜索树转变成排序的双向链表

将二叉搜索树转变成排序的双向链表: 点击链接: http://blog.csdn.net/l_tudou/article/details/51753921