Threaded Binary Tree

yaojingguo

#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;}