二叉树左右子树的交换并显示（C++实现）

文章目录

一、功能介绍
二、代码分析
三、完整代码

一、功能介绍

1、将指定结点的左右子树进行交换（默认为根结点）

2、从根结点开始将所有结点的左右子树进行交换

二、代码分析

1、二叉树结点结构

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(N²)≥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(N²),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为二叉树的高度，由于使用的是递归函数进行交换，而递归函数需要栈空间，栈空间取决于递归深度，即空间复杂度等于高度

5、显示二叉树

// 显示二叉树 
// 按数目输出空格 
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;
	}

// 第二步:输出 
// ①桉树的完整结构存入数组 
 
// 结果不太好,有时缺东少西的

// ②偏移值 
    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;
	}

// 第二步:输出 
// ①桉树的完整结构存入数组 
 
// 结果不太好,有时缺东少西的

// ②偏移值 
    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;
		}
	} 
}

感谢观看。

二叉树左右子树的交换并显示（C++实现）

C/C++/C#相关栏目本月热门文章