一、问题描述
创新互联成立于2013年，是专业互联网技术服务公司，拥有项目
成都网站制作、成都网站设计网站策划，项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命，1280元镇平做网站,已为上家服务,为镇平各地企业和个人服务,联系电话:18982081108
输入一棵二叉搜索树，现在要将该二叉搜索树转换成一个排序的双向链表。而且在转换的过程中，不能创建任何新的结点，只能调整树中的结点指针的指向来实现。
二、实现思路
在二叉搜索树中，每个结点都有两个分别指向其左、右子树的指针，左子树结点的值总是小于父结点的值，右子树结点的值总是大于父结点的值。而在双向链表中，每个结点也有两个指针，它们分别指向前一个结点和后一个结点。所以这两种数据结构的结点是一致，二叉搜索树之所以为二叉搜索树，双向链表之所以为双向链表，只是因为两个指针的指向不同而已
思路：在转换成排序双向链表时，原先指向左子结点的指针调整为链表中指向前一个结点的指针，原先指向右子结点的指针调整为链表中指向下一个结点的指针。对于树的操作，通常是在遍历树的各个结点的过程中，通过对结点实施某些操作来完成的，这个算法也不例外。由于要求转换后的双向链表也是有序的，而我们从上面也可以看到，当我们以中序遍历二叉搜索树时，其遍历的结点就是有序的，所以在这里采用的遍历顺序应该是中序。
//递归
#include
#include
using namespace std;
struct BinaryTreeNode
{
int data;
BinaryTreeNode* left;
BinaryTreeNode* right;
BinaryTreeNode(int x)
:data(x)
, left(NULL)
, right(NULL)
{}
};
class BinaryTree
{
protected:
BinaryTreeNode* _root;
BinaryTreeNode* _CreateBinaryTree(int* arr, int& index, int size)
{
BinaryTreeNode* root = NULL;
if (index < size&&arr[index] != '#')
{
root = new BinaryTreeNode(arr[index]);
root->left = _CreateBinaryTree(arr, ++index, size);
root->right = _CreateBinaryTree(arr, ++index, size);
}
return root;
}
void _Clear(BinaryTreeNode* root)
{
if (root == NULL)
return;
_Clear(root->left);
_Clear(root->right);
delete root;
}
void _Convert(BinaryTreeNode* root, BinaryTreeNode** head)//有可能改变head,加引用
{
if (root == NULL)
return;
BinaryTreeNode* cur = root;
if (cur->left)
_Convert(root->left, head);
cur->left = *head;
if (*head)
(*head)->right = cur;
*head = cur;
if (cur->right)
_Convert(cur->right, head);
}
//打印并销毁双向链表
private:
static void PrintList(BinaryTreeNode* head)
{
if (head == NULL)
return;
BinaryTreeNode* cur = head;
while (cur)
{
cout << cur->data << " ";
if (cur->left)
cout << "prev" << cur->left->data << " ";
if (cur->right)
cout << "next" << cur->right->data << endl;
cur = cur->right;
}
}
static void Destroy(BinaryTreeNode** head)
{
BinaryTreeNode* cur = *head;
BinaryTreeNode* del = NULL;
while (cur)
{
del = cur;
cur = cur->right;
delete del;
}
head = NULL;
}
public:
BinaryTree()
:_root(NULL)
{}
~BinaryTree()
{
_Clear(_root);
}
BinaryTree(int *arr, int size)
{
int index = 0;
_root = _CreateBinaryTree(arr, index, size);
}
void PreOrder_Non()
{
if (_root == NULL)
return;
BinaryTreeNode* cur = _root;
stack s;
s.push(_root);
while (!s.empty())
{
cur = s.top();
printf("%d ", cur->data);
s.pop();
if (cur->right)
s.push(cur->right);
if (cur->left)
s.push(cur->left);
}
}
BinaryTreeNode* TransformList()
{
if (_root == NULL)
return NULL;//返回匿名对象
//应按后序遍历顺序
BinaryTreeNode* ret = NULL;
_Convert(_root, &ret);
while (ret != NULL&&ret->left != NULL)
ret = ret->left;
_root = NULL;
PrintList(ret);
Destroy(&ret);
}
};
void Test1()
{
int arr[] = { 10, 6, 4, '#', '#', 8, '#', '#', 14, 12, '#', '#', 16 };
BinaryTree bt1(arr, sizeof(arr) / sizeof(arr[0]));
bt1.PreOrder_Non();
BinaryTreeNode* head = bt1.TransformList();
}
//非递归
TreeNode * transfer(TreeNode * root)
{
// left will be used as previous pointer (point to a little one);
// right will be used as post pointer (point to a large one);
if (!root) return NULL;
Stack *s = new Stack();
TreeNode *curr, *head, *tail;
curr = root;
head = NULL, tail=NULL;
while(true) {
while(curr)
{
s->push(curr);
curr = curr->left;
}
if(s->isEmpty()) break;
curr = s->pop();
//visit(curr);
//将curr节点加入到双向链表末尾
if ( head==NULL)
{ //curr是链表中的第一个节点。
head = curr;
tail = curr;
}
else
{
tail->right = curr;
curr->left = tail;
tail = curr; //注意此处不能够修改tail->right指针的值，到目前为止，
//当前节点的右子树还未被访问。
}
while(!curr->right)
{
if(s->isEmpty()) break;
curr = s->pop();
//visit(curr);
//
if ( head==NULL)
{
head = curr;
tail = curr;
}
else
{
tail->right = curr;
curr->left = tail;
tail = curr;
}
}
if (curr->right)
curr = curr->right;
else break;
}
head->left = NULL;
tail->right = NULL;
delete s;
return head;
}
我们有一个变量head用来记录转换了的链表末结点，由于在惯例中，我们会返回链表的第1个结点（从1开始计数）的指针，而head指向的却是末结点，我们可以通过该指针来从尾走到头来获取第一个结点的指针，但是在这里我却没有这样做，因为它需要对每个结点都遍历一次，时间复杂度为O（n）。而是在变换前，找到二叉排序树的最左结点的指针。因为排序二叉树是有序的，最左的结点即为最小的结点，而我们的算法也不会删除或新增结点，也就是说结点的地址是不会改变的，所以最左的结点就是转换后的链表的第1个结点，其时间复杂度为O（logN）。
该算法首先从根要点一直向左走，找到最左边的结点，其时间复杂度为O(logN)，然后对二叉排序树中的每个结点遍历一次，进行指针变换，其时间复杂度为O(N)，所以总的时间复杂度为O(N)。
至于空间复杂度，由于ConvertNode函数进行递归调用，其函数有两个开参，而函数栈中的函数调用层数不会超过树高，所以其空间复杂度为O(logN)。
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
当前名称：输入一棵二叉搜索树，现在要将该二叉搜索树转换成一个排序的双向链表。-创新互联
网页地址：
http://cxhlcq.com/article/cdchdh.html
重庆分公司
重庆分公司
