プログラミング
 Computer >> コンピューター >  >> プログラミング >> プログラミング

データ構造におけるポストオーダーツリートラバーサル


このセクションでは、二分探索木のポストオーダートラバーサル手法(再帰的)について説明します。

このようなツリーが1つあるとします-

データ構造におけるポストオーダーツリートラバーサル

トラバーサルシーケンスは次のようになります:8、5、15、23、20、16、10

アルゴリズム

postorderTraverse(root):
Begin
   if root is not empty, then
      postorderTraversal(left of root)
      postorderTraversal(right of root)
      print the value of root
   end if
End

#include<iostream>
using namespace std;
class node{
   public:
      int h_left, h_right, bf, value;
      node *left, *right;
};
class tree{
   private:
      node *get_node(int key);
   public:
      node *root;
      tree(){
         root = NULL; //set root as NULL at the beginning
      }
      void postorder_traversal(node *r);
      node *insert_node(node *root, int key);
};
node *tree::get_node(int key){
   node *new_node;
   new_node = new node; //create a new node dynamically
   new_node->h_left = 0; new_node->h_right = 0;
   new_node->bf = 0;
   new_node->value = key; //store the value from given key
   new_node->left = NULL; new_node->right = NULL;
   return new_node;
}
void tree::postorder_traversal(node *r){
   if(r != NULL){ //When root is present, visit left - root - right
      postorder_traversal(r->left);
      postorder_traversal(r->right);
      cout << r->value << " ";
   }
}
node *tree::insert_node(node *root, int key){
   if(root == NULL){
      return (get_node(key)); //when tree is empty, create a node as root
   }
   if(key < root->value){ //when key is smaller than root value, go to the left
      root->left = insert_node(root->left, key);
   }else if(key > root->value){ //when key is greater than root value, go to the right
      root->right = insert_node(root->right, key);
   }
   return root; //when key is already present, do not insert it again
}
main(){
   node *root;
   tree my_tree;
   //Insert some keys into the tree.
   my_tree.root = my_tree.insert_node(my_tree.root, 10);
   my_tree.root = my_tree.insert_node(my_tree.root, 5);
   my_tree.root = my_tree.insert_node(my_tree.root, 16);
   my_tree.root = my_tree.insert_node(my_tree.root, 20);
   my_tree.root = my_tree.insert_node(my_tree.root, 15);
   my_tree.root = my_tree.insert_node(my_tree.root, 8);
   my_tree.root = my_tree.insert_node(my_tree.root, 23);
   cout << "Post-Order Traversal: ";
   my_tree.postorder_traversal(my_tree.root);
}

出力

Post-Order Traversal: 8 5 15 23 20 16 10

  1. Pythonでの二分木ポストオーダートラバーサル

    二分木があるとします。反復アプローチを使用して、このツリーのポストオーダートラバーサルを見つける必要があります。したがって、ツリーが次のような場合- その場合、出力は次のようになります:[9,15,7,10、-10] これを解決するには、次の手順に従います- ルートがnullの場合、空の配列を返します 配列を作成するret stack:=ペア[root、0]でスタックを定義します スタックが空でない間- node:=スタックの一番上にあり、スタックから要素を削除します。 ノードペアの2番目の値が0の場合、 current:=ノードペアの最初

  2. Pythonでインオーダートラバーサルとポストオーダートラバーサルからバイナリツリーを構築する

    二分木のインオーダーおよびポストオーダートラバーサルシーケンスがあるとします。これらのシーケンスからツリーを生成する必要があります。したがって、事後順序と順序順のシーケンスが[9,15,7,20,3]と[9,3,15,20,7]の場合、ツリーは-になります。 手順を見てみましょう- メソッドがビルドツリーと呼ばれ、プレオーダーリストとインオーダーリストがあるとします root:=ポストオーダーから最後のノード、ポストオーダーから最初のノードを削除 root_index:=インオーダーリストからのroot.valのインデックス leftまたはroot:=buildTree(roo