按照顶层顺序和颠倒底层顺序交替打印二叉查找树的节点
原文:https://www . geesforgeks . org/print-二进制搜索树的节点-顶层-顺序-和-颠倒-底层-顺序-交替/
给定一个二叉查找树，任务是按照以下顺序打印 BST 的节点:
- 如果 BST 包含编号从 1 到 N 的级别，则打印顺序为级别 1 、级别 N 、级别 2 、级别N–1等等。
- 顶层顺序()1、2 、…)节点从左至右打印，底层顺序(【N】、 N-1 、…)节点从右至左打印。
示例:
输入:
输出: 27 42 31 19 10 14 35 解释: 一级从左到右:27 三级从右到左:42 31 19 10 二级从左到右:14 35
输入:
输出: 25 48 38 28 12 5 20 36 40 30 22 10
做法:解决问题的思路是将 BST 的节点按照级别和节点值的升序和降序进行存储，在升序和降序之间交替打印同一级别的所有节点。按照以下步骤解决问题:
- 初始化一个最小堆和一个最大堆，分别按照级别和节点值的升序和降序存储节点。
- 在给定的 BST 上执行级顺序遍历，以将节点存储在相应的优先级队列中。
- 从最小堆开始，依次交替打印每一级的所有节点最大堆。
- 如果发现最小堆或最大堆中的任何一级已经打印，跳到下一级。
下面是上述方法的实现:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Structure of a BST node
struct node {
int data;
struct node* left;
struct node* right;
};
// Utility function to create a new BST node
struct node* newnode(int d)
{
struct node* temp
= (struct node*)malloc(sizeof(struct node));
temp->left = NULL;
temp->right = NULL;
temp->data = d;
return temp;
}
// Function to print the nodes of a
// BST in Top Level Order and Reversed
// Bottom Level Order alternatively
void printBST(node* root)
{
// Stores the nodes in descending order
// of the level and node values
priority_queue<pair<int, int> > great;
// Stores the nodes in ascending order
// of the level and node values
priority_queue<pair<int, int>,
vector<pair<int, int> >,
greater<pair<int, int> > >
small;
// Initialize a stack for
// level order traversal
stack<pair<node*, int> > st;
// Push the root of BST
// into the stack
st.push({ root, 1 });
// Perform Level Order Traversal
while (!st.empty()) {
// Extract and pop the node
// from the current level
node* curr = st.top().first;
// Stores level of current node
int level = st.top().second;
st.pop();
// Store in the priority queues
great.push({ level, curr->data });
small.push({ level, curr->data });
// Traverse left subtree
if (curr->left)
st.push({ curr->left, level + 1 });
// Traverse right subtree
if (curr->right)
st.push({ curr->right, level + 1 });
}
// Stores the levels that are printed
unordered_set<int> levelsprinted;
// Print the nodes in the required manner
while (!small.empty() && !great.empty()) {
// Store the top level of traversal
int toplevel = small.top().first;
// If the level is already printed
if (levelsprinted.find(toplevel)
!= levelsprinted.end())
break;
// Otherwise
else
levelsprinted.insert(toplevel);
// Print nodes of same level
while (!small.empty()
&& small.top().first == toplevel) {
cout << small.top().second << " ";
small.pop();
}
// Store the bottom level of traversal
int bottomlevel = great.top().first;
// If the level is already printed
if (levelsprinted.find(bottomlevel)
!= levelsprinted.end()) {
break;
}
else {
levelsprinted.insert(bottomlevel);
}
// Print the nodes of same level
while (!great.empty()
&& great.top().first == bottomlevel) {
cout << great.top().second << " ";
great.pop();
}
}
}
// Driver Code
int main()
{
/*
Given BST
25
/ \
20 36
/ \ / \
10 22 30 40
/ \ / / \
5 12 28 38 48
*/
// Creating the BST
node* root = newnode(25);
root->left = newnode(20);
root->right = newnode(36);
root->left->left = newnode(10);
root->left->right = newnode(22);
root->left->left->left = newnode(5);
root->left->left->right = newnode(12);
root->right->left = newnode(30);
root->right->right = newnode(40);
root->right->left->left = newnode(28);
root->right->right->left = newnode(38);
root->right->right->right = newnode(48);
// Function Call
printBST(root);
return 0;
}
Output:
25 48 38 28 12 5 20 36 40 30 22 10
时间复杂度: O(V log(V))，其中 V 表示给定二叉树中的顶点数 辅助空间: O(V)
版权属于：月萌API www.moonapi.com，转载请注明出处
