数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究用 C++ 从给定的中序遍历构建特殊的二叉树
给定一个数组 arr[]，其中包含二叉树的中序遍历。目标是从该数组构建一个特殊的二叉树。特殊的二叉树是指其根节点的权重大于其左右子节点的权重。
例如
输入
int arr[] = {10, 20, 28, 40, 32, 31, 30}输出
使用给定的中序遍历构建的特殊二叉树如下所示：
解释
we are given with an array of integer values or the inorder traversal of a tree. So, the special tree formed is 10, 20, 28, 40, 32, 31, 30
输入
int arr[] = {10, 20, 25, 28, 40, 32, 31, 30, 35}输出
The special binary tree which will be constructed with the given inorder traversal is given below −
解释
we are given with an array of integer values or the inorder traversal of a tree. So, the special tree formed is 10, 20, 25, 28, 40, 32, 31, 30, 35.
**下面程序中使用的方案如下：**
在此方案中，我们将从给定数组中提取最大元素作为根节点，构建特殊的二叉树。该元素左侧的元素将成为左子树的一部分，右侧的元素将成为右子树的一部分。此过程递归执行以构建树。
将 arr[] 作为包含中序遍历的输入数组。
函数 new_node (int data) 创建一个左、右子节点均为 NULL 的节点。
函数 total(int arr[], int first, int last) 返回该元素的索引。
取 highest = arr[first] 和 lowest = first。
从 first+1 索引遍历到 last，如果发现任何元素 arr[i] 大于 highest，则将它的索引存储在 lowest 中并更新 highest。
在 for 循环结束时，lowest 将包含最高元素的索引。
函数 create_tree (int arr[], int first, int last) 递归地从 arr[] 构建特殊的二叉树。
如果 first>last，则返回 NULL，因为树将无法构建。
使用 temp = total(arr, first, last) 将 temp 作为数组的最大值。
创建一个数据为 temp 的节点，并为树的根节点创建一个指向它的指针 parent。
如果 first==last，则树将只有一个节点。返回 parent。
递归计算 parent->left = create_tree(arr, first, temp − 1);
以及 parent−>right = create_tree(arr, temp + 1, last)。
最后返回 parent。
函数 Inorder_traversal(tree_node* node) 打印上面生成的树的中序遍历。
如果节点为 NULL，则不返回任何内容。否则，首先使用 Inorder_traversal(node−>left) 打印左子树。
然后打印当前节点。
然后使用 Inorder_traversal (node−>right) 打印右子树。
示例
#include <bits/stdc++.h>
using namespace std;
int total(int arr[], int first, int last);
class tree_node{
public:
int data;
tree_node* left;
tree_node* right;
};
tree_node* new_node(int data);
tree_node* create_tree (int arr[], int first, int last){
if(first > last){
return NULL;
}
int temp = total(arr, first, last);
tree_node *parent = new_node(arr[temp]);
if(first == last){
return parent;
}
parent−>left = create_tree(arr, first, temp − 1);
parent−>right = create_tree(arr, temp + 1, last);
return parent;
}
int total(int arr[], int first, int last){
int highest = arr[first];
int lowest = first;
for(int i = first + 1; i <= last; i++){
if(arr[i] > highest){
highest = arr[i];
lowest = i;
}
}
return lowest;
}
tree_node* new_node (int data){
tree_node* newNode = new tree_node();
newNode−>data = data;
newNode−>left = NULL;
newNode−>right = NULL;
return newNode;
}
void Inorder_traversal(tree_node* node){
if (node == NULL){
return;
}
Inorder_traversal(node−>left);
cout<<node−>data<<" ";
Inorder_traversal (node−>right);
}
int main(){
int arr[] = {10, 20, 28, 40, 32, 31, 30};
int size = sizeof(arr)/sizeof(arr[0]);
tree_node *root = create_tree(arr, 0, size − 1);
cout<<"Construct Special Binary Tree from given Inorder traversal are: "<<"\n";
Inorder_traversal(root);
return 0;
}输出
如果我们运行以上代码，它将生成以下输出：
Construct Special Binary Tree from given Inorder traversal are: 10, 20, 28, 40, 32, 31, 30
387 次浏览
