tree5 Fundamentals of Data Structure - Binary Search Tree(ADT 5.3) #Binary Search Tree : Binary Tree로 비어 있는 트리일 수도 있고, 비어있지 않다면 다음과 같은 특성을 가진다. 1. 각 노드는 하나의 키를 가지며, 키들은 구별된다. 2. 루트를 기준으로 왼쪽 서브트리에 있는 키들은 루트의 키값보다 작다. 3. 루트를 기준으로 오른쪽 서브트리에 있는 키들은 루트의 키값보다 크다. 4. 왼쪽이나 오른쪽 서브트리도 마찬가지로 Binary Search Tree이며 위의 특성을 가진다. ※ 4번 특성으로 Binary Search Tree는 Recursive임을 알 수 있다. / 또한 Complete Binary Tree가 아니다. #Dictionary : a collection of n > 0 pairs, each pair has a key and a.. 2015. 8. 10. Fundamentals of Data Structure - Heaps #Heaps- 힙이란 주로 Priority Queue를 구현할 때 사용되는 것으로, TreeNode의 Data들을 오름차순, 혹은 내림차순 식으로 Root부터 Leaf까지 Binary Tree로 구현한 것을 말한다. 또한, 여러 종류의 heap들이 있지만 이번 Chapter에서는 Max heap 과 Min heap들만을 다루겠다.- Max Heap은 Max Tree라고도 하며, 각 노드의 값들은 Child 노드들의 값보다 작지 않은 형태를 띄고 있다. 그래서 Root Node의 값이 Tree내의 값들 중에서 가장 큰 값이며, 또한 이 트리는 Complete Binary Tree이다. Min heap은 그 반대의 것을 생각하면 된다.- 아래 구현할 heap은 Array를 기반으로 하며 Lemma 5.4를 .. 2015. 8. 6. Fundamentals of Data Structure - Threaded Binary Trees #Threads: Threads 란 A.J. Perlis 와 C. Thornton이 고안한 방법으로 Left child와 Right child를 NULL형태로 비효율적이게 낭비하는 것이 아닌 다른 방법으로 쓰이게끔 하는 방법이다. 이 개념은 정해진 규칙이 있다.첫 번째 : 만약 bt->leftchild가 NULL이라면, Tree를 inorder traversal 했을시 leftchild의 전 Node를 가르키게 한다. 예를 들어, Root가 A이고 B가 A의 Leftchild, C가 A의 Rightchild인 Tree가 있다고 가정하면, C의 LeftChild는 NULL이므로, Threads이용시 이 값은 A를 가르키게 된다.두 번째 : 만약 bt->rightchild가 NULL이라면, inorder t.. 2015. 8. 4. Fundamentals of Data Structure - Tree Traversal Tree Traversal이전에 포스팅했던 Binary_Tree ADT를 기초하여 Traversal을 구현하였다. Traversal 헤더파일 // // Traversal.h // BinaryTree // // Created by Skia on 2015. 8. 4.. // Copyright (c) 2015년 Skia. All rights reserved. // #ifndef __BinaryTree__Traversal__ #define __BinaryTree__Traversal__ #include "BinTree.h" void Inorder(BinTree* bt); void Postorder(BinTree* bt); void Preorder(BinTree* bt); #endif /* defined(__Bin.. 2015. 8. 4. Fundamentals of Data Structure - ADT 5.1 ADT 5.1 : Binary_TreeBinTree 헤더파일 // // BinTree.h // BinaryTree // // Created by Skia on 2015. 8. 4.. // Copyright (c) 2015년 Skia. All rights reserved. // #ifndef __BinaryTree__BinTree__ #define __BinaryTree__BinTree__ #include typedef enum { FALSE = 0, TRUE = 1} Bool; typedef struct _element{ int data; }element; typedef struct _binTree{ element item; struct _binTree* left; struct _binTree* righ.. 2015. 8. 4. 이전 1 다음
