题目：输入一颗二叉搜索树, 将该二叉搜索树转换成一个排序的双向链表.
要求不能创建任何新的结点, 只能调整数中结点的指针的指向.
方法: 使用中序遍历每一个结点, 并进行连接, 即左子树指前, 右子树指后, 并保存前一个节点.
本程序包含算法原理, 测试程序, 及 输出.
/*
* main.cpp
*
* Created on: 2014.6.12
* Author: Spike
*/
/*eclipse cdt, gcc 4.8.1*/
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
struct BinaryTreeNode {
int value;
BinaryTreeNode* left;
BinaryTreeNode* right;
};
void printTree (BinaryTreeNode* tree)
{
BinaryTreeNode* node = tree;
std::queue<BinaryTreeNode*> temp1;
std::queue<BinaryTreeNode*> temp2;
temp1.push(node);
while (!temp1.empty())
{
node = temp1.front();
if (node->left != NULL) {
temp2.push(node->left);
}
if (node->right != NULL) {
temp2.push(node->right);
}
temp1.pop();
std::cout << node->value << " ";
if (temp1.empty())
{
std::cout << std::endl;
temp1 = temp2;
std::queue<BinaryTreeNode*> empty;
std::swap(temp2, empty);
}
}
}
BinaryTreeNode* buildTree (const std::vector<int>& L)
{
if (L.empty())
return nullptr;
std::queue<BinaryTreeNode*> parentQueue;
std::queue<BinaryTreeNode*> childQueue;
BinaryTreeNode* root = new BinaryTreeNode();
root->value = L[0];
parentQueue.push(root);
std::size_t times = 1;
while (times < L.size())
{
BinaryTreeNode* parent = parentQueue.front();
parentQueue.pop();
BinaryTreeNode* lchild = new BinaryTreeNode();
lchild->value = L[times];
lchild->left = nullptr;
lchild->right = nullptr;
++times;
parent->left = lchild;
childQueue.push(lchild);
if (times == L.size()) break;
BinaryTreeNode* rchild = new BinaryTreeNode();
rchild->value = L[times];
rchild->left = nullptr;
rchild->right = nullptr;
++times;
parent->right = rchild;
childQueue.push(rchild);
if (parentQueue.empty()) {
parentQueue = childQueue;
std::queue<BinaryTreeNode*> empty;
std::swap(childQueue, empty);
}
}
return root;
}
void printList (BinaryTreeNode* pHeadOfList)
{
while (pHeadOfList != NULL && pHeadOfList->right != NULL)
{
std::cout << pHeadOfList->value << " ";
pHeadOfList = pHeadOfList->right;
}
std::cout << pHeadOfList->value << " ";
std::cout << std::endl;
return;
}
void ConvertNode(BinaryTreeNode* root, BinaryTreeNode*& pLast)
{
if (root == NULL)
return;
BinaryTreeNode* current = root;
if (current->left != NULL)
ConvertNode(current->left, pLast);
current->left = pLast;
if (pLast != NULL)
pLast->right = current;
pLast = current;
if (current->right != NULL)
ConvertNode(current->right, pLast);
}
BinaryTreeNode* Convert(BinaryTreeNode* root)
{
BinaryTreeNode* pLast = NULL;
ConvertNode(root, pLast);
BinaryTreeNode* head = pLast;
while (head != NULL && head->left != NULL)
head = head->left;
return head;
}
int main (void)
{
std::vector<int> L = {10, 6, 14, 4, 8, 12, 16};
BinaryTreeNode* tree = buildTree(L);
std::cout << "----Tree:----\n";
printTree(tree);
BinaryTreeNode* list = Convert(tree);
std::cout << "----List:----\n";
printList(list);
return 0;
}
输出:
----Tree:----
10
6 14
4 8 12 16
----List:----
4 6 8 10 12 14 16
