Threaded Binary Tree
#include <stdio.h>enum pointer_tag { LINK, THREAD };struct node {char* data;struct node* lchild;struct node* rchild;enum pointer_tag ltag, rtag;};void visit(char* data) {printf("%s ", data);}void traverse(struct node* head) {struct node* p = head->lchild;while (p != head) { while (p->ltag == LINK) p = p->lchild; visit(p->data); while (p->rtag == THREAD && p->rchild != head) { p = p->rchild; visit(p->data); } p = p->rchild;}printf("\n");}void set_node(struct node* node, char * data, struct node* lchild, struct node* rchild, enum pointer_tag ltag, enum pointer_tag rtag) {node->data = data;node->lchild = lchild;node->rchild = rchild;node->ltag = ltag;node->rtag = rtag;}/* * + * / \ * a b */void test_1() {struct node root, node1, node2, node3;set_node(&root, "r", &node1, &node3, LINK, THREAD);set_node(&node1, "+", &node2, &node3, LINK, LINK);set_node(&node2, "a", &root, &node1, THREAD, THREAD);set_node(&node3, "b", &node1, &root, THREAD, THREAD);traverse(&root);}/* * - * / \ * / \ * + "/" * / \ / \ *a *e f * / \ * b - * / \ * c d */void test_2() {struct node root, node1, node2, node3, node4, node5, node6, node7, node8, node9, node10, node11;set_node(&root, "r", &node1, &node7, LINK, THREAD);set_node(&node1, "-", &node2, &node3, LINK, LINK);set_node(&node2, "+", &node4, &node5, LINK, LINK);set_node(&node3, "/", &node6, &node7, LINK, LINK);set_node(&node4, "a", &root, &node2, THREAD, THREAD);set_node(&node5, "*", &node8, &node9, LINK, LINK);set_node(&node6, "e", &node1, &node3, THREAD, THREAD);set_node(&node7, "f", &node3, &root, THREAD, THREAD);set_node(&node8, "b", &node2, &node5, THREAD, THREAD);set_node(&node9, "-", &node10, &node11, LINK, LINK);set_node(&node10, "c", &node5, &node9, THREAD, THREAD);set_node(&node11, "d", &node9, &node1, THREAD, THREAD);traverse(&root);}int main(int argc, const char *argv[]) {test_1();test_2();return 0;}
页:
[1]