C 言語でバイナリツリーの右側のビューを出力します。-C++-php.cn

タスクは、指定されたバイナリツリーの右ノードを出力することです。まずユーザーはデータを挿入してバイナリツリーを作成し、次に結果のツリーの右側のビューを印刷します。

C 言語でバイナリツリーの右側のビューを出力します。

上の画像は、ノード 10、42、93、14、35、96、57、および 88 を使用して作成されたバイナリツリーを示しており、それらが選択されて右側に表示されています。ツリーノードの側面。たとえば、10、93、57、および 88 はバイナリツリーの右端のノードです。

例

Input : 10 42 93 14 35 96 57 88 Output : 10 93 57 88

ログイン後にコピー

各ノードには、左ポインターと右ポインターの 2 つのポインターがあります。この質問によると、プログラムは正しいノードをトラバースするだけで済みます。したがって、ノードの左側の子を考慮する必要はありません。

右側のビューには、そのレベルの最後のノードであるすべてのノードが保存されます。したがって、最初に右のサブツリーをたどってから左のサブツリーをたどるという方法で、単純に再帰的メソッドを使用してノードを保存しアクセスすることができます。ノードのレベルが前のノードのレベルよりも大きいことがプログラムによって検出されると、前のノードがそのレベルの最後のノードになるため、そのノードが表示されます。

次のコードは、特定のアルゴリズムの C 言語実装を示しています。

アルゴリズム

START Step 1 -> create node variable of type structure Declare int data Declare pointer of type node using *left, *right Step 2 -> create function for inserting node with parameter as item Declare temp variable of node using malloc Set temp->data = item Set temp->left = temp->right = NULL return temp step 3 -> Declare Function void right_view(struct node *root, int level, int *end_level) IF root = NULL Return IF *end_level < level Print root->data Set *end_level = level Call right_view(root->right, level+1, end_level) Call right_view(root->left, level+1, end_level) Step 4 -> Declare Function void right(struct node *root) Set int level = 0 Call right_view(root, 1, &level) Step 5 -> In Main() Pass the values for the tree nodes using struct node *root = New(10) Call right(root) STOP

ログイン後にコピー

の中国語訳は次のとおりです:

Example

#include #include struct node { int data; struct node *left, *right; }; struct node *New(int item) { struct node *temp = (struct node *)malloc(sizeof(struct node)); temp->data = item; temp->left = temp->right = NULL; return temp; } void right_view(struct node *root, int level, int *end_level) { if (root == NULL) return; if (*end_level < level) { printf("%d\t", root->data); *end_level = level; } right_view(root->right, level+1, end_level); right_view(root->left, level+1, end_level); } void right(struct node *root) { int level = 0; right_view(root, 1, &level); } int main() { printf("right view of a binary tree is : "); struct node *root = New(10); root->left = New(42); root->right = New(93); root->left->left = New(14); root->left->right = New(35); root->right->left = New(96); root->right->right = New(57); root->right->left->right = New(88); right(root); return 0; }

ログイン後にコピー