C++ 可折叠二叉树

2024 年 8 月 28 日 | 阅读 6 分钟

在本文中，我们将介绍 C++ 中的可折叠二叉树。在 C++ 中，可折叠二叉树是一种树数据结构，其中每个节点的左右子树互为镜像。如果沿着树的中心折叠，**左子树**和**右子树**应具有相同的结构。在实现可折叠二叉树时，会迭代检查这种镜像对称性。如果节点的每个左右子节点重叠，则该树是可折叠的。C++ 中的递归算法可以实现此特性，这对于某些树操作至关重要。

我们可以使用不同的方法

通过切换到左子树的镜像来实现可折叠二叉树
通过确定左右子树是否为镜像图像来找到可折叠二叉树
使用广度优先搜索方法

1. 通过切换到左子树的镜像来实现可折叠二叉树

目标是将**左子树**转换为其镜像，然后将其与**右子树**进行比较。您可以按照以下步骤解决此问题

如果树为空，则返回 true。
接下来，将**左子树**转换为其镜像图像。
之后，检查并保存结果，如果左右子树的结构相同。
**`istheStructSame(root->left, root->right) = res. istheStructSame()`** 递归比较两个子树的结构，如果结构相同则返回 true。
撤消步骤 (2) 中所做的更改以恢复原始树。
最后，返回步骤 3 中存储的结果 **`res`**。

文件名：Is_foldable.cpp

//A C++ program to determine if a binary tree is foldable.
#include <bits/stdc++.h>
using namespace std;

/* A binary tree in which each node has data, a pointer to the left child, and a pointer to the right child */
class node {
public:
	int value;
	node* left;
	node* right;
};

// converts the given binary tree to a mirror image
void mirror_image(node* node);

// returns true if both trees are the same
bool istheStructSame(node* a1, node* b1);

/* function to determine if the tree is foldable or not*/
bool is_Foldable(node* root)
{
	bool result;

	//base condition
	if (root == NULL)
		return true;

	// left subtree is converted to a mirror image
	mirror_image(root->left);

	/* Comparing the structures of the right and left subtrees */
	result = istheStructSame(root->left, root->right);

	// to revert to the original tree
	mirror_image(root->left);

	return result;
}

bool istheStructSame(node* a1, node* b1)
{
	if (a1 == NULL && b1 == NULL) {
		return true;
	}
	if (a1 != NULL && b1 != NULL
		&& istheStructSame(a1->left, b1->left)
		&& istheStructSame(a1->right, b1->right)) {
		return true;
	}

	return false;
}

/* Modify a tree so that the left and right pointer roles are switched at each node.*/
void mirror_image(node* Node)
{
	if (Node == NULL)
		return;
	else {
		node* t;

		
		mirror_image(Node->left);
		mirror_image(Node->right);

		// pointer swapping
		t = Node->left;
		Node->left = Node->right;
		Node->right = t;
	}
}

/* Assists allocating a new node with the specified data and NULL right and left references. */
node* newNode(int value)
{
	node* Node = new node();
	Node->value = value;
	Node->left = NULL;
	Node->right = NULL;

	return (Node);
}

//main selection
int main(void)
{
	/* the structure of the binary tree
			1
		/ \
		9 7
		\ /
		6 8
	*/
	node* root = newNode(1);
	root->left = newNode(9);
	root->right = newNode(6);
	root->left->right = newNode(7);
	root->right->left = newNode(8);

	if (is_Foldable(root) == 1) {
		cout << "The given tree is foldable. ";
	}
	else {
		cout << "\nThe given tree is not foldable. ";
	}
	return 0;
}

输出

The given tree is foldable.

2. 通过确定左右子树是否为镜像图像来找到可折叠二叉树

目标是确定左右子树是否为镜像。您可以按照以下步骤解决此问题

如果树为空，则返回 true。
否则，检查左右子树的结构是否相似。使用实用函数 **`IsFoldable(root->left, root->right)`**。
检查 **`m1`** 和 **`m2`** 是否互为镜像。
如果两棵树都不为空，则返回 true。
如果一棵为空而另一棵不为空，则返回 **`false`**。
如果满足以下要求，则返回 true。
**`n1->left`** 是 **`n2->right`** 的镜像图像。
**`n1->right`** 是 **`n2->left`** 的镜像图像。

文件名：Is_foldable_mirror.cpp

#include <bits/stdc++.h>
using namespace std;

/* A binary tree in which each node has data, a pointer to the left child, and a pointer to the right child */
class node {
public:
	int value;
	node* left;
	node* right;
};

// returns true if both trees are the same
bool IsFoldabletree(node* n1, node* n2);

