【问题描述】

编写程序在不增加结点的情况下，将二叉排序树转换成有序双向链表（如下图）。

链表创建结束后，按照从前往后的顺序输出链表中结点的内容。

【输入输出】

【输入形式】

第一行输入数字n，第二行输入n个整数。

【输出形式】

按照从后往前的顺序输出链表中的结点内容。

【样例输入】

6 63 55 90 58 98 70

【样例输出】

Convert binary sort tree into linked list...

55 58 63 70 90 98

【代码】

多加了个逆序输出链表内容……

#include<iostream>
using namespace std;
const int MAX = 1000;
struct BiNode {
	int data;
	BiNode* lchild, * rchild;
};

class BiSortTree {
private:
	BiNode* root;  //指向根结点的头指针
	BiNode* rear;  //指向尾结点的指针
	//BiNode  *pre;   //---指向当前访问的结点的前序节点
public:
	BiSortTree(int array[], int arrayLength);  //构造函数，建立一棵二叉树
	~BiSortTree();          //---
	void convertBiToLink(); //---二叉排序树转换成双向链表
	void DisplayLink();     //---显示双向链表
	void ReverseDisplayLink(); //---逆序显示
	void release(BiNode* bt);
private:
	void insertBST(BiNode*& bt, BiNode *key);
	void convert(BiNode* bt); //---二叉排序树转换成双向链表的递归程序
};
BiSortTree::BiSortTree(int array[], int arrayLength)
{
	root = NULL;  
	for (int i = 0; i < arrayLength; i++)
	{
		BiNode* p = new BiNode;
		p->lchild = p->rchild = NULL;
		p->data = array[i];
		insertBST(root, p);
	}
}
BiSortTree::~BiSortTree()
{
	release(root);
}
void BiSortTree::release(BiNode* bt)
{
	if (bt != NULL)
	{
		release(bt->lchild);
		release(bt->rchild);
		delete bt;
		bt = NULL;
	}
}
// 插入节点
void BiSortTree::insertBST(BiNode*& bt, BiNode *key)
{
	if (bt == NULL)
	{
		bt = new BiNode;
		bt->data = key->data;
		bt->lchild = NULL;
		bt->rchild = NULL;
	}
	else
	{
		if (key->data < bt->data)
			insertBST(bt->lchild, key);
		else if (key->data > bt->data)
			insertBST(bt->rchild, key);
	}
}

/*二叉排序树转换成双向链表

二叉排序树的递归定义是：
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树；

实现思路：
1.二叉排序树的特点就是一个结点的左子树比它小，右子树比它大，所以可以根据中序遍历得到一棵排序的序列。
2.由于不能创建新结点，那么我们只能去修改原始二叉树的指针。
  这里我们让指向左子树的指针变为链表中指向前序结点的指针，而指向右子树的指针变为链表中指向后一个结点的指针。

*/
void BiSortTree::convertBiToLink()
{
	if (root == NULL)
		return;
	else
	{
		convert(root);
		//将root指向链表的头部
		while (root->lchild) //root从当前位置出发，向其左孩子移动，直到左孩子为空，到达头部
		{
			root = root->lchild;
		}
	}
}
//二叉树转换成双向链表，采用中序遍历，当访问根节点的时候实现转换
void BiSortTree::convert(BiNode* bt)
{
	static BiNode* pre = NULL;  //指向当前访问节点的前序结点
	if (bt == NULL)
	{
		return;
	}
	else
	{
		convert(bt->lchild);  //访问左子树
		//访问根节点
		if (pre == NULL) // 如果是链表的第一个节点
		{
			root = bt; // 设置链表的头部
		}
		else
		{
			pre->rchild = bt; // 将前一个节点的右指针指向当前节点
			bt->lchild = pre; // 将当前节点的左指针指向前一个节点
		}
		pre = bt;           // 当前根节点变成前序结点
		convert(bt->rchild);  // 访问右子树
	}
}
//正序输出二叉排序树链表
void BiSortTree::DisplayLink()
{
	BiNode* p;
	p = root;
	while (p)
	{
		cout << p->data << " ";
		p = p->rchild;
	}
	cout << endl;
}
//逆序输出二叉排序树链表
void BiSortTree::ReverseDisplayLink()
{
	if (root == NULL) 
		return; // 如果链表为空，直接返回
	BiNode* p = root;
	// 找到链表的最后一个节点
	while (p->rchild)
	{
		p = p->rchild;
	}
	// 逆序输出
	while (p)
	{
		cout << p->data << " ";
		BiNode* temp = p->lchild;
		delete p; // 释放节点以避免内存泄漏
		p = temp;
	}
	root = NULL; // 清空链表头部指针
	rear = NULL; // 清空链表尾部指针
}
int main()
{
	int n;
	cin >> n;
	int array[MAX] = { 0 };
	for (int i = 0; i < n; i++)
	{
		cin >> array[i];
	}
	cout << "Convert binary sort tree into linked list..." << endl;
	BiSortTree BSTLink(array, n);
	BSTLink.convertBiToLink();
	BSTLink.DisplayLink();

	cout << "Reverse display link...\n";
	BSTLink.ReverseDisplayLink();
	return 0;
}