logo

TechCodeview

이진 트리의 선주문 순회

선주문 순회 의 유형으로 정의됩니다. 트리 순회 이는 루트-왼쪽-오른쪽 정책을 따릅니다.

가운데 버튼 CSS
  • 하위 트리의 루트 노드를 먼저 방문합니다.
  • 그런 다음 왼쪽 하위 트리를 탐색합니다.
  • 마지막으로 오른쪽 하위 트리를 탐색합니다.
선주문 순회

선주문 순회

이진 트리의 선주문 순회 알고리즘

선주문 순회 알고리즘은 다음과 같습니다.



선주문(루트):

  1. 루트 != NULL이 될 때까지 2~4단계를 따르세요.
  2. 루트 쓰기 -> 데이터
  3. 선주문(루트 -> 왼쪽)
  4. 선주문(루트 -> 오른쪽)
  5. 루프 종료

이진 트리의 선주문 순회는 어떻게 작동하나요?

다음 트리를 고려해보세요.

이진 트리의 예

이진 트리의 예

이 이진 트리에서 선주문 순회를 수행하면 순회는 다음과 같습니다.

1 단계: 처음에는 루트, 즉 노드 1을 방문합니다.

노드 1이 방문됨

노드 1이 방문됨

2 단계: 그런 다음 왼쪽 하위 트리를 순회합니다. 이제 왼쪽 하위 트리의 루트를 방문합니다. 즉, 노드 2를 방문합니다.

노드 2가 방문되었습니다.

노드 2가 방문되었습니다.

3분기

3단계: 다시 노드 2의 왼쪽 하위 트리를 탐색하고 해당 하위 트리의 루트, 즉 노드 4를 방문합니다.

노드 4가 방문되었습니다.

노드 4가 방문되었습니다.

4단계: 4의 하위 트리는 없으며 노드 2의 왼쪽 하위 트리를 방문합니다. 이제 노드 2의 오른쪽 하위 트리를 탐색하고 해당 하위 트리의 루트, 즉 노드 5를 방문합니다.

노드 5를 방문했습니다.

노드 5를 방문했습니다.

5단계: 노드 1의 왼쪽 하위 트리를 방문합니다. 이제 노드 1의 오른쪽 하위 트리를 탐색하고 루트 노드, 즉 노드 3을 방문합니다.

설정 메뉴 안드로이드
노드 3이 방문됨

노드 3이 방문됨

6단계: 노드 3에는 왼쪽 하위 트리가 없습니다. 따라서 오른쪽 하위 트리를 탐색하고 하위 트리의 루트, 즉 노드 6을 방문합니다. 그 이후에는 아직 통과하지 않은 노드가 없습니다. 이렇게 순회가 종료됩니다.

전체 트리를 방문합니다.

전체 트리를 방문합니다.

따라서 노드 순회 순서는 다음과 같습니다. 1 -> 2 -> 4 -> 5 -> 3 -> 6 .

전기의 장점

이진 트리의 선주문 순회를 구현하는 프로그램

다음은 선주문 순회 코드 구현입니다.

