이진트리 순회 트리내의 모든 노드를 특정 순서에 따라 한번씩 방문 하는 것 방문 순서 R: Moving Right Child

Presentation on theme: "이진트리 순회 트리내의 모든 노드를 특정 순서에 따라 한번씩 방문 하는 것 방문 순서 R: Moving Right Child"— Presentation transcript:

1 이진트리 순회 트리내의 모든 노드를 특정 순서에 따라 한번씩 방문 하는 것 방문 순서 R: Moving Right Child
L: Moving Left Child V: Visiting Node Inorder Traversal(중위 순회) LVR(RVL) Preorder Traversal(전위 순회) VLR(VRL) Postorder Traversal(후위순회) LRV(RLV)

2 이진트리 순회 중위 순회(inorder traversal) 1. 널 노드에 도달할 때까지 왼쪽 방향으로 이동
2. 널 노드에 도착하면 널 노드의 부모 방문 3. 순회는 오른쪽 방향으로 계속 4. 오른쪽으로 이동할 수 없을 때에는 바로 위 레벨의 방문하지 않은 노드에서 순회 계속 A B C E F G H D 1 2 3 6 4 void inorder(TreeNode *root){ /* 중위 트리 순회 */ if (root){ inorder(root->left); printf("%d ", root->data); inorder(root->right); } 5

3 이진트리 순회 중위 순회(inorder traversal) A B C E F G H D 1 2 3 6 4 5 IN(NULL){
return } IN(a의 주소){ IN(p->lchild); PF("%c ",p->data); IN(p->rchild); } IN(b의 주소){ IN(p->lchild); PF("%c ",p->data); IN(p->rchild); } IN(c의 주소){ IN(p->lchild); PF("%c ",p->data); IN(p->rchild); } IN(e의 주소){ IN(p->lchild); PF("%c ",p->data); IN(p->rchild); } IN(NULL){ return } IN(NULL){ return } IN(NULL){ return } IN(d의 주소){ IN(p->lchild); PF("%c ",p->data); IN(p->rchild); } IN(f의 주소){ IN(p->lchild); PF("%c ",p->data); IN(p->rchild); } IN(NULL){ return } IN(NULL){ return } A B C E F G H D 1 IN(NULL){ return } IN(g의 주소){ IN(p->lchild); PF("%c ",p->data); IN(p->rchild); } IN(h의 주소){ IN(p->lchild); PF("%c ",p->data); IN(p->rchild); } 2 IN(NULL){ return } 3 6 4 IN(NULL){ return } 5

4 이진트리 순회 중위 순회(inorder traversal) 예
void inorder(TreeNode *root){ /* 중위 트리 순회 */ if (root){ inorder(root->left); printf("%c", root->data); inorder(root->right); } - * C Void main(){ TreeNode a, b, c, o1, o2; a.data='A'; a.left= a.right= NULL; b.data='B'; b.left= b.right= NULL; c.data='C'; c.left= c.right= NULL; o2.data= '*'; o2.left=&a; o2.right=&b; o1.data= '-'; o1.left=&o2; o1.right=&c; inorder(&o1); } A B

5 이진트리 순회 전위 순회(preorder traversal)
1. 노드를 먼저 방문 2. 왼쪽 가지의 모든 노드 방문 3. 널 노드에 도달하면 오른쪽 자식을 가진 가장 가까운 조상으로 돌아가서 오른쪽 자식에서 순회를 계속 A B C E F G H D 1 2 3 6 4 5 void preorder(TreeNode *root){ /* 전위 트리 순회 */ if (root){ printf("%d", root->data); preorder(root->left); preorder(root->right); }

6 이진트리 순회 전위 순회(preorder traversal) A B C E F G H D PR(NULL){ return }
PR(a의 주소){ PF("%c ",p->data); PR(p->lchild); PR(p->rchild); } PR(b의 주소){ PF("%c ",p->data); PR(p->lchild); PR(p->rchild); } PR(c의 주소){ PF("%c ",p->data); PR(p->lchild); PR(p->rchild); } PR(e의 주소){ PF("%c ",p->data); PR(p->lchild); PR(p->rchild); } PR(NULL){ return } PR(NULL){ return } PR(NULL){ return } PR(d의 주소){ PF("%c ",p->data); PR(p->lchild); PR(p->rchild); } PR(f의 주소){ PF("%c ",p->data); PR(p->lchild); PR(p->rchild); } PR(NULL){ return } PR(NULL){ return } A B C E F G H D 1 PR(NULL){ return } PR(g의 주소){ PF("%c ",p->data); PR(p->lchild); PR(p->rchild); } PR(h의 주소){ PF("%c ",p->data); PR(p->lchild); PR(p->rchild); } 2 PR(NULL){ return } 3 6 4 IN(NULL){ return } 5

7 이진트리 순회 후위 순회(postorder traversal)
1. 노드를 방문하기 전에 두 자식을 먼저 방문노드 보다 그 노드의 자식이 먼저 출력 A B C E F G H D 1 2 void postorder(TreeNode *root){ if (root){ postorder(root->left); postorder(root->right); printf("%c ", root->data); } 3 6 4 5

8 이진트리 순회 후위 순회(postorder traversal) PR(NULL){ return } A B C E F G H D
PR(a의 주소){ PR(p->lchild); PR(p->rchild); PF("%c ",p->data); } PR(b의 주소){ PR(p->lchild); PR(p->rchild); PF("%c ",p->data); } PR(c의 주소){ PR(p->lchild); PR(p->rchild); PF("%c ",p->data); } PR(e의 주소){ PR(p->lchild); PR(p->rchild); PF("%c ",p->data); } PR(NULL){ return } PR(NULL){ return } PR(NULL){ return } PR(d의 주소){ PR(p->lchild); PR(p->rchild); PF("%c ",p->data); } PR(f의 주소){ PR(p->lchild); PR(p->rchild); PF("%c ",p->data); } PR(NULL){ return } PR(NULL){ return } A B C E F G H D 1 PR(NULL){ return } PR(g의 주소){ PR(p->lchild); PR(p->rchild); PF("%c ",p->data); } PR(h의 주소){ PR(p->lchild); PR(p->rchild); PF("%c ",p->data); } 2 PR(NULL){ return } 3 6 4 IN(NULL){ return } 5