问题
现在有一颗二叉排序树,以二叉链表的形式存储
进行中序遍历可以得到从小到大的输出序列,现在要求对二叉排序树进行变换
使得其中序遍历序列为从大到小排列。
思路
- 先交换当前根结点左右子树的左右孩子结点
- 再交换当前根结点的左右孩子结点
C语言(关键代码)——使用了C++引用
void exChangeNode(BST& T) {
if (!T || (T->lchild == NULL && T->rchild == NULL))//如果根结点为空或根结点无左右子树,直接返回
{
return;
}
exChangeNode(T->lchild);//递归处理左子树
exChangeNode(T->rchild);//递归处理右子树
if (T->lchild != NULL || T->rchild != NULL)//交换当前根的左右孩子结点
{
BiNode* tempNode = T->lchild;
T->lchild = T->rchild;
T->rchild = tempNode;
}
}
完整代码
#include <stdio.h>
#include <stdlib.h>
typedef struct BiNode {
int data;
struct BiNode* lchild, * rchild;
}BiNode,*BST;
void insertBST(BST &T,int data){
if (!T)//如果根结点为空,就把当前结点当做根结点
{
T = (BST)calloc(1, sizeof(BiNode));
T->data = data;
}
if (T->data == data)
{
return;//如果当前结点的值等于要插入结点的值,插入失败
}
else if (T->data < data)
{
return insertBST(T->rchild, data);
}
else
{
return insertBST(T->lchild, data);
}
}
void creatBST(BST &T,int* datas, int len) {
T = NULL;
int i = 0;
while (i < len)
{
insertBST(T, datas[i++]);//将结点插入到二叉排序树中
}
}
void inOrder(BST T) {
if (T)
{
inOrder(T->lchild);
printf("%d ", T->data);
inOrder(T->rchild);
}
}
void exChangeNode(BST& T) {
if (!T || (T->lchild == NULL && T->rchild == NULL))//如果根结点为空或根结点无左右子树,直接返回
{
return;
}
exChangeNode(T->lchild);//递归处理左子树
exChangeNode(T->rchild);//递归处理右子树
if (T->lchild != NULL || T->rchild != NULL)//交换当前根的左右孩子结点
{
BiNode* tempNode = T->lchild;
T->lchild = T->rchild;
T->rchild = tempNode;
}
}
int main() {
BST root;
int n;//数据个数
scanf("%d", &n);
int* datas = (int*)malloc(sizeof(int) * n);
for (int i = 0; i < n; i++)
{
scanf("%d", &datas[i]);
}
creatBST(root,datas, n);//创建二叉排序树
printf("二叉排序树从小到大输出\n");
inOrder(root);//中序遍历二叉排序树(如果正确的话输出应该是从小到大的)
printf("\n");
//现在要将二叉排序树进行一个操作,让其中序遍历从大到小输出
//1.将根结点的左右子树的左右孩子交换
//2.交换根结点的左右孩子
printf("二叉排序树从大到小输出\n");
exChangeNode(root);
inOrder(root);
return 0;
}