Chuyển ngang cây theo thứ tự trong cấu trúc dữ liệu

Trong phần này, chúng ta sẽ thấy kỹ thuật duyệt theo thứ tự sau (đệ quy) cho cây tìm kiếm nhị phân.

Giả sử chúng ta có một cây như thế này -

Trình tự duyệt sẽ như sau:8, 5, 15, 23, 20, 16, 10

Thuật toán

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

Ví dụ

#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);
}

Đầu ra

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