二叉树左右子树的交换并显示（C++实现）
时间：2022-11-02 01:30:00
文章目录
- 一、功能介绍
- 二、代码分析
- 三、完整代码
一、功能介绍
1.交换指定结点的左右子树(默认为根点)
2、从根结点开始将所有结点的左右子树进行交换
二、代码分析
二叉树结点结构
struct BinaryTree { char data; struct BinaryTree *left, *right; };使用char作为存储在二叉树结点的数据类型，左右子树都使用二叉树结点的指针。
2.随机生成数据
// 随机生成数据部分(范围大小写英文字母和 0~9 的 10 个数字) char randomChar() { char data = rand() % 128; if (!(data >= '0' && data <= '9' || data >= 'A' && data <= 'Z' || data >= 'a' && data <= 'z')) { return randomChar(); } else return data; } // 二叉树成二叉树 int nodeNumber = 0; BinaryTree* randomCreate() { char x = randomChar(); // cout << x << endl; BinaryTree *node; node = (BinaryTree*)malloc(sizeof(BinaryTree)); node->data = x; // 左右子树是空的还是存在的，按概率随机生成，至少生成 3 有数据的结 点以及总共 5 个结点 if ( nodeNumber <= 5) { int y = randomChar(); // 1/6 概率生成只是右孩子的结点 // 1/6 概率生成只是左孩子的结点 // 前 3 次 2/3 孩子左右孩子有结点的概率 // 后 n 次 1/3 孩子左右孩子有结点的概率 // 后 n 次 1/3 产生子叶结点的概率 if (y % 6 == 0) { node->left = NULL; node->right = randomCreate(); } else if (y % 6 == 1) { node->left = randomCreate(); node->right = NULL; } else if (y % 6 == 2 || y % 6 == 3) { node->left = randomCreate(); node->right = randomCreate(); } else { if (nodeNumber <= 3) { node->left = randomCreate(); node->right = randomCreate(); } else { node->left = NULL; node->right = NULL; } } } else { // 防止左右儿童未初始化的情况 node->left = NULL; node->right = NULL; } return node; }利用迭代生成二叉树的每个结点，
时间复杂：O(N2)≥O(N),N为设定生成的结点数
空间复杂：O(N)
3.二叉树左右子树简单交换
// 交换整个子树 void childChange_simple(BinaryTree *parent) { if (parent == NULL) { return; } else { BinaryTree *mid; mid = parent->left; parent->left = parent->right; parent->right = mid; return; }// 只是左右子树的整体交换，它内部的左右没有交换 }由于左右子树交换简单，左右子树内部结构没有改变，交换操作时只交换需要交换的左右子树。
若左右子树交换根结点：
时间复杂：O(1)
空间复杂：O(1)
若交换指定结点的左右子树，则需配合搜索函数：
时间复杂：O(N2),N现有结点的数量
空间复杂：O(N 1)
4.二叉树左右子树迭代交换
// 树内每个左右结点都交换 void childChange_iteration(BinaryTree *parent) { if (parent == NULL) { return; } else { BinaryTree *mid = parent->left; parent->left = parent->right; parent->right = mid; childChange_iteration(parent->left); childChange_iteration(parent->right); return; }// 用迭代交换左右子树及其内部的左右结点 }由于递归函数依次交换指定结点的左右子树，因此：
时间复杂：O(N)，N现有结点的数量
空间复杂：O(H)，H对于二叉树的高度，由于使用递归函数交换，递归函数需要栈空间，栈空间取决于递归深度，即空间复杂度等于高度
显示二叉树
// 显示二叉树 // 按数量输出空间 void Space(int number) { for (int i = 0; i < number; i ) { cout << ' '; } } // 输出 void printBinaryTree(BinaryTree *root) { // 第一步:按照树的结构顺序将数据存储在二维数组中 int deep = getDeep(root); int length = (int)pow(2, deep - 1); char Btree[deep][length]; int width, row = 1; Btree[0][0] = root->data; Btree[0][length - 1] = ' '; queue BTreeQueue; BTreeQueue.push(root); while (!BTreeQueue.empty()) { width = BTreeQueue.size(); // 将数据存储在二维数组中，如果空，则使用 NullNode 取代空的结点， | 代 替空的数据 // 以行数作为终止循环的标志 for (int col = 0; col < width; col ) { BinaryTree* mid = BTreeQueue.front(); BTreeQueue.pop(); if (mid->left != NULL) { BTreeQueue.push(mid->left); Btree[row][2 * col] = mid->left->data; } else { BTreeQueue.push(NullNode); Btree[row][2 * col] = '|'; } if (mid->right != NULL) { BTreeQueue.push(mid->right); Btree[row][2 * col 1] = mid->right->data; } else { BTreeQueue.push(NullNode); Btree[row][2 * col 1] = '|'; } } row ; if (row >= deep) break; } // 参考数据输出(简单输出) for (int i = 0; i < deep; i ) { for (int j = 0; j < (int)pow(2, i); j ) { cout << Btree[i][j] << " "; } cout << endl; } // 第二步：输出 // ①桉树的完整结构存储在数组中 /* char displayBtree[deep * 2][length]; for (int i = 0; i < deep * 2; i ) for (int j = 0; j < length; j ) displayBtree[i][j] = '\u0020'; for (int i = 0; i < deep; i ) { int flag = 0; for (int j = 0; j < (int)pow(2, i); j ) { if (i != 0) { displayBtree[2 * i - 1][flag (length / (i 2)) - 1] = Btree[i][j] != 0) { displayBtree[2 * i - 1][flag (length / (i 2)) - 1] = Btree[i][j] != '|' ? (j % 2 == 0 ? '/' : '\\') : ' '; } displayBtree[2 * i][flag (length / (i 2)) - 1] = Btree[i][j] != '|' ? Btree[i][j] : ' '; flag = (length / (i 2)) - 1; } } for (int i = 0; i < deep * 2; i ) { for (int j = 0; j < length; j ) cout <&t; displayBtree[i][j];
cout << endl;
}
*/
// 结果不太好,有时缺东少西的
// ②偏移值
int ScreenWidth = length * 2 + 2;
int parentPot = ScreenWidth / 2, offset;
// 根结点
Space(parentPot);
cout << Btree[0][0] << endl;
// 子树
for (int i = 1; i < deep; i ++) {
if (parentPot != 1) {
offset = parentPot / 2;
}
else
offset = parentPot;
// 斜线
for (int j = 0; j < (int)pow(2, i); j ++) {
Space(offset - 1);
if (j % 2 == 0) {
Space(1);
cout << ((Btree[i][j] != '|') ? '/' : ' ');
Space(offset - 1);
} else {
cout << ((Btree[i][j] != '|') ? '\\' : ' ');
Space(offset);
}
}
cout << endl;
// 数据
for (int j = 0; j < (int)pow(2, i); j ++) {
Space(offset - 1);
if (j % 2 == 0) {
Space(1);
cout << ((Btree[i][j] != '|') ? Btree[i][j] : ' ');
Space(offset - 1);
} else {
cout << ((Btree[i][j] != '|') ? Btree[i][j] : ' ');
Space(offset);
}
}
cout << endl;
parentPot = offset;
}
// 效果可行,但是不太美观
} 首先将二叉树的数据按层储存，再显示二叉树。
在显示二叉树时，将二叉树的结构创建二维数组储存再输出，但是这样的输出显示有点问题，有时最后一层的结点不显示，或者中间某层的结点不显示，或者中间某层结点显示串行。后来查阅资料发现可以使用偏移量来确定左右孩子的显示。
采用偏移量显示时，首先要确定整个二叉树的最大宽度，根结点采用最大宽度的一半，偏移量采用父母结点之间的距离的一半，同层次结点之间的距离与最左边的父母结点到最右显示边界的距离一致，可以小于一半，但不能大于一半，这样会导致相邻两个父母结点的孩子结点产生显示冲突。
时间复杂度：≈O(4N)，N为现有结点的个数
空间复杂度：O(H*W)，H为二叉树的高度，W为二叉树对应的满二叉树的宽度。
三、完整代码
#include
using namespace std;
// 二叉树结点结构
struct BinaryTree {
char data;
struct BinaryTree *left, *right;
};
// 分隔字符串
string bias(30, '/');
// 空二叉树结点
BinaryTree *NullNode = (BinaryTree*)malloc(sizeof(BinaryTree));
// 人工输入二叉树
BinaryTree* inputNode() {
BinaryTree *node;
char x;
cin >> x;
if (x == '#') {
return NULL;
}
else {
node = (BinaryTree*)malloc(sizeof(BinaryTree));
//开创结点空间
node->data = x;
node->left = inputNode();
node->right = inputNode();
}
return node;
}
// 仅整个子树交换
void childChange_simple(BinaryTree *parent) {
if (parent == NULL) {
return;
}
else {
BinaryTree *mid;
mid = parent->left;
parent->left = parent->right;
parent->right = mid;
return;
}// 仅仅是左右子树的整体交换,并没有将其内部的左右相互交换
}
// 子树内的每个左右结点都交换
void childChange_iteration(BinaryTree *parent) {
if (parent == NULL) {
return;
}
else {
BinaryTree *mid = parent->left;
parent->left = parent->right;
parent->right = mid;
childChange_iteration(parent->left);
childChange_iteration(parent->right);
return;
}// 利用迭代将左右子树以及其内部的左右结点都进行了交换
}
//遍历
// 1.前序:先输出根节点,再输出左子树,最后输出右子树
void NLR(BinaryTree *root) {
if (root) {
cout << root->data;
NLR(root->left);
NLR(root->right);
}
else {
cout << '#';
}
}
// 2.中序:先输出左子树,再输出根节点,最后输出右子树
void LNR(BinaryTree *root) {
if (root) {
NLR(root->left);
cout << root->data;
NLR(root->right);
} else
cout << '#';
}
// 3.后序:先输出左子树,再输出右子树,最后输出根节点
void LRN(BinaryTree *root) {
if (root) {
NLR(root->left);
NLR(root->right);
cout << root->data;
}
else {
cout << '#';
}
}
// 求深度
int getDeep(BinaryTree *root) {
// 结点为空,则深度为 0
if (root == NULL) {
return 0;
}
// 结点不为空,则把该结点的一点深度加上其左右结点的深度
else {
return 1 + max(getDeep(root->left), getDeep(root->right));
}
}
// 求宽度
int getWidth(BinaryTree *root) {
// 结点为空,则宽度为 0
if (root == NULL) {
return 0;
}
// 节点不为空
else {
int maxWidth = 0, width;
queue btq;
btq.push(root);
// 利用队列按顺序计算每行的宽度
while (!btq.empty()) {
width = btq.size();
// 记录每行的宽度
maxWidth = max(maxWidth, width);
// 取行宽度的最大值
for (int i = 0; i < width; i ++) {
BinaryTree *mid = btq.front();
btq.pop();
if (mid->left != NULL) {
btq.push(mid->left);
}
if (mid->right != NULL) {
btq.push(mid->right);
}
}
// 除去一行已经计算过宽度的,换下一行继续计算宽度
}
return maxWidth;
}
}
// 求子叶个数
int getLeef(BinaryTree *root) {
if (root == NULL) {
return 0;
}
else if (root->left == NULL && root->right == NULL) {
return 1;
}
else {
return getLeef(root->left) + getLeef(root->right);
}
// 检查每个结点的左右子树是否存在,都不存在才为子叶
}
// 判断是否为满二叉树
bool judgeFull(BinaryTree *root) {
return getWidth(root) == (int)pow(2, getDeep(root) - 1);
/*由于满二叉树的定义--满二叉树的每行结点数都为最大值--可知,
最后一行一定为最后一行的最大值,若前面有某个结点的左右子树
为空,这必不可能形成满二叉树*/
}
// mode = 1 :查找 mode = 2 :删除结点为根的子树
vector search(BinaryTree *root, char data, int mode) {
vector res; // 存结果
queue TreeQueue; // 按每行的顺序查找
TreeQueue.push(root);
int width;
while (!TreeQueue.empty()) {
width = TreeQueue.size();
for (int i = 0; i < width; i ++) {
BinaryTree* mid = TreeQueue.front();
TreeQueue.pop();
// 查找
if (mode == 1) {
if (mid->left != NULL)
TreeQueue.push(mid->left);
if (mid->right != NULL)
TreeQueue.push(mid->right);
if (mid->data == data)
res.push_back(mid);
}
// 删除:找到即删,没找到则继续按行查找
else {
if (mid->left != NULL && mid->left->data == data) {
res.push_back(mid->left);
mid->left = NULL;
}
else if (mid->left != NULL) {
TreeQueue.push(mid->left);
}
if (mid->right != NULL && mid->right->data == data) {
res.push_back(mid->right);
mid->right = NULL;
}
else if (mid->right != NULL) {
TreeQueue.push(mid->right);
}
}
}
}
if (mode == 2 && root->data == data) {
res.push_back(root);
}
// 判断根节点是否符合查找的数据
return res;
}
// 随机生成数据部分(范围大小写英文字母以及 0~9 的 10 个数字)
char randomChar() {
char data = rand() % 128;
if (!(data >= '0' && data <= '9' || data >= 'A' && data <= 'Z' || data >= 'a' && data <= 'z')) {
return randomChar();
}
else
return data;
}
// 随机生成二叉树
int nodeNumber = 0;
BinaryTree* randomCreate() {
char x = randomChar();
// cout << x << endl;
BinaryTree *node;
node = (BinaryTree*)malloc(sizeof(BinaryTree));
node->data = x;
// 按概率随机生成左右子树是否为空或存在并生成至少 3 个有数据的结 点以及总共 5 个结点
if (++ nodeNumber <= 5) {
int y = randomChar();
// 1/6 的概率生成仅右孩子的结点
// 1/6 的概率生成仅左孩子的结点
// 前 3 次 2/3 的概率生成左右孩子都有的结点
// 后 n 次 1/3 的概率生成左右孩子都有的结点
// 后 n 次 1/3 的概率生成子叶结点
if (y % 6 == 0) {
node->left = NULL;
node->right = randomCreate();
} else if (y % 6 == 1) {
node->left = randomCreate();
node->right = NULL;
} else if (y % 6 == 2 || y % 6 == 3) {
node->left = randomCreate();
node->right = randomCreate();
} else {
if (nodeNumber <= 3) {
node->left = randomCreate();
node->right = randomCreate();
} else {
node->left = NULL;
node->right = NULL;
}
}
} else {
// 防止因为左右孩子都未初始化的情况
node->left = NULL;
node->right = NULL;
}
return node;
}
// 显示二叉树
// 按数目输出空格
void Space(int number) {
for (int i = 0; i < number; i ++) {
cout << ' ';
}
}
// 输出
void printBinaryTree(BinaryTree *root) {
// 第一步:将数据按树的结构顺序存入二维数组中
int deep = getDeep(root);
int length = (int)pow(2, deep - 1);
char Btree[deep][length];
int width, row = 1;
Btree[0][0] = root->data;
Btree[0][length - 1] = ' ';
queue BTreeQueue;
BTreeQueue.push(root);
while (!BTreeQueue.empty()) {
width = BTreeQueue.size();
// 将数据存入二维数组,若为空则用 NullNode 代替空的结点, | 代 替空的数据
// 并以行数作为终止循环的标志
for (int col = 0; col < width; col ++) {
BinaryTree* mid = BTreeQueue.front();
BTreeQueue.pop();
if (mid->left != NULL) {
BTreeQueue.push(mid->left);
Btree[row][2 * col] = mid->left->data;
} else {
BTreeQueue.push(NullNode);
Btree[row][2 * col] = '|';
}
if (mid->right != NULL) {
BTreeQueue.push(mid->right);
Btree[row][2 * col + 1] = mid->right->data;
} else {
BTreeQueue.push(NullNode);
Btree[row][2 * col + 1] = '|';
}
}
row ++;
if (row >= deep)
break;
}
// 参考数据输出(简易的输出)
for (int i = 0; i < deep; i ++) {
for (int j = 0; j < (int)pow(2, i); j ++) {
cout << Btree[i][j] << " ";
}
cout << endl;
}
// 第二步:输出
// ①桉树的完整结构存入数组
/*
char displayBtree[deep * 2][length];
for (int i = 0; i < deep * 2; i ++)
for (int j = 0; j < length; j ++)
displayBtree[i][j] = '\u0020';
for (int i = 0; i < deep; i ++)
{ int flag = 0;
for (int j = 0; j < (int)pow(2, i); j ++)
{ if (i != 0)
{ displayBtree[2 * i - 1][flag + (length / (i + 2)) - 1] = Btree[i][j] != '|' ? (j % 2 == 0 ? '/' : '\\') : ' ';
}
displayBtree[2 * i][flag + (length / (i + 2)) - 1] = Btree[i][j] != '|' ? Btree[i][j] : ' ';
flag += (length / (i + 2)) - 1;
}
}
for (int i = 0; i < deep * 2; i ++)
{
for (int j = 0; j < length; j ++)
cout << displayBtree[i][j];
cout << endl;
}
*/
// 结果不太好,有时缺东少西的
// ②偏移值
int ScreenWidth = length * 2 + 2;
int parentPot = ScreenWidth / 2, offset;
// 根结点
Space(parentPot);
cout << Btree[0][0] << endl;
// 子树
for (int i = 1; i < deep; i ++) {
if (parentPot != 1) {
offset = parentPot / 2;
}
else
offset = parentPot;
// 斜线
for (int j = 0; j < (int)pow(2, i); j ++) {
Space(offset - 1);
if (j % 2 == 0) {
Space(1);
cout << ((Btree[i][j] != '|') ? '/' : ' ');
Space(offset - 1);
} else {
cout << ((Btree[i][j] != '|') ? '\\' : ' ');
Space(offset);
}
}
cout << endl;
// 数据
for (int j = 0; j < (int)pow(2, i); j ++) {
Space(offset - 1);
if (j % 2 == 0) {
Space(1);
cout << ((Btree[i][j] != '|') ? Btree[i][j] : ' ');
Space(offset - 1);
} else {
cout << ((Btree[i][j] != '|') ? Btree[i][j] : ' ');
Space(offset);
}
}
cout << endl;
parentPot = offset;
}
// 效果可行,但是不太美观
}
// 整体删除并释放空间
int destory(BinaryTree *root) {
// 结点为空,则返回值 1
if (root == NULL)
return 1;
// 结点不为空,则返回值 0,且按行释放结点的空间
queue NodeQueue;
NodeQueue.push(root);
int width;
while (!NodeQueue.empty()) {
width = NodeQueue.size();
for (int i = 0; i < width; i ++) {
BinaryTree* mid = NodeQueue.front();
NodeQueue.pop();
if (mid->left != NULL)
NodeQueue.push(mid->left);
if (mid->right != NULL)
NodeQueue.push(mid->right);
free(mid);
}
}
return 0;
}
// 选项菜单
void menu() {
cout << " 二叉树的左右子树交换 " << endl
<< bias << endl
<< "1.随机生成二叉树" << endl
<< "2.手动输入二叉树" << endl
<< "3.简单的左右子树交换" << endl
<< "4.左右子树递归交换" << endl
<< "0.退出" << endl
<< bias << endl;
}
// 输出当前二叉树的相关信息
void DisplayInfo(BinaryTree *T) {
cout << endl << bias ;
cout << endl << "当前二叉树的前序遍历结果为:";
NLR(T);
cout << endl << "当前二叉数的中序遍历结果为:";
LNR(T);
cout << endl << "当前二叉树为:" << endl;
printBinaryTree(T);
cout << endl << bias << endl;
}
// 主函数
int main() {
// 随机生成数据初始化
srand((unsigned)time(0));
// 空结点初始化(全局变量)
NullNode->data = '|';
NullNode->left = NULL;
NullNode->right = NULL;
menu();
BinaryTree *T;
T = randomCreate();
DisplayInfo(T);
int n;
while(true) {
cout << endl << "请选择(9.显示菜单):";
cin >> n;
switch (n) {
case 0:
destory(T);
return 0;
case 1:
cout << "生成的二叉树如下:" << endl;
destory(T);
nodeNumber = 0;
T = randomCreate();
DisplayInfo(T);
break;
case 2:
cout << "请以前序的方式输入二叉树:" << endl;
destory(T);
T = inputNode();
DisplayInfo(T);
break;
case 3:
cout << "交换后的二叉树如下:" << endl;
childChange_simple(T);
DisplayInfo(T);
break;
case 4:
cout << "交换后的二叉树如下:" << endl;
childChange_iteration(T);
DisplayInfo(T);
break;
case 9:
menu();
break;
default:
cout << "输入错误!(序号介于 0~4 之间)" << endl;
break;
}
}
}
感谢观看。
