Disclaimer: The following method is not necessarily correct. It was written during personal study and has not been tested extensively. It is for reference only. There may be bugs and will not be changed for the time being.
Description: In order to improve search efficiency, a database constructs a binary search tree (BST) for a certain integer field. Each node contains two pieces of data information: 1) the node’s data, 2) the number of elements in the node’s subtree. In order to compress the size of the search tree, the database adds a field to each node, which is used to store the node data visited before accessing the node during in-order traversal. Under this improvement, if the stored node is a leaf node, the node will be deleted in the new tree to improve storage efficiency. If a leaf node has no in-order successor, there is no need to delete it.
Given a preorder traversal of the BST (the second field is not given), please write a program to output the preorder traversal result of the new BST after compression.
Input format
Enter a total of two lines: the first line is an int data n, indicating the number of summary points of the BST. 1<=n<=100000: The second line contains n int data, which is the pre-order traversal result of the BST (make sure the order is correct and the data are different). The range of each data: 0<=X<=1*10^7.
Output format
Output a total of one line: the first line is the pre-order traversal result of the new BST, output node data and other saved node data in order (if not, output the character -)
#include <iostream>
#include <vector>
#include <map>
#include <stack>
using namespace std;
struct Node
{
int val, childNodes = 0;
Node* left, *right;
int left_type = 0;//Type flag
int right_type = 0;//Type flag
Node(int val, int childNodes):val(val),childNodes(childNodes),left(nullptr), right(nullptr) {}
};
// Create a binary search tree based on preorder traversal
Node* createBstFromPreOrder(vector<int> & amp; preOrderNums, int left, int right) {
if (left > right) {
return nullptr;
}
Node* root = new Node(preOrderNums[left], right - left);
// If not found, mid is the rightmost value greater than 1, so that the right boundary on the left is mid-1, which is exactly the rightmost value of the array.
int mid = right + 1;
for (int i = left + 1; i <= right; i + + ) {
if (preOrderNums[i] > preOrderNums[left]) {
mid = i;
break;
}
}
root->left = createBstFromPreOrder(preOrderNums, left + 1, mid-1);
root->right = createBstFromPreOrder(preOrderNums, mid, right);
return root;
}
//The previous node when threading
Node* pre = nullptr;
map<int, int> mp_delete;
//In-order threading the binary tree
void InThreading(Node* p){
//If the current node exists
if (p) {
InThreading(p->left);//Recurse the left subtree of the current node for threading
//If the current node has no left child, the left flag is set to 1, and the left pointer field points to the previous node pre
if (!p->left) {
p->left_type = 1;
p->left=pre;
}
//If pre has no right child, the right flag bit is set to 1, and the right pointer field points to the current node.
if (pre & amp; & amp;!pre->right) {
pre->right=p;
pre->right_type = 1;
p->childNodes = pre->val;
//Indicates the node that needs to be deleted
cout << "Node to be deleted:" << pre->val << endl;
mp_delete[pre->val] = 1;
}
pre=p;//pre points to the current node
InThreading(p->right);//Recursive right subtree for threading
}
}
void preorderBst(Node *root)
{
if(root != NULL)
{
Node *p = root;
while (p != NULL)
{
while (p->left_type == 0) // The left pointer is not a clue, so move left while accessing
{
cout << p->val << " " << p->childNodes << endl; // Access nodes
p = p->left; // Shift left, access the left subtree
}
cout << p->val << " " << p->childNodes << endl; // At this time, the left side of p must be a clue, but it has not been accessed yet, so access it
p = p->right; // At this time, the left child of p does not exist. If the right pointer is not empty, it will point to its successor regardless of whether it is a clue or not.
}
}
}
Node *Next(Node *t) //If node t is known, find the "successor" node position of t
{
if(t->right_type==1) //The right flag is 1, you can directly get the "successor" node
{
t=t->right;
}
else /*The right flag is 0 and cannot directly go to the "successor" node.
Then you need to find the node in the lower left corner of the right subtree*/
{
t=t->right;
while(t->left_type==0)
{
t=t->left;
} //while
}//else
return t;
}
// Change the method to traverse the clue binary tree. When the relevant node is deleted, the clue is canceled and this method cannot be used.
void InorderTraverse(Node *temp)//Use clues to implement in-order traversal
{
if(!temp)
{
return;
}
\t
while(temp->left_type==0)//Find the first node
{ //Because the creation of the binary tree creat is created by the pre-order traversal sequence, the first node pointed by t is not the first node to be accessed by the in-order traversal.
temp=temp->left;
}
cout << "val:" << temp->val << " left_type:" << temp->left_type
<< " right_type:" << temp->right_type << " childNodes:" << temp->childNodes << endl;
while(temp->right)// The "right child of t is not empty" is used as the loop condition here because the "successor" of the last node was previously set to be empty, indicating the end.
{ //Access subsequent nodes based on clues
temp=Next(temp);
cout << "val:" << temp->val << " left_type:" << temp->left_type
<< " right_type:" << temp->right_type << " childNodes:" << temp->childNodes << endl;
}
}
//Use mp to record the first time it appears, and use it to judge when walking to the left. If it has appeared before, it will not go in the right direction. It means that the left side has been passed.
map<int, int> mp;
// Delete the relevant nodes and cancel the clues
void deleteBstNode(Node* root) {
if (root == nullptr) return;
stack<Node*> stk;
Node* p = root;
while (p != nullptr || stk.size()) {
// When it has not appeared before and there is a child on the left
while(p->left & amp; & amp; p->left->left_type == 0 & amp; & amp; mp[p->val] == 0) {
stk.push(p);
mp[p->val] = 1;
p = p->left;
}
// If the child on the left has a predecessor node, cancel the predecessor flag
if (p->left & amp; & amp; p->left->left_type == 1 & amp; & amp; p->left->left & amp; & amp; mp[p->val] == 0) {
stk.push(p);
mp[p->val] = 1;
// Set the previous node in its order to -1 and mark it as "-"
p->childNodes = -1;
p = p->left;
p->left = nullptr;
p->left_type = 0;
}
// Indicates that the left side needs to be deleted
else if (p->left & amp; & amp; mp[p->val] == 0) {
cout << "Deleted---" << p->left->val << endl; //2
p->left->right = nullptr;
p->left = nullptr;
}
// If the right side is gone, or there happens to be one on the right side that needs to be deleted
if((p->right == nullptr & amp; & amp; stk.size()) || (p->right & amp; & amp; p->right->right_type == 1)) {
while ((p->right == nullptr & amp; & amp; stk.size()) || (p->right & amp; & amp; p->right->right_type == 1)) {
// The right side needs to be deleted
if (p->right & amp; & amp; p->right->right_type == 1) {
cout << "Deleted + + + " << p->right->val << endl; // 5
p->right->right = nullptr;
p->right = nullptr;
} else if(p->right){
// No need to delete
p = p->right;
break;
}
p = stk.top();
stk.pop();
}
// When the above conditions are not met, move p to the right
if (p->right & amp; & amp; p->right->right_type == 0) {
p = p->right;
}
} else if (p->right & amp; & amp; p->right->right_type == 0) {
p = p->right;
} else {
// Must return when not satisfied at the end
return;
}
}
}
// Recursive pre-order traversal of binary tree
void preOrder(Node* root) {
if (root == nullptr) {
return;
}
cout << root->val << " " << root->childNodes << " " << endl;;
preOrder(root->left);
preOrder(root->right);
}
// Recursive in-order traversal of binary tree
void inOrder(Node* root) {
if (root == nullptr) {
return;
}
inOrder(root->left);
cout << root->val << " " << root->childNodes << " " << endl;;
inOrder(root->right);
}
// Recursive subsequent traversal of the binary tree
void postOrder(Node* root) {
if (root == nullptr) {
return;
}
postOrder(root->left);
postOrder(root->right);
cout << root->val << " " << root->childNodes << " " << endl;;
}
// There is a problem with the following access clue binary tree method
// void inOrderTraverse(Node* root)
// {
// //Start from the root node and find the leftmost one first
// if (root == NULL)
// {
// return;
// }
// Node* temp = root;
// //Find the leftmost node first and then traverse directly to the right based on clues
// while (temp != NULL & amp; & amp; temp->left_type == 0)
// {
// temp = temp->left;
// }
// while (temp != NULL)
// {
// //Output
// cout << "val:" << temp->val << " left_type:" << temp->left_type
// << " right_type:" << temp->right_type << " childNodes:" << temp->childNodes << endl;
// temp = temp->right;
// }
// }
int main() {
vector<int> nums = {6, 4, 2, 5, 9, 7, 8};
Node * head = createBstFromPreOrder(nums, 0, nums.size()-1);
preOrder(head);
cout << "=====================================" << endl;
inOrder(head);
cout << "=====================================" << endl;
postOrder(head);
cout << "=====================================" << endl;
// Threaded binary tree
InThreading(head);
//Delete related nodes
deleteBstNode(head);
//Traverse the binary tree
preOrder(head);
cout << "=====================================" << endl;
cin.get();
return 0;
}
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 57284 people are learning the system