1.
void inorder(tree_ptr ptr) { if(ptr) { inorder(ptr->left_child); printf( %d,ptr->data); inorder(ptr->right_child);
2) => A / B * C * D + E ()
A / B * C * D + E
void preorder(tree_ptr ptr) { if(ptr) { printf( %d, ptr->data); preorder(ptr->left_child); preorder(ptr->right_child);
void postorder(tree_ptr ptr) { if(ptr) { postorder(ptr->left_child); postorder(ptr->right_child); printf( %d, ptr->data);
/* 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;
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
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;
2. (Threaded) left_child data right_child data left_child right_child
- ptr->left_thread = ptr->left_child - ptr->left_thread = ptr->left_child - ptr->right_thread = ptr->right_child - ptr->right_thread = ptr->right_child
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
left_thread left_child data right_child right_thread TRUE FALSE
root f = FALSE t = TRUE
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);
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;
root root parent parent child child
root root parent parent child child
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;
/* 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)));
Review