二叉搜索树 与 双向链表 代码(C++)

题目：输入一颗二叉搜索树, 将该二叉搜索树转换成一个排序的双向链表.

要求不能创建任何新的结点, 只能调整数中结点的指针的指向.

方法: 使用中序遍历每一个结点, 并进行连接, 即左子树指前, 右子树指后, 并保存前一个节点.

本程序包含算法原理, 测试程序, 及 输出.

/*

* 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