資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
