제 1 장 기본 개념

Transcription

1 이진트리순회와트리반복자 트리순회 (tree traversal) 트리에있는모든노드를한번씩만방문 순회방법 : LVR, LRV, VLR, VRL, RVL, RLV L : 왼쪽이동, V : 노드방문, R : 오른쪽이동 왼쪽을오른쪽보다먼저방문 (LR) LVR : 중위 (inorder) 순회 VLR : 전위 (preorder) 순회 LRV : 후위 (postorder) 순회 산술식의이진트리표현 + E D / 1

2 이진트리순회와트리반복자 1 template <class T> 2 void Tree<T>::Inorder() 3 {// Driver calls workhorse for traversal of entire tree. The driver is 4 // declared as a public member function of Tree. 5 Inorder(root); 6 7 template <class T> 8 void Tree<T>::Inorder(TreeNode<T> currentnode) 9 {// Workhorse traverses the subtree rooted at currentnode. 10 // The workhorse is declared as a private member function of Tree. 11 if (currentnode) { 12 Inorder(currentNode->lefthild); 13 Visit(currentNode); 14 Inorder(currentNode->righthild);

3 Inorder traversal ( 중위순회 ) 호출 currentnode 의값조치호출 currentnode 의값 조치 Driver / 0 0 / 0 0 cout<< cout<< / cout<< cout<< 출력 : /D+E Driver D 0 D 0 + E 0 E 0 cout<< cout<< cout<< D cout<< + cout<< E / + D 3 E

4 Preorder Traversal ( 전위순회 ) Program 5.2:Preorder traversal of a binary tree 1 template <class T> 2 void Tree<T>::Preorder() 3 {// Driver. 4 Preorder(root); 5 6 template <class T> 7 void Tree<T>::Preorder(TreeNode<T> currentnode) 8 {// Workhorse. 9 if (currentnode) { 10 Visit(currentNode); 11 Preorder(currentNode->lefthild); 12 Preorder(currentNode->righthild); 출력 : +/DE / + D 4 E

5 Postorder Traversal ( 전위순회 ) 1 template <class T> 2 void Tree<T>::Postorder() 3 {// Driver. 4 Postorder(root); 5 6 template <class T> 7 void Tree<T>::Postorder(TreeNode<T> currentnode) 8 {// Workhorse. 9 if (currentnode) { 10 Postorder(currentNode->lefthild); 11 Postorder(currentNode->righthild); 12 Visit(currentNode); D E 출력 : /DE+ / 5

6 비순환중위순회 1 template <class T> 2 void Tree<T>::NonrecInorder() 3 {// Nonrecursive inorder traversal using a stack. 4 Stack<TreeNode<T>> s; // declare and initialize stack 5 TreeNode<T> currentnode = root; 6 while(1) { 7 while (currentnode) { // move down lefthild fields 8 s.push(currentnode); // add to stack 9 currentnode = currentnode->lefthild; if (s.isempty()) return; 12 currentnode = s.top(); 13 s.pop(); // delete from stack 14 Visit(currentNode); 15 currentnode = currentnode->righthild;

7 Level Order Traversal( 레벨순서순회 ) 큐사용 루트방문 -> 왼쪽자식방문 -> 오른쪽자식방문 + E D / + template <class T> void Tree<T>::LevelOrder() {// 이진트리의레벨순서순회 Queue<TreeNode<T>> q; TreeNode<T> currentnode = root; while(currentnode){ Visit(currentNode); if(currentnode->lefthild) q.push(currentnode->lefthild); if(currentnode->righthild) q.push(currentnode->righthild); if(q.isempty()) return; currentnode = q.front(); q.pop(); / D E 7

8 스택없는순회 각노드에 parent ( 부모 ) 필드추가 스택을사용하지않아도루트노드로올라갈수있음 root 스레드 (thread) 이진트리로표현 각노드마다두비트필요 lefthild필드와 righthild 필드를루트로돌아갈수있는경로를유지하도록사용 경로상의주소스택은리프노드에저장 D E 0 0 F 0 0 G 0 0 H 0 0 I 0 root D E F G H I 8

9 이진트리의추가연산 복사 : 프로그램 5.9 동일성검사 : 프로그램 5.10 재귀함수로구현 만족성문제 변수 x 1, x 2,, x n 과연산자,, 으로이루어진식 변수 = { 참, 거짓 규칙 (1) 변수도하나의식 (2) x, y가식일때, x, x y, x y 도식 (3) 연산순서는,, 순, 괄호사용 명제해석식 (formula of propositional calculus) 위규칙을이용해서구성한식 x x ) 1 ( 2 x3 9

10 template <class T> Tree<T>::Tree(T data, TreeNode<T> lhild, TreeNode<T> rhild) : data(d), lefthild(lhild), righthild(rhild) { Program 5.9:opying a binary tree template <class T> Tree<T>::Tree(const Tree<T>& s) // driver {// opy constructor root = opy(s.root); template <class T> TreeNode<T> Tree<T>::opy(TreeNode<T> orignode) // Workhorse {// Return a pointer to an exact copy of the binary tree rooted at orignode. if (!orignode) return 0; else return new TreeNode<T>(origNode->data, opy(orignode->lefthild), opy(orignode->righthild));

11 Program 5.10:inary tree equivalence template <class T> bool Tree<T>::operator==(const Tree& t) const { return Equal(root, t.root); template <class T> bool Tree<T>::Equal(TreeNode<T> a, TreeNode<T> b) {// Workhorse. if ((!a) && (!b)) return true; // both a and b are 0 else return (a && b // both a and b are non-zero && (a->data == b->data) // data is the same && Equal(a->lefthild, b->lefthild) // left subtrees equal && Equal(a->righthild, b->righthild)); // right subtrees equal

12 만족성문제 (1) 명제식의만족성 (satisfiability) 문제 식의값이 true 가되도록, 변수에값을지정할수있는방법이있는가? 1 x2) ( x1 x3) ( x x 3 x 3 x 1 x 3 x 2 x 1 12

13 만족성문제 (2) 가능한모든 true 와 false 의조합을대입 : O(g 2 n ) g : 식을계산하는데필요한시간 전체식이하나의값이될때까지서브트리를계산하면서트리후위순회 x 1 x 2 x 3 formular T T T? T T F? T F T? T F F? F T T? F T F? F F T? F F F? x 1 x 3 x 3 x 2 x 1 x 1x2 x x1 x3 3 13

14 만족성문제 (3) 후위순회계산 Tree 템플릿클래스를 T=pair<Operator, bool> 로인스턴스화 enum Operator { Not, nd, Or, True, False; for n 개변수에대한 2 n 개의가능한참값조합 { 다음조합을생성 ; 그들의값을변수에대입 ; 명제식을나타내는트리를후위순회로계산 ; if(formula.data().second()){cout << current combination; return; cout << no satisfiable combination ; // visit the node pointed at by p switch (p->data.first) { case Not: p->data.second =!p->righthild->data.second; break; case nd: p->data.second = p->lefthild->data.second && p->righthild->data.second; break; case Or: p->data.second = p->lefthild->data.second p->righthild->data.second; break; case True: p->data.second = true; break; case False: p->data.second = false; 14

15 Thread (1) n 노드이진트리의연결표현 총링크의수 : 2n null 링크의수 : n+1 > null이아닌링크수 n-1 root D 0 E 0 0 F 0 0 G 0 0 H 0 0 I 0 15

16 Thread (2) 스레드 (Thread) 0 링크필드를다른노드를가리키는포인터로대치 if p->righthild == 0, p->righthild = p의중위후속자에대한포인터 if p->lefthild = 0, p->lefthild = p의중위선행자에대한포인터 root D E F G H I 순회 : H D I E F G 16

17 Thread (3) 노드구조 : leftthread 와 righthild 의 tag 필드를사용 leftthread == false : lefthild 포인터 == true : lefthild 스레드 rightthread == false : righthild 포인터 == true : righthild 스레드 헤드노드 연결되지않은스레드제거 leftthread lefthild data righthild rightthread TRUE FLSE 17

18 스레드이진트리의메모리표현 root f - f f f f f f f f D f t E t t F t t G t t H t t I t f = false; t = true 18

19 스레드이진트리의중위순회 스택을이용하지않고중위순회가능 중위순회의후속자 x->rightthread == true : x->righthild == false : 오른쪽자식의왼쪽자식링크를따라가서 LeftThread==true인노드 스레드이진트리에서중위후속자를찾는함수 T ThreadedInorderIterator::Next() {// 스레드이진트리에서 currentnode 의중위후속자를반환 ThreadedNode<T> temp = currentnode->righthild; if(!currentnode->rightthread) while(!temp->leftthread) temp = temp->lefthild; currentnode = temp; if(currentnode == root) return 0; else return &currentnode->data; 19

20 스레드이진트리에서의노드삽입 s 의오른쪽자식으로 r 을삽입 20

21 Program 5.14:Inserting r as the right child of s template <class T> void ThreadedTree<T>::InsertRight(ThreadedNode<T> s, ThreadedNode<T> r) {// Insert r as the right child of s. r->righthild = s->righthild; r->rightthread = s->rightthread; r->lefthild = s; r->leftthread = true; // lefthild is a thread s->righthild = r; s->rightthread = false; if (! r->rightthread) { ThreadedNode<T> temp = InorderSucc(r); // returns the inorder successor of r temp->lefthild = r; 21