एक कंटीन्यूअस ट्री को एक ऐसे पेड़ के रूप में परिभाषित किया जाता है जिसमें रूट नोड से लीफ नोड तक किसी भी पथ के साथ नोड्स का मान या वजन होता है जैसे कि पैरेंट नोड और उसके सभी डायरेक्टचिल्ड्रन नोड्स के बीच पूर्ण अंतर हमेशा 1 होता है।
अगर हम जड़ से पत्ती तक के रास्ते में कोई नोड चुनते हैं, तो
|बाएं बच्चे के नोड के नोड-वजन का वजन|=|बाएं बच्चे के नोड का वजन-नोड का वजन| =1, यह सही बच्चे के लिए भी सही है
|राइट चाइल्ड नोड के नोड-वेट का वजन|=|वेट लोफ राइट चाइल्ड नोड-नोड का वजन| =1
आरेख
आइए उदाहरणों से समझते हैं।
नीचे दिया गया पेड़ निरंतर है क्योंकि माता-पिता नोड्स और उनके बच्चे के बीच पूर्ण अंतर हमेशा 1 होता है।
नीचे दिया गया वृक्ष एक सतत वृक्ष होने के योग्य नहीं है।
एल्गोरिदम यह पता लगाने के लिए कि क्या पेड़ निरंतर है
-
अगर रूट न्यूल है, तो 1
. लौटाएं -
यदि यह एक लीफ नोड है, तो 1 लौटाएं क्योंकि ट्री कंटीन्यूअस रहा है इसलिए लीफ नोड तक पहुंच गया है।
-
यदि बायां उपट्री खाली है तो दाएं बच्चे के साथ वर्तमान नोड की निरंतरता की जांच करें (वजन के पूर्ण अंतर की गणना करें) और दाएं उपट्री के लिए पुनरावर्ती रूप से जारी रखें।
-
यदि दायां उपट्री खाली है, तो बाएं बच्चे के साथ वर्तमान नोड की निरंतरता की जांच करें (वजन के पूर्ण अंतर की गणना करें) और बाएं उपट्री के लिए पुनरावर्ती रूप से जारी रखें।
-
अन्यथा बाएं और दाएं बच्चे के वजन के साथ पूर्ण अंतर की गणना करें और बाएं और दाएं उप-वृक्षों के लिए पुनरावर्ती रूप से जारी रखें।
स्यूडोकोड
// Function to check tree is continuous or not
struct btreeNode{
int data;
btreeNode* left, * right;
};
int isContinuous(btreeNode *root){
// if node is NULL return 1, exit condition
if (root == NULL)
return 1;
//if leaf node is reached then tree must be continous during this path
if (root->left == NULL && root->right == NULL)
return 1;
// if no left child
if (root->left == NULL)
return (abs(root->data - root->right->data) == 1) && isContinuous(root->right);
// if no right child
if (root->right == NULL)
return (abs(root->data - root->left->data) == 1) && isContinuous(root->left);
// calculate absoute difference
return abs(root->data - root->left->data)==1 && abs(root->data - root->right->data)==1 &&
isContinuous(root->left) && isContinuous(root->right);
}