untitled

Size: px

Start display at page:

Download "untitled"

서택 모
8 years ago
Views:

2 1.

4 void inorder(tree_ptr ptr) { if(ptr) { inorder(ptr->left_child); printf( %d,ptr->data); inorder(ptr->right_child);

7 2) => A / B * C * D + E ()

8 A / B * C * D + E

9 void preorder(tree_ptr ptr) { if(ptr) { printf( %d, ptr->data); preorder(ptr->left_child); preorder(ptr->right_child);

10 void postorder(tree_ptr ptr) { if(ptr) { postorder(ptr->left_child); postorder(ptr->right_child); printf( %d, ptr->data);

11 /* iterative inorder tree traversal */ void iter_inorder(tree_ptr node) { int top = -1; tree_ptr stack[max_stack_size]; while(1) { while(node) { push(&top, node); node = node->left_child; node = pop(&top); if(!node) break; printf( %d, node->data); node = node->right_child;

$while(node) { push(&top, node); node = node->left_child; node =$

13 void level_order(tree_ptr ptr) { int front = rear = 0; tree_ptr queue[max_queue_size]; if(!ptr) return; add(front,&rear,ptr); for(;;) { ptr = delete(&front, rear); if(ptr) { printf( %d, ptr->data); if(ptr->left_child) add(front,&rear,ptr->left_child); if(ptr->right_child) add(front, &rear,ptr->right_child); else break;

$if(ptr) { printf( %d, ptr->data); if(ptr->left_child)$

14 2. (Threaded) left_child data right_child data left_child right_child

16 - ptr->left_thread = ptr->left_child - ptr->left_thread = ptr->left_child - ptr->right_thread = ptr->right_child - ptr->right_thread = ptr->right_child

17 struct tnode { ; short int left_thread; struct tnode *left_child; char data; struct tnode *right_child; short int right_thread; typedef struct tnode threaded_tree; typedef threaded_tree *threaded_ptr; left_thread left_child data right_child right_thread

right_thread; typedef struct tnode threaded_tree; typedef

18 left_thread left_child data right_child right_thread TRUE FALSE

19 root f = FALSE t = TRUE

21 threaded_ptr insucc(threaded_ptr tree) { threaded_ptr temp; temp = tree->right_child; if(!tree->right_thread) while(!temp->left_thread) temp = temp->left_child; return temp; void tinorder(threaded_ptr tree) { threaded_ptr temp = tree; for(;;) { temp = insucc(temp); if(temp = tree) break; printf( %3c, temp->data);

23 void insert_right(threaded_ptr parent, threaded_ptr child) { threaded_ptr temp; child->right_child=parent->right_child; (4) child->right_thread=parent->right_thread; (2) child->left_child=parent; (3) child->left_thread=true; (2) parent->right_child=child; (5) parent->right_thread=false; (1) if(!child->right_thread) { /* */ temp=insucc(child); temp->left_child=child;

24 root root parent parent child child

25 root root parent parent child child

26 3. /* program copy() */ tree_ptr copy(tree_ptr original) { tree_ptr temp; if(original) { temp = (tree_ptr)malloc(sizeof(node)); if(is_full(temp)) exit(1); temp->left_child = copy(original->left_child); temp->right_child = copy(original->right_child); temp->data = original->data; return temp; return NULL;

27 /* program equal() */ int equal(tree_ptr first,tree_ptr second) { return ((!first &&!second) (first && second && (first->data == second->data) && equal(first->left_child, second->left_child) && equal(first->right_child, second->right_child)));

28 Review

슬라이드 제목 없음

슬라이드 제목 없음 Chapter 5: TREES Trees Trees Def) a tree is finite set of one or more nodes such that 1) there is a special node (root) 2) remaining nodes are partitioned into n 0 disjoint trees T 1,T 2,,T n where each