주어진
이진 검색 트리
산출:
중위 순회: 10 20 30 100 150 200 300
선주문 순회: 100 20 10 30 200 150 300
우편주문 순회: 10 30 20 150 300 200 100
입력:
이진 검색 트리
산출:
중위 순회: 8 12 20 22 25 30 40
선주문 순회: 22 12 8 20 30 25 40
통신판매 순회: 8 20 12 25 40 30 22
중위순회 :
문제를 해결하기 위한 아이디어는 다음과 같습니다.
처음에는 트래버스 왼쪽 하위 트리 그런 다음 방문하세요 뿌리 그런 다음 횡단 오른쪽 하위 트리 .
아이디어를 구현하려면 아래 단계를 따르십시오.
- 왼쪽 하위 트리 탐색
- 루트를 방문하여 데이터를 인쇄합니다.
- 오른쪽 하위 트리 탐색
그만큼 중위순회 BST의 노드 값은 정렬된 순서로 제공됩니다. 내림차순을 얻으려면 오른쪽, 루트 및 왼쪽 하위 트리를 방문하십시오.
다음은 중위 순회 구현입니다.
C++
// C++ code to implement the approach> #include> using> namespace> std;> // Class describing a node of tree> class> Node {> public>:> >int> data;> >Node* left;> >Node* right;> >Node(>int> v)> >{> >this>->데이터 = v;> >this>->왼쪽 =>this>->오른쪽 = NULL;> >}> };> // Inorder Traversal> void> printInorder(Node* node)> {> >if> (node == NULL)> >return>;> >// Traverse left subtree> >printInorder(node->왼쪽);> >// Visit node> >cout ' '; // Traverse right subtree printInorder(node->오른쪽); } // 드라이버 코드 int main() { // 트리 노드 구축* root = new Node(100); 루트->왼쪽 = 새 노드(20); 루트->오른쪽 = 새 노드(200); 루트->왼쪽->왼쪽 = new Node(10); 루트->왼쪽->오른쪽 = new Node(30); 루트->오른쪽->왼쪽 = new Node(150); 루트->오른쪽->오른쪽 = new Node(300); // 함수 호출 cout<< 'Inorder Traversal: '; printInorder(root); return 0; }> |
>
>
자바
// Java code to implement the approach> import> java.io.*;> // Class describing a node of tree> class> Node {> >int> data;> >Node left;> >Node right;> >Node(>int> v)> >{> >this>.data = v;> >this>.left =>this>.right =>null>;> >}> }> class> GFG {> >// Inorder Traversal> >public> static> void> printInorder(Node node)> >{> >if> (node ==>null>)> >return>;> >// Traverse left subtree> >printInorder(node.left);> >// Visit node> >System.out.print(node.data +>' '>);> >// Traverse right subtree> >printInorder(node.right);> >}> >// Driver Code> >public> static> void> main(String[] args)> >{> >// Build the tree> >Node root =>new> Node(>100>);> >root.left =>new> Node(>20>);> >root.right =>new> Node(>200>);> >root.left.left =>new> Node(>10>);> >root.left.right =>new> Node(>30>);> >root.right.left =>new> Node(>150>);> >root.right.right =>new> Node(>300>);> >// Function call> >System.out.print(>'Inorder Traversal: '>);> >printInorder(root);> >}> }> // This code is contributed by Rohit Pradhan> |
>
>
파이썬3
# Python3 code to implement the approach> # Class describing a node of tree> class> Node:> >def> __init__(>self>, v):> >self>.left>=> None> >self>.right>=> None> >self>.data>=> v> # Inorder Traversal> def> printInorder(root):> >if> root:> ># Traverse left subtree> >printInorder(root.left)> > ># Visit node> >print>(root.data,end>=>' '>)> > ># Traverse right subtree> >printInorder(root.right)> # Driver code> if> __name__>=>=> '__main__'>:> ># Build the tree> >root>=> Node(>100>)> >root.left>=> Node(>20>)> >root.right>=> Node(>200>)> >root.left.left>=> Node(>10>)> >root.left.right>=> Node(>30>)> >root.right.left>=> Node(>150>)> >root.right.right>=> Node(>300>)> ># Function call> >print>(>'Inorder Traversal:'>,end>=>' '>)> >printInorder(root)> ># This code is contributed by ajaymakvana.> |
>
>
씨#
// Include namespace system> using> System;> // Class describing a node of tree> public> class> Node> {> >public> int> data;> >public> Node left;> >public> Node right;> >public> Node(>int> v)> >{> >this>.data = v;> >this>.left =>this>.right =>null>;> >}> }> public> class> GFG> {> >// Inorder Traversal> >public> static> void> printInorder(Node node)> >{> >if> (node ==>null>)> >{> >return>;> >}> >// Traverse left subtree> >GFG.printInorder(node.left);> >// Visit node> >Console.Write(node.data.ToString() +>' '>);> >// Traverse right subtree> >GFG.printInorder(node.right);> >}> >// Driver Code> >public> static> void> Main(String[] args)> >{> >// Build the tree> >var> root =>new> Node(100);> >root.left =>new> Node(20);> >root.right =>new> Node(200);> >root.left.left =>new> Node(10);> >root.left.right =>new> Node(30);> >root.right.left =>new> Node(150);> >root.right.right =>new> Node(300);> >// Function call> >Console.Write(>'Inorder Traversal: '>);> >GFG.printInorder(root);> >}> }> |
>
>
자바스크립트
// JavaScript code to implement the approach> class Node {> constructor(v) {> this>.left =>null>;> this>.right =>null>;> this>.data = v;> }> }> // Inorder Traversal> function> printInorder(root)> {> if> (root)> {> // Traverse left subtree> printInorder(root.left);> // Visit node> console.log(root.data);> // Traverse right subtree> printInorder(root.right);> }> }> // Driver code> if> (>true>)> {> // Build the tree> let root =>new> Node(100);> root.left =>new> Node(20);> root.right =>new> Node(200);> root.left.left =>new> Node(10);> root.left.right =>new> Node(30);> root.right.left =>new> Node(150);> root.right.right =>new> Node(300);> // Function call> console.log(>'Inorder Traversal:'>);> printInorder(root);> }> // This code is contributed by akashish__> |
>
>산출
Inorder Traversal: 10 20 30 100 150 200 300>
시간 복잡도: O(N), 여기서 N은 노드 수입니다.
보조 공간: O(h), 여기서 h는 트리의 높이입니다.
선주문 순회:
문제를 해결하기 위한 아이디어는 다음과 같습니다.
처음에는 방문하셔서 뿌리 그런 다음 횡단 왼쪽 하위 트리 그런 다음 횡단 오른쪽 하위 트리 .
아이디어를 구현하려면 아래 단계를 따르십시오.
- 루트를 방문하여 데이터를 인쇄합니다.
- 왼쪽 하위 트리 탐색
- 오른쪽 하위 트리 탐색
다음은 선주문 순회 구현입니다.
C++
// C++ code to implement the approach> #include> using> namespace> std;> // Class describing a node of tree> class> Node {> public>:> >int> data;> >Node* left;> >Node* right;> >Node(>int> v)> >{> >this>->데이터 = v;> >this>->왼쪽 =>this>->오른쪽 = NULL;> >}> };> // Preorder Traversal> void> printPreOrder(Node* node)> {> >if> (node == NULL)> >return>;> >// Visit Node> >cout ' '; // Traverse left subtree printPreOrder(node->왼쪽); // 오른쪽 하위 트리를 탐색합니다. printPreOrder(node->right); } // 드라이버 코드 int main() { // 트리 노드 구축* root = new Node(100); 루트->왼쪽 = 새 노드(20); 루트->오른쪽 = 새 노드(200); 루트->왼쪽->왼쪽 = new Node(10); 루트->왼쪽->오른쪽 = new Node(30); 루트->오른쪽->왼쪽 = new Node(150); 루트->오른쪽->오른쪽 = new Node(300); // 함수 호출 cout<< 'Preorder Traversal: '; printPreOrder(root); return 0; }> |
>
>
자바
// Java code to implement the approach> import> java.io.*;> // Class describing a node of tree> class> Node {> >int> data;> >Node left;> >Node right;> >Node(>int> v)> >{> >this>.data = v;> >this>.left =>this>.right =>null>;> >}> }> class> GFG {> >// Preorder Traversal> >public> static> void> printPreorder(Node node)> >{> >if> (node ==>null>)> >return>;> >// Visit node> >System.out.print(node.data +>' '>);> >// Traverse left subtree> >printPreorder(node.left);> >// Traverse right subtree> >printPreorder(node.right);> >}> >public> static> void> main(String[] args)> >{> >// Build the tree> >Node root =>new> Node(>100>);> >root.left =>new> Node(>20>);> >root.right =>new> Node(>200>);> >root.left.left =>new> Node(>10>);> >root.left.right =>new> Node(>30>);> >root.right.left =>new> Node(>150>);> >root.right.right =>new> Node(>300>);> >// Function call> >System.out.print(>'Preorder Traversal: '>);> >printPreorder(root);> >}> }> // This code is contributed by lokeshmvs21.> |
>
>
파이썬3
class> Node:> >def> __init__(>self>, v):> >self>.data>=> v> >self>.left>=> None> >self>.right>=> None> # Preorder Traversal> def> printPreOrder(node):> >if> node>is> None>:> >return> ># Visit Node> >print>(node.data, end>=> ' '>)> ># Traverse left subtree> >printPreOrder(node.left)> ># Traverse right subtree> >printPreOrder(node.right)> # Driver code> if> __name__>=>=> '__main__'>:> ># Build the tree> >root>=> Node(>100>)> >root.left>=> Node(>20>)> >root.right>=> Node(>200>)> >root.left.left>=> Node(>10>)> >root.left.right>=> Node(>30>)> >root.right.left>=> Node(>150>)> >root.right.right>=> Node(>300>)> ># Function call> >print>(>'Preorder Traversal: '>, end>=> '')> >printPreOrder(root)> |
>
>
씨#
// Include namespace system> using> System;> // Class describing a node of tree> public> class> Node> {> >public> int> data;> >public> Node left;> >public> Node right;> >public> Node(>int> v)> >{> >this>.data = v;> >this>.left =>this>.right =>null>;> >}> }> public> class> GFG> {> >// Preorder Traversal> >public> static> void> printPreorder(Node node)> >{> >if> (node ==>null>)> >{> >return>;> >}> >// Visit node> >Console.Write(node.data.ToString() +>' '>);> >// Traverse left subtree> >GFG.printPreorder(node.left);> >// Traverse right subtree> >GFG.printPreorder(node.right);> >}> >public> static> void> Main(String[] args)> >{> >// Build the tree> >var> root =>new> Node(100);> >root.left =>new> Node(20);> >root.right =>new> Node(200);> >root.left.left =>new> Node(10);> >root.left.right =>new> Node(30);> >root.right.left =>new> Node(150);> >root.right.right =>new> Node(300);> >// Function call> >Console.Write(>'Preorder Traversal: '>);> >GFG.printPreorder(root);> >}> }> |
>
베드페이지 같은 사이트
>
자바스크립트
class Node {> >constructor(v) {> >this>.data = v;> >this>.left =>this>.right =>null>;> >}> }> function> printPreOrder(node) {> >if> (node ==>null>)>return>;> >console.log(node.data +>' '>);> >printPreOrder(node.left);> >printPreOrder(node.right);> }> // Build the tree> let root =>new> Node(100);> root.left =>new> Node(20);> root.right =>new> Node(200);> root.left.left =>new> Node(10);> root.left.right =>new> Node(30);> root.right.left =>new> Node(150);> root.right.right =>new> Node(300);> console.log(>'Preorder Traversal: '>);> printPreOrder(root);> // This code is contributed by akashish__> |
>
>산출
Preorder Traversal: 100 20 10 30 200 150 300>
시간 복잡도: O(N), 여기서 N은 노드 수입니다.
보조 공간: O(H), 여기서 H는 트리의 높이입니다.
우편 주문 순회:
문제를 해결하기 위한 아이디어는 다음과 같습니다.
처음에는 트래버스 왼쪽 하위 트리 그런 다음 횡단 오른쪽 하위 트리 그런 다음 뿌리 .
아이디어를 구현하려면 아래 단계를 따르십시오.
- 왼쪽 하위 트리 탐색
- 오른쪽 하위 트리 탐색
- 루트를 방문하여 데이터를 인쇄합니다.
다음은 후순위 순회 구현입니다.
C++
// C++ code to implement the approach> #include> using> namespace> std;> // Class to define structure of a node> class> Node {> public>:> >int> data;> >Node* left;> >Node* right;> >Node(>int> v)> >{> >this>->데이터 = v;> >this>->왼쪽 =>this>->오른쪽 = NULL;> >}> };> // PostOrder Traversal> void> printPostOrder(Node* node)> {> >if> (node == NULL)> >return>;> >// Traverse left subtree> >printPostOrder(node->왼쪽);> >// Traverse right subtree> >printPostOrder(node->오른쪽);> >// Visit node> >cout ' '; } // Driver code int main() { Node* root = new Node(100); root->왼쪽 = 새 노드(20); 루트->오른쪽 = 새 노드(200); 루트->왼쪽->왼쪽 = new Node(10); 루트->왼쪽->오른쪽 = new Node(30); 루트->오른쪽->왼쪽 = new Node(150); 루트->오른쪽->오른쪽 = new Node(300); // 함수 호출 cout<< 'PostOrder Traversal: '; printPostOrder(root); cout << '
'; return 0; }> |
>
>
자바
// Java code to implement the approach> import> java.io.*;> // Class describing a node of tree> class> GFG {> > >static> class> Node {> >int> data;> >Node left;> >Node right;> >Node(>int> v)> >{> >this>.data = v;> >this>.left =>this>.right =>null>;> >}> }> >// Preorder Traversal> >public> static> void> printPreorder(Node node)> >{> >if> (node ==>null>)> >return>;> >// Traverse left subtree> >printPreorder(node.left);> >// Traverse right subtree> >printPreorder(node.right);> > >// Visit node> >System.out.print(node.data +>' '>);> >}> >public> static> void> main(String[] args)> >{> >// Build the tree> >Node root =>new> Node(>100>);> >root.left =>new> Node(>20>);> >root.right =>new> Node(>200>);> >root.left.left =>new> Node(>10>);> >root.left.right =>new> Node(>30>);> >root.right.left =>new> Node(>150>);> >root.right.right =>new> Node(>300>);> >// Function call> >System.out.print(>'Preorder Traversal: '>);> >printPreorder(root);> >}> }> |
>
>
씨#
// Include namespace system> using> System;> // Class describing a node of tree> public> class> Node> {> >public> int> data;> >public> Node left;> >public> Node right;> >public> Node(>int> v)> >{> >this>.data = v;> >this>.left =>this>.right =>null>;> >}> }> public> class> GFG> {> >// Preorder Traversal> >public> static> void> printPreorder(Node node)> >{> >if> (node ==>null>)> >{> >return>;> >}> >// Traverse left subtree> >GFG.printPreorder(node.left);> >// Traverse right subtree> >GFG.printPreorder(node.right);> >// Visit node> >Console.Write(node.data.ToString() +>' '>);> >}> >public> static> void> Main(String[] args)> >{> >// Build the tree> >var> root =>new> Node(100);> >root.left =>new> Node(20);> >root.right =>new> Node(200);> >root.left.left =>new> Node(10);> >root.left.right =>new> Node(30);> >root.right.left =>new> Node(150);> >root.right.right =>new> Node(300);> >// Function call> >Console.Write(>'Preorder Traversal: '>);> >GFG.printPreorder(root);> >}> }> |
>
>
파이썬3
class> Node:> >def> __init__(>self>, v):> >self>.data>=> v> >self>.left>=> None> >self>.right>=> None> # Preorder Traversal> def> printPostOrder(node):> >if> node>is> None>:> >return> ># Traverse left subtree> >printPostOrder(node.left)> ># Traverse right subtree> >printPostOrder(node.right)> > ># Visit Node> >print>(node.data, end>=> ' '>)> # Driver code> if> __name__>=>=> '__main__'>:> ># Build the tree> >root>=> Node(>100>)> >root.left>=> Node(>20>)> >root.right>=> Node(>200>)> >root.left.left>=> Node(>10>)> >root.left.right>=> Node(>30>)> >root.right.left>=> Node(>150>)> >root.right.right>=> Node(>300>)> ># Function call> >print>(>'Postorder Traversal: '>, end>=> '')> >printPostOrder(root)> |
>
>
자바스크립트
class Node {> >constructor(v) {> >this>.data = v;> >this>.left =>null>;> >this>.right =>null>;> >}> }> // Preorder Traversal> function> printPostOrder(node) {> >if> (node ===>null>) {> >return>;> >}> >// Traverse left subtree> >printPostOrder(node.left);> >// Traverse right subtree> >printPostOrder(node.right);> >// Visit Node> >console.log(node.data, end =>' '>);> }> // Driver code> // Build the tree> let root =>new> Node(100);> root.left =>new> Node(20);> root.right =>new> Node(200);> root.left.left =>new> Node(10);> root.left.right =>new> Node(30);> root.right.left =>new> Node(150);> root.right.right =>new> Node(300);> // Function call> console.log(>'Postorder Traversal: '>, end =>''>);> printPostOrder(root);> // This code is contributed by akashish__> |
>
>산출
PostOrder Traversal: 10 30 20 150 300 200 100>
시간 복잡도: O(N), 여기서 N은 노드 수입니다.
보조 공간: O(H), 여기서 H는 트리의 높이입니다.