C++ 
// C++ program for preorder traversals #include  using namespace std; // Structure of a Binary Tree Node struct Node {  int data;  struct Node *left, *right;  Node(int v)  {  data = v;  left = right = NULL;  } }; // Function to print preorder traversal void printPreorder(struct Node* node) {  if (node == NULL)  return;  // Deal with the node  cout << node->데이터<< ' ';  // Recur on left subtree  printPreorder(node->왼쪽);  // 오른쪽 하위 트리에서 반복 printPreorder(node->right); } // 드라이버 코드 int main() { struct Node* root = new Node(1);  루트->왼쪽 = 새 노드(2);  루트->오른쪽 = new Node(3);  루트->왼쪽->왼쪽 = new Node(4);  루트->왼쪽->오른쪽 = new Node(5);  루트->오른쪽->오른쪽 = new Node(6);  // 함수 호출 cout<< 'Preorder traversal of binary tree is: 
';  printPreorder(root);  return 0; }>
자바 
// Java program for preorder traversals class Node {  int data;  Node left, right;  public Node(int item) {  data = item;  left = right = null;  } } class BinaryTree {  Node root;  BinaryTree() {  root = null;  }  // Function to print preorder traversal  void printPreorder(Node node) {  if (node == null)  return;  // Deal with the node  System.out.print(node.data + ' ');  // Recur on left subtree  printPreorder(node.left);  // Recur on right subtree  printPreorder(node.right);  }  // Driver code  public static void main(String[] args) {  BinaryTree tree = new BinaryTree();  // Constructing the binary tree  tree.root = new Node(1);  tree.root.left = new Node(2);  tree.root.right = new Node(3);  tree.root.left.left = new Node(4);  tree.root.left.right = new Node(5);  tree.root.right.right = new Node(6);  // Function call  System.out.println('Preorder traversal of binary tree is: ');  tree.printPreorder(tree.root);  } }>
파이썬3 
# Python program for preorder traversals # Structure of a Binary Tree Node class Node: def __init__(self, v): self.data = v self.left = None self.right = None # Function to print preorder traversal def printPreorder(node): if node is None: return # Deal with the node print(node.data, end=' ') # Recur on left subtree printPreorder(node.left) # Recur on right subtree printPreorder(node.right) # Driver code if __name__ == '__main__': root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.right.right = Node(6) # Function call print('Preorder traversal of binary tree is:') printPreorder(root)>
씨# 
// C# program for preorder traversals using System; // Structure of a Binary Tree Node public class Node {  public int data;  public Node left, right;  public Node(int v)  {  data = v;  left = right = null;  } } // Class to print preorder traversal public class BinaryTree {  // Function to print preorder traversal  public static void printPreorder(Node node)  {  if (node == null)  return;  // Deal with the node  Console.Write(node.data + ' ');  // Recur on left subtree  printPreorder(node.left);  // Recur on right subtree  printPreorder(node.right);  }  // Driver code  public static void Main()  {  Node root = new Node(1);  root.left = new Node(2);  root.right = new Node(3);  root.left.left = new Node(4);  root.left.right = new Node(5);  root.right.right = new Node(6);  // Function call  Console.WriteLine(  'Preorder traversal of binary tree is: ');  printPreorder(root);  } } // This code is contributed by Susobhan Akhuli>
자바스크립트 
// Structure of a Binary Tree Node class Node {  constructor(v) {  this.data = v;  this.left = null;  this.right = null;  } } // Function to print preorder traversal function printPreorder(node) {  if (node === null) {  return;  }  // Deal with the node  console.log(node.data);  // Recur on left subtree  printPreorder(node.left);  // Recur on right subtree  printPreorder(node.right); } // Driver code function main() {  const root = new Node(1);  root.left = new Node(2);  root.right = new Node(3);  root.left.left = new Node(4);  root.left.right = new Node(5);  root.right.right = new Node(6);  // Function call  console.log('Preorder traversal of binary tree is:');  printPreorder(root); } main();>
산출 
Preorder traversal of binary tree is: 1 2 4 5 3 6>

설명:

선주문 순회 작동 방식

선주문 순회 작동 방식

복잡성 분석:

시간 복잡도: O(N) 여기서 N은 총 노드 수입니다. 왜냐하면 모든 노드를 적어도 한 번은 통과하기 때문입니다.
보조 공간:

  • 오(1) 재귀 스택 공간이 고려되지 않는 경우.
  • 그렇지 않으면, 오) 여기서 h는 트리의 높이입니다.
  • 최악의 경우, 시간 와 같을 수 있다 N (나무가 기울어진 나무인 경우)
  • 최선의 경우, 시간 와 같을 수 있다 침착한 (트리가 완전한 트리인 경우)

선주문 순회 사용 사례:

선주문 탐색의 일부 사용 사례는 다음과 같습니다.

  • 이는 트리의 복사본을 만드는 데 자주 사용됩니다.
  • 표현식 트리에서 접두사 표현식을 가져오는 것도 유용합니다.

관련 기사:

  • 트리 순회 유형
  • 반복적인 선주문 순회
  • 주어진 배열이 BST의 선주문 순회를 나타낼 수 있는지 확인하십시오.
  • 중위 순회 및 후위 순회에서 선주문
  • 이진 트리의 선순서 순회에서 n번째 노드 찾기
  • N-ary 트리의 선주문 순회