C++のバイナリツリーでノードの後続を事前注文する
この問題では、二分木とノード値が与えられます。私たちのタスクは、ノードのプレオーダーサクセサを印刷することです。
二分木 は、各ルートノードが最大2つの子ノードを持つことができる特殊なタイプのツリーです。
プレオーダートラバーサル ツリーのノードをトラバースする方法です。ここでは、最初にルートノードをトラバースし、次に左の子、次に右の子をトラバースします。
後続ノードの事前注文 ノードのプレオーダートラバーサルでノードの隣に来るノードです。
問題を理解するために例を見てみましょう
Input: 9 Output 0 Explanation: the preorder traversal of the tree is: 5 9 0 1 2 5. So the preorder successor of 9 is 0.
この問題を解決するための簡単なアプローチは、バイナリツリーのプレオーダートラバーサルを見つけて、指定された番号の後に続く要素を出力することです。
より効果的な解決策は、与えられた番号の位置をチェックし、位置に基づいてその後継者を検索することです。したがって、ポジションに左の子がある場合、事前注文の後継者は左の子になります。リーフノードであるが子のままである場合、その兄弟ノードはプレオーダーサクセサです。リーフノードであり、子が残っていない場合は、子ノードがプレオーダーの後続ノードとなる祖先ノードに移動する必要があります。
プログラムは解決策をより明確にします
例
#include <iostream>
using namespace std;
struct Node {
struct Node *left, *right, *parent;
int key;
};
Node* insertNode(int key){
Node* temp = new Node;
temp->left = temp->right = temp->parent = NULL;
temp->key = key;
return temp;
}
Node* preOrderSuccessorNode(Node* root, Node* n){
if (n->left)
return n->left;
Node *curr = n, *parent = curr->parent;
while (parent != NULL && parent->right == curr) {
curr = curr->parent;
parent = parent->parent;
}
if (parent == NULL)
return NULL;
return parent->right;
}
int main(){
Node* root = insertNode(99);
root->parent = NULL;
root->left = insertNode(4);
root->left->parent = root;
root->left->left = insertNode(18);
root->left->left->parent = root->left;
root->left->right = insertNode(50);
root->left->right->parent = root->left;
root->right = insertNode(26);
root->right->parent = root;
root->right->left = insertNode(5);
root->right->left->parent = root->right;
root->right->right = insertNode(10);
root->right->right->parent = root->right;
Node* preOrder = preOrderSuccessorNode(root, root->left->right);
if (preOrder) {
cout<<"Preorder successor of "<<root->left->right->key<<" is "<<preOrder->key;
} else {
cout<<"Preorder successor of "<<root->left->right->key<<" is NULL";
}
return 0;
} 出力
Preorder successor of 50 is 26
-
C++のバイナリツリーでノードの先行ノードを事前注文する
この問題では、二分木とノード値が与えられます。私たちのタスクは、ノードのプレオーダーの先行を印刷することです。 二分木 は、各ルートノードが最大2つの子ノードを持つことができる特殊なタイプのツリーです。 プレオーダートラバーサル ツリーのノードをトラバースする方法です。ここでは、最初にルートノードをトラバースし、次に左の子、次に右の子をトラバースします。 先行ノードの事前注文 ノードのプレオーダートラバーサルでノードの前に来るノードです。 問題を理解するために例を見てみましょう Input: 1 Output: 9 この問題を解決するには、 navie アプローチは、二分木の
-
Pythonでの二分木プレオーダートラバーサル
二分木があるとします。そのツリーのプレオーダートラバーサルを返す必要があります。したがって、ツリーが次のような場合- その場合、プレオーダートラバーサルは次のようになります:[3,9,20,15,7] これを解決するには、次の手順に従います- resとstという空のリストを作成します。 node:=root ノードまたはstが空でない場合 ノードがnullでない場合、 ノードのvalをresに挿入し、ノードをstに挿入し、ノードを設定します:=ノードの左側 temp:=stの最後の要素、およびstの最後の要素を削除 臨時雇用者の権利が利用できる場合は、 node:=t