का उपयोग करके एक स्टैक लागू करें मैं एक बीएसटी का उपयोग कर एक स्टैक (पुश और पॉप ऑपरेशंस) को कार्यान्वित करना चाहता हूं।एक बीएसटी
बीएसटी में पोस्ट ऑर्डर ट्रैवर्सल के दौरान, स्टैक में रूट पर रखा जाता है, जबकि इसे क्रमशः ट्रैवर्स किया जाता है। तो, क्या इसका मतलब है कि मुझे रूट या कुछ और तत्वों से तत्वों को सम्मिलित करना और हटाना है?
int num=1;
struct node
{
int flag;
int val;
node *left,*right,*parent;
};
node* tree::InorderTraversalusingInBuiltstack()
{
stack<node *> p;
node *current=root;
while(!p.empty()|| current!=NULL)
{
while(current!=NULL)
{
p.push(current);
current=current->left;
}
current=p.top();
if(current->flag==num)
{
return current;
}
p.pop();
current=current->right;
}
}
void tree::StackUsingBST()
{
node *q;
while(root!=NULL)
{
num--;
q=InorderTraversalusingInBuiltqueue();
node *a=q->parent;
if(a!=NULL)
{
if(a->left==q)
a->left=NULL;
else
a->right=NULL;
q->parent=NULL;
delete q;
disp();
cout<<endl;
}
else
{
delete q;
root=NULL;
}
}
}
यहाँ मेरी दृष्टिकोण है कि मैं थोड़ा मेरे डेटा संरचना संशोधित, एक वैश्विक चर के रूप में एक झंडा चर का उपयोग करना है;
पहले लगता है मैं सम्मिलित 8 तो उसके संगत झंडा मान 1 तो सम्मिलित 12 इसके झंडे मूल्य = 2 तो 3 सम्मिलित है इसके झंडे मूल्य = 3
अब inorder ढेर मैं नष्ट करने के लिए है के रूप में BST उपयोग करने के लिए तत्व जो आखिरी बार डाला गया है, और मेरे अहंकार के अनुसार उच्चतम ध्वज मूल्य है।
यह भी ध्यान रखें कि डाले गए अंतिम तत्व में कोई बच्चा नहीं होगा, इसलिए इसका विलोपन काफी आसान है।
नोड्स के साथ उपलब्ध उच्चतम ध्वज मूल्य को खोजने के लिए, मैंने स्टैक का उपयोग करके एक इनडोरर्ट्रावर्सेल किया जो इसके रिकर्सिव ट्रैवर्सल से बेहतर है।
उस नोड को उच्चतम ध्वज मूल्य के अनुरूप ढूंढने के बाद, मैं उस नोड को हटा देता हूं। इस प्रक्रिया को रूट = NULL तक दोहराया जाता है।