C ++での二分木の反時計回りのスパイラルトラバーサル?
二分木の反時計回りのスパイラルトラバーサルは、トラバースされた場合にスパイラルを作成するが逆の順序でツリーの要素をトラバースします。次の図は、二分木の反時計回りのスパイラルトラバーサルを示しています。
二分木のスパイラルトラバーサル用に定義されたアルゴリズムは、次のように機能します-
2つの変数iとjが初期化され、値はi=0およびj=変数の高さと同等になります。フラグは、セクションが印刷されている間をチェックするために使用されます。フラグは最初はfalseに設定されています。 i
例
#include <bits/stdc++.h> using namespace std; struct Node { struct Node* left; struct Node* right; int data; Node(int data) { this->data = data; this->left = NULL; this->right = NULL; } }; int height(struct Node* root) { if (root == NULL) return 0; int lheight = height(root->left); int rheight = height(root->right); return max(1 + lheight, 1 + rheight); } void leftToRight(struct Node* root, int level) { if (root == NULL) return; if (level == 1) cout << root->data << " "; else if (level > 1) { leftToRight(root->left, level - 1); leftToRight(root->right, level - 1); } } void rightToLeft(struct Node* root, int level) { if (root == NULL) return; if (level == 1) cout << root->data << " "; else if (level > 1) { rightToLeft(root->right, level - 1); rightToLeft(root->left, level - 1); } } int main() { struct Node* root = new Node(1); root->left = new Node(2); root->right = new Node(3); root->left->left = new Node(4); root->right->left = new Node(5); root->right->right = new Node(7); root->left->left->left = new Node(10); root->left->left->right = new Node(11); root->right->right->left = new Node(8); int i = 1; int j = height(root); int flag = 0; while (i <= j) { if (flag == 0) { rightToLeft(root, i); flag = 1; i++; } else { leftToRight(root, j); flag = 0; j--; } } return 0; }
出力
1 10 11 8 3 2 4 5 7
-
C++のバイナリツリーの最大パス合計
この問題では、各ノードに値が含まれる二分木が与えられます。私たちのタスクは、二分木の2つの葉の間の最大パスの合計を見つけるプログラムを作成することです。 ここでは、値の最大合計を提供する、あるリーフノードから別のリーフノードへのパスを見つける必要があります。この最大合計パスには、ルートノードを含めることができます/含めることができません。 二分木 は、各ノードが最大2つの子ノードを持つことができるツリーデータ構造です。これらは左の子と右の子と呼ばれます。 例 − 問題を理解するために例を見てみましょう- 入力 −//二分木… 出力 − 24 説明 −リーフノード− 2から9へ
-
C++で二分木の2つのノード間の距離を見つける
ノードが少ない二分木があると考えてください。 2つのノードuとvの間の距離を見つける必要があります。ツリーが次のようになっていると仮定します- これで、(4、6)=4の間の距離、パスの長さは4、(5、8)の間の長さ=5などになります。 この問題を解決するために、LCA(Lowest Common Ancestor)を見つけてから、LCAから2つのノードまでの距離を計算します。 例 #include<iostream> using namespace std; class Node { public: in