यदि आपके पास प्रत्येक बच्चे में माता-पिता का लिंक है तो यह संभव है। जब आप बच्चे का सामना करते हैं, तो बाएं उपट्री पर जाएं। बैक अप आने पर यह देखने के लिए जांचें कि क्या आप अपने माता-पिता के बाएं बच्चे हैं या नहीं। यदि ऐसा है, तो सही उपट्री पर जाएं। अन्यथा, जब तक आप बाएं बच्चे न हों तब तक ऊपर जायें जब तक कि आप पेड़ की जड़ को हिट न करें।
इस उदाहरण में ढेर का आकार स्थिर रहता है, इसलिए कोई अतिरिक्त स्मृति खपत नहीं होती है। बेशक, जैसा कि मेहर्डद ने बताया, माता-पिता के लिंक को ओ (एन) स्थान माना जा सकता है, लेकिन यह पेड़ की संपत्ति से अधिक है, यह एल्गोरिदम की संपत्ति है।
यदि आपको उस पेड़ को पार करने के क्रम में कोई परवाह नहीं है, तो आप नोड्स पर एक अभिन्न मैपिंग असाइन कर सकते हैं जहां रूट 1 है, रूट के बच्चे 2 और 3 हैं, उनमें से बच्चे हैं 4, 5, 6, 7, इत्यादि। फिर आप पेड़ की प्रत्येक पंक्ति के माध्यम से काउंटर को बढ़ाकर और उस नोड को इसके संख्यात्मक मूल्य से एक्सेस करके लूप करते हैं। आप उच्चतम संभावित बच्चे तत्व का ट्रैक रख सकते हैं और जब आपका काउंटर गुजरता है तो लूप को रोक सकते हैं। समय-समय पर, यह एक अत्यंत अक्षम अक्षम एल्गोरिदम है, लेकिन मुझे लगता है कि यह ओ (1) स्थान लेता है।
(मैं ढेर से नंबर के विचार उधार लिया था। आप नोड एन है, तो आप 2N पर बच्चों और 2N +1 पा सकते हैं। आप एक बच्चे के माता-पिता को खोजने के लिए इस नंबर से पीछे की ओर काम कर सकते हैं।)
यहाँ सी सूचना में कार्रवाई में इस एल्गोरिथ्म का एक उदाहरण है कि वहाँ पेड़ के निर्माण के लिए छोड़कर कोई malloc के हैं, और कोई पुनरावर्ती कार्य हैं कि जिसका अर्थ है कि ढेर निरंतर अंतरिक्ष लेता है:
#include <stdio.h>
#include <stdlib.h>
typedef struct tree
{
int value;
struct tree *left, *right;
} tree;
tree *maketree(int value, tree *left, tree *right)
{
tree *ret = malloc(sizeof(tree));
ret->value = value;
ret->left = left;
ret->right = right;
return ret;
}
int nextstep(int current, int desired)
{
while (desired > 2*current+1)
desired /= 2;
return desired % 2;
}
tree *seek(tree *root, int desired)
{
int currentid; currentid = 1;
while (currentid != desired)
{
if (nextstep(currentid, desired))
if (root->right)
{
currentid = 2*currentid+1;
root = root->right;
}
else
return NULL;
else
if (root->left)
{
currentid = 2*currentid;
root = root->left;
}
else
return NULL;
}
return root;
}
void traverse(tree *root)
{
int counter; counter = 1; /* main loop counter */
/* next = maximum id of next child; if we pass this, we're done */
int next; next = 1;
tree *current;
while (next >= counter)
{
current = seek(root, counter);
if (current)
{
if (current->left || current->right)
next = 2*counter+1;
/* printing to show we've been here */
printf("%i\n", current->value);
}
counter++;
}
}
int main()
{
tree *root1 =
maketree(1, maketree(2, maketree(3, NULL, NULL),
maketree(4, NULL, NULL)),
maketree(5, maketree(6, NULL, NULL),
maketree(7, NULL, NULL)));
tree *root2 =
maketree(1, maketree(2, maketree(3,
maketree(4, NULL, NULL), NULL), NULL), NULL);
tree *root3 =
maketree(1, NULL, maketree(2, NULL, maketree(3, NULL,
maketree(4, NULL, NULL))));
printf("doing root1:\n");
traverse(root1);
printf("\ndoing root2:\n");
traverse(root2);
printf("\ndoing root3:\n");
traverse(root3);
}
मैं कोड की गुणवत्ता के लिए क्षमा चाहता हूं - यह काफी हद तक अवधारणा का सबूत है। साथ ही, इस एल्गोरिदम का रनटाइम आदर्श नहीं है क्योंकि यह किसी भी राज्य की जानकारी को बनाए रखने में सक्षम नहीं होने के लिए क्षतिपूर्ति करने के लिए बहुत सारे काम करता है। प्लस तरफ, यह ऑर्डर करने के लिए ओ (1) स्पेस एल्गोरिदम के बिल को फिट करता है, किसी भी क्रम में, पेड़ के तत्वों को बिना माता-पिता के लिंक की आवश्यकता होती है या पेड़ की संरचना को संशोधित किया जाता है।
मैं माता-पिता को ओ (एन) सहायक स्थान के रूप में लिंक मानता हूं। आपको अपने बाइनरी पेड़ का स्पष्ट रूप से उल्लेख करने के लिए अपने प्रश्न को संपादित करना चाहिए, ऐसी संपत्ति नहीं है। –
आपके माता-पिता नोड्स के पॉइंटर्स कैसे नहीं हो सकते हैं? आप अपने पेड़ पर बिना उनके बिना कैसे पुन: प्रयास कर सकते हैं? क्या वह ढेर आ रहा है? संतुलन करने के लिए आपको माता-पिता के पॉइंटर्स की आवश्यकता होगी। –