資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學用C++構造其先序遍歷的完整k叉樹
給定一個數組arr[]，其中包含k叉樹的先序遍歷序列。目標是從該序列構造相同的k叉樹，並列印其後序遍歷。一個完整的k叉樹是指根節點有0個或k個子節點的樹，即最多k個子節點。
例如
輸入
int arr[] = {2, 5, 1, 3, 6, 7, 2, 1 }, int size = 8, int children = 2輸出
根據先序遍歷，構造的具有兩個子節點的完整k叉樹如下：
解釋
我們得到一個整數陣列，或者是一個具有k個子節點（k=2）的樹的先序遍歷。因此，生成的樹的後序遍歷為3 6 1 2 1 7 5 2，其構造規則是：先訪問所有左子樹節點，然後訪問所有右子樹節點，最後訪問根節點。
輸入
int arr[] = {2, 5, 1, 3, 6, 7, 2, 1 }, int size = 8, int children = 3輸出
根據先序遍歷，構造的具有三個子節點的完整k叉樹如下：
解釋
我們得到一個整數陣列，或者是一個具有k個子節點（k=3）的樹的先序遍歷。因此，生成的樹的後序遍歷為3 6 1 2 1 7 5 2，其構造規則是：先訪問所有左子樹節點，然後訪問所有右子樹節點，最後訪問根節點。
**下面程式中使用的方法如下：**
在這種方法中，我們將首先從給定陣列構造k叉樹，並將第一個元素作為根節點。如果左子樹為空，則右子樹也為空。遞迴呼叫左子樹和右子樹，並將它們連線起來。對於後序遍歷，我們先訪問左子樹，然後訪問右子樹，最後列印節點的值。
呼叫postorder(root->left)
呼叫postorder(root->right)
列印root->data
將arr[]作為包含先序遍歷的輸入陣列。
將k作為子節點數的變數。
將起始索引作為count=0。
使用Tree_Node* node = create_tree(arr, size, children, count)構造樹。
函式new_Node(int data)生成一個新的樹節點。
函式create_tree(int arr[], int N, int k, int height, int& count)從陣列arr[]生成k叉樹。
如果節點數<=0，則返回NULL，無法構造樹。
初始化newNode = new_Node(arr[count])，即arr[]的第一個元素。
如果(newNode == NULL)結果為真，則無法構造樹。
使用for迴圈遍歷arr[]，從i=0到i
如果(count < N - 1 && height > 1)，則為下一個索引遞增count，並使用newNode->root.push_back(create_tree(arr, N, k, height - 1, count))將此節點新增到樹中。
否則，透過推送NULL來結束樹，使用newNode->root.push_back(NULL);
最後返回指向節點的指標。
函式create_tree(int* arr, int N, int k, int count)返回樹的高度。
計算height= (int)ceil(log((double)N * (k - 1) + 1) / log((double)k));
在return語句中呼叫create_tree(arr, N, k, height, count)以生成上面計算高度的樹。
函式postorder_traversal(Tree_Node* node, int k)列印以node為根節點的k叉樹的後序遍歷。
如果節點為NULL，則不返回任何內容。
使用for迴圈遍歷，從i=0到i
在for迴圈結束時列印node->address。
示例
#include <bits/stdc++.h>
using namespace std;
struct Tree_Node{
int address;
vector<Tree_Node*> root;
};
Tree_Node* new_Node(int data){
Tree_Node* newNode = new Tree_Node;
newNode−>address = data;
return newNode;
}
Tree_Node* create_tree(int arr[], int N, int k, int height, int& count){
if(N <= 0){
return NULL;
}
Tree_Node* newNode = new_Node(arr[count]);
if (newNode == NULL){
cout<<"Code Dumped";
return NULL;
}
for(int i = 0; i < k; i++){
if (count < N − 1 && height > 1){
count++;
newNode−>root.push_back(create_tree(arr, N, k, height − 1, count));
}else{
newNode−>root.push_back(NULL);
}
}
return newNode;
}
Tree_Node* create_tree(int* arr, int N, int k, int count){
int height = (int)ceil(log((double)N * (k − 1) + 1) / log((double)k));
return create_tree(arr, N, k, height, count);
}
void preorder_traversal(Tree_Node* node, int k){
if (node == NULL){
return;
}
for(int i = 0; i < k; i++){
preorder_traversal(node−>root[i], k);
}
cout<<node−>address<< " ";
}
int main(){
int arr[] = {2, 5, 1, 3, 6, 7, 2, 1 };
int size = 8;
int children = 2;
int count = 0;
Tree_Node* node = create_tree(arr, size, children, count);
cout<<"Construct the full k−ary tree from its preorder traversal are: ";
preorder_traversal(node, children);
return 0;
}輸出
如果執行以上程式碼，將生成以下輸出：
Construct the full k-ary tree from its preorder traversal are: 3 6 1 2 1 7 5 2
355 次瀏覽
