线索二叉树

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <string.h>
  4 #include <vector>
  5 #include <stack>
  6 #include <algorithm>
  7 using namespace std;
  8 
  9 typedef enum{
 10     Thread,
 11     Link
 12 }Tag;
 13 
 14 typedef struct Node
 15 {
 16     int data;
 17     struct Node * lchild;
 18     struct Node * rchild;
 19     Tag rtag;
 20     Tag ltag;
 21 } Node;
 22 
 23 Node *createNode(int data, Node * l = NULL, Node * r = NULL)
 24 {
 25     Node * res = (Node *)malloc(sizeof(Node));
 26     res->data = data;
 27     res->lchild = l;
 28     res->rchild = r;
 29     res->rtag = Link;
 30     res->ltag = Link;
 31     return res;
 32 }
 33 
 34 
 35 Node * createTree(Node * &root, int x)
 36 {
 37     if (root == NULL){
 38         root = createNode(x, NULL, NULL);
 39         return root;
 40     }
 41     Node * p = root;
 42     Node * q = NULL;
 43     while(p != NULL){
 44         q = p;
 45         if ( x > p->data ){
 46             p = p->rchild;
 47         }
 48         else {
 49             p = p->lchild;
 50         }
 51     }
 52     if ( x > q->data) q->rchild = createNode(x);
 53     else q->lchild = createNode(x);
 54     return root;
 55 }
 56 
 57 void print(Node * root)
 58 {
 59     if (root == NULL) return;
 60     print(root->lchild);
 61     printf("%d\n", root->data);
 62     print(root->rchild);
 63 }
 64 
 65 void mprint(Node * root)
 66 {
 67     Node * p = root;
 68     stack<Node *> st;
 69     st.push(root);
 70     while (!st.empty()) {
 71         if (st.top() == NULL) {
 72             st.pop();
 73             if (!st.empty()) {
 74                 printf("%d\n", st.top()->data);    
 75                 Node * temp = st.top();
 76                 st.pop();
 77                 st.push(temp->rchild);
 78             }
 79         }
 80         else {
 81             st.push(st.top()->lchild);
 82         }
 83     }
 84 }
 85 
 86 void threadTree(Node *&prev, Node *root) {
 87     if (root == NULL) return;
 88     threadTree(prev, root->lchild);
 89     if (root->lchild == NULL) {
 90         root->lchild = prev;
 91         root->ltag = Thread;
 92     }
 93     if (prev != NULL && prev->rchild == NULL) {
 94         prev->rchild = root;
 95         prev->rtag = Thread;
 96     }
 97     prev = root;
 98     threadTree(prev, root->rchild);
 99 }
100 
101 
102 int inThreadTreePrint(Node * root) {
103     Node * p = root;
104     while(p) {
105         if (p->lchild != NULL && p->ltag != Thread)
106             p = p->lchild;
107         else {
108             printf("%d\n", p->data);
109             while (p->rchild != NULL && p->rtag == Thread) {
110                 p = p->rchild;
111                 printf("%d\n", p->data);
112             }
113             p = p->rchild;
114         }
115     }
116 }
117 
118 
119 
120 int main(void)
121 {
122     Node *root = NULL;
123     createTree(root, 5);
124     createTree(root, 4);
125     createTree(root, 9);
126     createTree(root, 7);
127     createTree(root, 1);
128     createTree(root, 2);
129     Node * prev = NULL;
130     threadTree(prev, root);
131     printf("%d ", root->lchild->data);
132     if (root->lchild->lchild) printf("%d ", root->lchild->lchild->data);
133     else printf("NULL ");
134     if (root->rchild->lchild->rchild) printf("%d ", root->rchild->lchild->rchild->data);
135     else printf("NULL ");
136     printf("\n");
137     printf("----------------------------------------------------\n");
138     inThreadTreePrint(root);
139     return 0;
140 }