数据结构
网络
关系数据库管理系统 (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 次浏览
