二叉树左右子树的交换并显示（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<BinaryTree*> BTreeQueue; 
	BTreeQueue.push(root); 
	while (!BTreeQueue.empty())

今天的文章二叉树左右子树的交换并显示（C++实现）分享到此就结束了，感谢您的阅读。