algorithm
이진 트리 순회
수색…
소개
특정 순서로 이진 트리의 노드를 방문하는 것을 트래버스라고합니다.
이진 트리의 선주문, Inorder 및 Post Order 순회
이진 트리를 고려하십시오.
선주문 순회 (루트) 는 노드를 가로 지르고 노드의 하위 트리를 마친 다음 노드의 오른쪽 하위 트리를 남깁니다.
따라서 트리의 선주문 통과는 다음과 같습니다.
1 2 4 5 3 6 7
순서 순회 (루트) 는 노드의 왼쪽 하위 트리를 통과 한 다음 노드의 오른쪽 하위 트리를 통과합니다.
따라서 위 트리의 순차 트래킹은 다음과 같습니다.
4 2 5 1 6 3 7
순차적 순회 (루트) 는 노드의 왼쪽 하위 트리를 통과 한 다음 오른쪽 하위 트리를 통과 한 다음 노드를 통과합니다.
따라서 위 트리의 순차적 순회는 다음과 같습니다.
4 5 2 6 7 3 1
레벨 순서 트래버 설 - 구현
예를 들어, 지정된 트리가 다음의 경우 :
레벨 순서 트래버 설은
1 2 3 4 5 6 7
레벨별로 노드 데이터를 인쇄합니다.
암호:
#include<iostream>
#include<queue>
#include<malloc.h>
using namespace std;
struct node{
int data;
node *left;
node *right;
};
void levelOrder(struct node *root){
if(root == NULL) return;
queue<node *> Q;
Q.push(root);
while(!Q.empty()){
struct node* curr = Q.front();
cout<< curr->data <<" ";
if(curr->left != NULL) Q.push(curr-> left);
if(curr->right != NULL) Q.push(curr-> right);
Q.pop();
}
}
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
int main(){
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);
printf("Level Order traversal of binary tree is \n");
levelOrder(root);
return 0;
}
큐 데이터 구조는 위의 목적을 달성하는 데 사용됩니다.
Modified text is an extract of the original Stack Overflow Documentation
아래 라이선스 CC BY-SA 3.0
와 제휴하지 않음 Stack Overflow