/* Returns true if the given tree can be folded */
bool Is_Foldable(node* root)
{
	if (root == NULL) {
		return true;
	}

	return IsFoldabletree(root->left, root->right);
}

/* A function that determines whether trees with roots m1 and m2 are mirror images of one other */
bool IsFoldabletree(node* m1, node* m2)
{
	/* if both left and right subtrees are null, then return tree*/
	if (m1 == NULL && m2 == NULL) {
		return true;
	}

 //If either of the trees is null, then return false
	if (m1 == NULL || m2 == NULL) {
		return false;
	}

/*If not, verify if the left and right subtrees are mirror images of each other */
	return IsFoldabletree(m1->left, m2->right)
		&& IsFoldabletree(m1->right, m2->left);
}
/* Assists allocating a new node with the specified data and NULL right and left references. */

node* newNode(int value)
{
	node* Node = new node();
	Node->value = value;
	Node->left = NULL;
	Node->right = NULL;

	return (Node);
}

int main(void)
{
	/* The structure of the binary tree
		1
		/ \
		6 7
		\ /
		8 9
	*/
	node* root = newNode(1);
	root->left = newNode(6);
	root->right = newNode(7);
	root->left->right = newNode(8);
	root->right->left = newNode(9);

	if (Is_Foldable(root) == true) {
		cout << "The given tree is foldable.";
	}
	else {
		cout << "The given tree is not foldable.";
	}

	return 0;
}

输出

The given tree is foldable.

3. 使用广度优先搜索方法

想法是使用 **`Queue`** 和 BFS 技术遍历树。您可以按照以下步骤解决此问题

**右子树**的右子节点是左子树的左子节点。它们中的每一个都应该是有效的。
右子树的左子节点等于左子树的右子节点。它们都应该为 null 或不为 null。

文件名：IsFoldableTree.cpp

#include <bits/stdc++.h>
using namespace std;
// Class Node for storing data as well as left and right
// pointers 
class Node
{
public:
	int data;
	Node *left;
	Node *right;

	Node(int data)
	{
		this->data = data;
		left = right = NULL;
	}
};

class IsFoldableTrees
{
public:
	Node *root = NULL;

	// function to find whether the tree is foldable or not
	bool isFoldableTree()
	{
		// for storing nodes
		queue<Node *> q1;

		//Adding the left and right nodes to the queue
		if (root != NULL)
		{
			q1.push(root->left);
			q1.push(root->right);
		}

		while (!q1.empty())
		{

			// Remove the first two nodes. 
			// Check for a null conditions. 
			Node *p1 = q1.front();
			q1.pop();
			Node *r1 = q1.front();
			q1.pop();

			// If both are null, continue and examine the subsequent elements
			if (p1 == NULL && r1 == NULL)
				continue;

			//If either of them is null return false
			if ((p1 == NULL && r1 != NULL) || (p1 != NULL && r1 == NULL))
				return false;

			/* Insert in the following order: 1. left of left subtree
			2. the right of the right subtree
			3.to the right of the left subtree
			4.left subtree of the right */
			q1.push(p1->left);
			q1.push(r1->right);
			q1.push(p1->right);
			q1.push(r1->left);
		}

		//If tree is foldable
		return true;
	}
};

int main()
{
	IsFoldableTrees tr = IsFoldableTrees();

	//Inserting data into the tree
	tr.root = new Node(1);
	tr.root->left = new Node(9);
	tr.root->right = new Node(10);
	tr.root->right->left = new Node(23);
	tr.root->left->right = new Node(45);

	// function calling
	if (tr.isFoldableTree())
		cout << "The given tree is foldable" << endl;
	else
		cout << "The given tree is not foldable" << endl;
}

输出

The given tree is foldable.

下一主题C++ 中字符串的字典序排名

C++ 可折叠二叉树

1. 通过切换到左子树的镜像来实现可折叠二叉树

2. 通过确定左右子树是否为镜像图像来找到可折叠二叉树

3. 使用广度优先搜索方法

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 可折叠二叉树

1. 通过切换到左子树的镜像来实现可折叠二叉树

2. 通过确定左右子树是否为镜像图像来找到可折叠二叉树

3. 使用广度优先搜索方法

相关帖子

在 C++ 中添加向量

C++ 函数对象

C++ 中达到给定 MEX 的最小增量

声明返回指向整型指针数组的指针的 C/C++ 函数

C++ 使用栈实现队列

C++ Unique_ptr

C++ 程序查找两个数组中和最小的 k 对

何时按引用或指针传递参数

C++ 程序检查矩阵是否正交

C++ multimap get_allocator() 函数

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器