数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++二叉树中叶节点的成对交换
给定一棵二叉树。任务是成对交换叶节点，例如：
输入：
输出：
我们将跟踪指向两个相邻叶节点的两个指针，并在给定问题中交换它们的值。
寻找解决方案的方法
在这种方法中，我们遍历树，找到叶节点，并跟踪计数器以检查当前计数。主要的技巧是我们的计数器是奇数，所以我们的第一个指针现在指向该节点。当我们的计数器变为偶数时，我们交换数据，因此我们的叶节点被交换。
示例
上述方法的C++代码
#include <bits/stdc++.h>
using namespace std;
struct Node{ // structure of our tree node
int data;
struct Node *left, *right;
};
void Swap(Node **a, Node **b){ // the swapping utility function
Node * temp = *a;
*a = *b;
*b = temp;
}
/********Pointers for leaf nodes for swapping********/
Node **firstleaf;
Node **secondleaf;
void SwapTheLeafNodes(Node **root, int &count){//recursive function for
//Swapping leaf nodes
if (!(*root)) // if root is null we return
return;
if(!(*root)->left &&!(*root)->right){ // condition for leaf node
secondleaf = root; // now we firstly make our second pointer point to this node
count++; // we also increment the count
if (count%2 == 0) // now if our count is even that means we have a pair so we can swap them
Swap(firstleaf, secondleaf);
else // if count is odd so that means we only got first node yet
firstleaf = secondleaf;
}
if ((*root)->left)
SwapTheLeafNodes(&(*root)->left, count);
if ((*root)->right)
SwapTheLeafNodes(&(*root)->right, count);
}
Node* newNode(int data){ // function for initializing new node
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
void printInorder(Node* node){ // inorder traversal function
if (node == NULL)
return;
printInorder(node->left);
printf("%d ", node->data);
printInorder(node->right);
}
int main(){
/* Creating binary tree*/
Node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->right->left = newNode(5);
root->right->right = newNode(8);
root->right->left->left = newNode(6);
root->right->left->right = newNode(7);
root->right->right->left = newNode(9);
root->right->right->right = newNode(10);
cout << "Inorder traversal before swap:\n";
printInorder(root);
cout << "\n";
int count = 0; // out counter for keeping track of leaf nodes
SwapTheLeafNodes(&root, count); // swapping the nodes
cout << "Inorder traversal after swap:\n";
printInorder(root);
cout << "\n";
return 0;
}输出
Inorder traversal before swap: 4 2 1 6 5 7 3 9 8 10 Inorder traversal after swap: 6 2 1 4 5 9 3 7 8 10
上述代码的解释
在上述方法中，我们只是创建了两个指针，它们将跟踪我们的叶节点。当我们遇到叶节点时，我们遍历树。我们首先使我们的第二个指针指向该节点，现在我们增加一个计数变量，如果我们的计数是偶数，那么我们交换节点，如果计数是奇数，那么这意味着我们只找到了我们对的第一个元素，所以我们将该值存储在第一个指针中，这就是我们的函数的工作方式。
结论
在本教程中，我们解决了二叉树中成对交换叶节点的问题。我们还学习了这个问题的C++程序以及我们解决这个问题的完整方法（普通和高效）。我们可以用C、Java、Python和其他语言编写相同的程序。我们希望您觉得本教程有所帮助。
更新于：2021年11月25日
247 次浏览
广告