struct Node 
{ 
  int data; 
  bool leftTag; 
  bool rightTag; 
  Node* left; 
  Node* right; 
  Node(int _data):data(_data),left(0),right(0),leftTag(false),rightTag(false){} 
}; 

class BinaryTree 
{ 
private: 
  Node* root; 
private: 
  Node* head; 
  Node* pre; 
  void makeThread(Node* node); 
public: 
  void buildThread(); 
  void traverseBySuccessor(); 
  void traverseByPredecessor(); 
 
// helper methods 
private: 
  static inline bool visit(Node* T) 
  { 
    if (T) 
    { 
      printf("data:%c, left:%c, right:%c\n", 
        (char)T->data, 
        (T->left!=0) ? (char)T->left->data : '#', 
        (T->right!=0) ? (char)T->right->data : '#'); 
      return true; 
    } 
    else return false; 
  } 
}; 

void BinaryTree::makeThread(Node* node) 
{ 
  if (node!=NULL) 
  { 
    makeThread(node->left); 
    if (pre!= NULL) 
    { 
      if (pre->right==NULL) // 如果前驱节点的右子树为空, 那么把前驱节点的右子树用作线索 
      { 
        pre->rightTag = true;  
        pre->right = node; 
      } 
      else pre->rightTag = false; 
    } 
    if (node->left==NULL) // 如果当前结点的左子树为空, 那么把当前结点的左子树用作线索 
    { 
      node->leftTag = true; 
      node->left = pre; 
    } 
    else node->leftTag = false; 
    pre = node; 
    makeThread(node->right); 
  } 
} 
 
void BinaryTree::traverseBySuccessor() 
{ 
  Node* p = head->left; //first find the root node 
  // 亲测表明 如果不使用head哑节点 就要设三道卡, 防止p访问到NULL,  
  // 分别在主while处, 第二个visit处和下面的p=p->right处 
  while (p!=head) 
  { 
    while (!p->leftTag) 
      p = p->left; 
    visit(p); 
 
    while (p->rightTag && p->right!=head) 
    { 
      p = p->right; 
      visit(p); 
    } 
    p = p->right; 
  } 
  cout<<endl; 
} 
 
void BinaryTree::traverseByPredecessor() 
{ 
  Node* p = head->left; //first find the root node 
  while (p!=head) 
  { 
    while (!p->rightTag) 
      p = p->right; 
    visit(p); 
    if (p!=NULL) 
    { 
      while (p->leftTag && p->left!=head) 
      { 
        p = p->left; 
        visit(p); 
      } 
      p = p->left; 
    } 
  } 
  cout<<endl; 
} 
 
void BinaryTree::buildThread() 
{ 
  pre = NULL; 
  head = new Node('@'); 
  head->left = root; 
  head->right = head; 
  makeThread(root); 
  // 经过了makeThread过程之后, pre必然指向中序遍历最晚的结点. 
  // 把pre的右子树指向head, 就构成了一个双向循环链表 
  // 
  pre->rightTag = 1; 
  pre->right = head; 
  pre = NULL; 
  Node* p = root; 
  /* 
   * 在建立前驱线索的时候，最左边的结点没有和head结点连接。要在这里补上 
   */ 
  while (p->left!=NULL) 
    p = p->left; 
  p->left = head; 
}