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) // 如果前驅(qū)節(jié)點(diǎn)的右子樹(shù)為空, 那么把前驅(qū)節(jié)點(diǎn)的右子樹(shù)用作線索 
      { 
        pre->rightTag = true;  
        pre->right = node; 
      } 
      else pre->rightTag = false; 
    } 
    if (node->left==NULL) // 如果當(dāng)前結(jié)點(diǎn)的左子樹(shù)為空, 那么把當(dāng)前結(jié)點(diǎn)的左子樹(shù)用作線索 
    { 
      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 
  // 親測(cè)表明 如果不使用head啞節(jié)點(diǎn) 就要設(shè)三道卡, 防止p訪問(wèn)到NULL,  
  // 分別在主while處, 第二個(gè)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); 
  // 經(jīng)過(guò)了makeThread過(guò)程之后, pre必然指向中序遍歷最晚的結(jié)點(diǎn). 
  // 把pre的右子樹(shù)指向head, 就構(gòu)成了一個(gè)雙向循環(huán)鏈表 
  // 
  pre->rightTag = 1; 
  pre->right = head; 
  pre = NULL; 
  Node* p = root; 
  /* 
   * 在建立前驅(qū)線索的時(shí)候，最左邊的結(jié)點(diǎn)沒(méi)有和head結(jié)點(diǎn)連接。要在這里補(bǔ)上 
   */ 
  while (p->left!=NULL) 
    p = p->left; 
  p->left = head; 
}