Đặt hàng trước Traversal cây 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ự trước (đệ 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:10, 5, 8, 16, 15, 20, 23

Thuật toán

preorderTraverse(root):
Begin
   if root is not empty, then
      print the value of root
      preorderTraversal(left of root)
      preorderTraversal(right 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 preorder_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::preorder_traversal(node *r){
   if(r != NULL){ //When root is present, visit left - root - right
      cout << r->value << " ";
      preorder_traversal(r->left);
      preorder_traversal(r->right);
   }
}
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 << "Pre-Order Traversal: ";
   my_tree.preorder_traversal(my_tree.root);
}

Đầu ra

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