이 섹션에서는 이진 검색 트리에 있는 키를 탐색하는 다양한 탐색 알고리즘을 볼 것입니다. 이러한 순회는 Inorder 순회, Preorder 순회, Postorder 순회 및 레벨 순서 순회입니다.
다음과 같은 트리가 하나 있다고 가정해 보겠습니다. -
Inorder 순회 시퀀스는 다음과 같습니다. − 5 8 10 15 16 20 23
선주문 순회 시퀀스는 다음과 같습니다. − 10 5 8 16 15 20 23
Postorder 순회 시퀀스는 다음과 같습니다. − 8 5 15 23 20 16 10
레벨 순서 순회 시퀀스는 다음과 같습니다. - 10, 5, 16, 8, 15, 20, 23
알고리즘
inorderTraversal(루트):루트가 비어 있지 않으면 시작하고, 루트가 비어 있지 않으면 inorderTraversal(루트 왼쪽)에서 루트 값을 인쇄합니다. 루트의 preorderTraversal(루트의 왼쪽) preorderTraversal(루트의 오른쪽) end ifEndpostorderTraverse(루트):루트가 비어 있지 않으면 시작하고 postorderTraversal(루트의 왼쪽) postorderTraversal(루트의 오른쪽) 루트 끝의 값을 인쇄 ifEndlevelOrderTraverse(루트) :큐에 루트를 삽입하는 노드를 저장하기 위해 큐를 정의하기 시작합니다. que가 비어 있지 않은 동안 수행 item :=item present at the front position of queue 항목의 왼쪽이 null이 아니면 항목의 값을 인쇄한 다음 항목의 오른쪽이 null이 아니면 항목의 왼쪽을 que end에 삽입합니다. que doneEnd에서 앞 요소를 삭제하면 항목의 오른쪽을 que end에 삽입합니다.
예시
#include#include 네임스페이스 std;class node 사용{ public:int h_left, h_right, bf, value; 노드 *왼쪽, *오른쪽;};클래스 트리{ private:노드 *get_node(int 키); 공개:노드 *루트; 트리(){ 루트 =NULL; //처음에 root를 NULL로 설정 } void inorder_traversal(node *r); 무효 preorder_traversal(노드 *r); 무효 postorder_traversal(노드 *r); 무효 levelorder_traversal(노드 *r); node *insert_node(node *root, int 키);};node *tree::get_node(int 키){ node *new_node; new_node =새 노드; // 동적으로 새 노드를 생성 new_node->h_left =0; new_node->h_right =0; new_node->bf =0; new_node->값 =키; //주어진 키의 값을 저장합니다. new_node->left =NULL; new_node->오른쪽 =NULL; return new_node;}void tree::inorder_traversal(node *r){ if(r !=NULL){ //루트가 있으면 왼쪽 - 루트 - 오른쪽을 방문합니다. inorder_traversal(r->left); cout < 값 <<" "; inorder_traversal(r->오른쪽); }}void tree::preorder_traversal(node *r){ if(r !=NULL){ //루트가 존재하면 왼쪽 - 루트 - 오른쪽으로 방문 cout < value <<" "; preorder_traversal(r->왼쪽); preorder_traversal(r->오른쪽); }}void tree::postorder_traversal(node *r){ if(r !=NULL){ //루트가 있으면 왼쪽 - 루트 - 오른쪽을 방문합니다. postorder_traversal(r->left); postorder_traversal(r->오른쪽); cout < 값 <<" "; }} 무효 트리::levelorder_traversal(노드 *루트){ 큐 <노드*> 큐; 노드 *항목; que.push(루트); //먼저 루트를 삽입 while(!que.empty()){ item =que.front(); //프론트 엔드에서 요소를 가져옵니다. cout < value <<" "; if(item->left !=NULL) //왼쪽 자식이 있으면 큐에 삽입 que.push(item->left); if(item->right !=NULL) //오른쪽 자식이 있으면 큐에 삽입 que.push(item->right); que.pop(); //큐에서 아이템 제거 }}node *tree::insert_node(node *root, int key){ if(root ==NULL){ return (get_node(key)); //트리가 비어 있을 때 root로 노드 생성 } if(key value){ //key가 root 값보다 작을 때 왼쪽으로 이동 root->left =insert_node(root->left, key ); }else if(key> root->value){ //key가 root 값보다 크면 오른쪽으로 이동 root->right =insert_node(root->right, key); } 리턴 루트; //키가 이미 있는 경우 다시 삽입하지 않음}main(){ node *root; 나무 my_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 <<"순차 순회:"; my_tree.inorder_traversal(my_tree.root); cout <<"\n선주문 순회:"; my_tree.preorder_traversal(my_tree.root); cout <<"\n주문 후 순회:"; my_tree.postorder_traversal(my_tree.root); cout <<"\n레벨 순서 순회:"; my_tree.levelorder_traversal(my_tree.root);}
출력
순차 순회:5 8 10 15 16 20 23선주문 순회:10 5 8 16 15 20 23주문 후 순회:8 5 15 23 20 16 10수준-순차 순회:15 208 5 사전>