#include<stack>#include<queue>using namespace std;class tree_node{public:  int key;  tree_node *left;  tree_node *right;  int tag;  tree_node(){    key = 0;    left = right = NULL;    tag = 0;  }  ~tree_node(){}};void visit(int value){  printf("%d/n", value);}// 插入tree_node * insert_tree(tree_node *root, tree_node* node){  if (!node){    return root;  }  if (!root){    root = node;    return root;  }  tree_node * p = root;  while (p){    if (node->key < p->key){      if (p->left){        p = p->left;      }      else{        p->left = node;        break;      }    }    else{      if (p->right){        p = p->right;      }      else{        p->right = node;        break;      }    }  }  return root;}// 查詢key所在nodetree_node* search_tree(tree_node* root, int key){  tree_node * p = root;  while (p){    if (key < p->key){      p = p->left;    }    else if (key > p->key){      p = p->right;    }    else{      return p;    }  }  return NULL;}// 創建樹tree_node* create_tree(tree_node *t, int n){  tree_node * root = t;  for (int i = 1; i<n; i++){    insert_tree(root, t + i);  }  return root;}// 節點前驅tree_node* tree_pre(tree_node* root){  if (!root->left){ return NULL; }  tree_node* p = root->left;  while (p->right){    p = p->right;  }  return p;}// 節點后繼tree_node* tree_suc(tree_node* root){  if (!root->right){ return NULL; }  tree_node* p = root->right;  while (p->left){    p = p->left;  }  return p;}// 中序遍歷void tree_walk_mid(tree_node *root){  if (!root){ return; }  tree_walk_mid(root->left);  visit(root->key);  tree_walk_mid(root->right);}// 中序遍歷非遞歸void tree_walk_mid_norecursive(tree_node *root){  if (!root){ return; }  tree_node* p = root;  stack<tree_node*> s;  while (!s.empty() || p){    while (p){      s.push(p);      p = p->left;    }    if (!s.empty()){      p = s.top();      s.pop();      visit(p->key);      p = p->right;    }  }}// 前序遍歷void tree_walk_pre(tree_node *root){  if (!root){ return; }  visit(root->key);  tree_walk_pre(root->left);  tree_walk_pre(root->right);}// 前序遍歷非遞歸void tree_walk_pre_norecursive(tree_node *root){  if (!root){ return; }  stack<tree_node*> s;  tree_node* p = root;  s.push(p);  while (!s.empty()){    tree_node *node = s.top();    s.pop();    visit(node->key);    if (node->right){      s.push(node->right);    }    if (node->left){      s.push(node->left);    }  }}// 后序遍歷void tree_walk_post(tree_node *root){  if (!root){ return; }  tree_walk_post(root->left);  tree_walk_post(root->right);  visit(root->key);}// 后序遍歷非遞歸void tree_walk_post_norecursive(tree_node *root){  if (!root){ return; }  stack<tree_node*> s;  s.push(root);  while (!s.empty()){    tree_node * node = s.top();    if (node->tag != 1){      node->tag = 1;      if (node->right){        s.push(node->right);      }      if (node->left){        s.push(node->left);      }    }    else{      visit(node->key);      s.pop();    }  }}// 層級遍歷非遞歸void tree_walk_level_norecursive(tree_node *root){  if (!root){ return; }  queue<tree_node*> q;  tree_node* p = root;  q.push(p);  while (!q.empty()){    tree_node *node = q.front();    q.pop();    visit(node->key);    if (node->left){      q.push(node->left);    }    if (node->right){      q.push(node->right);    }  }}// 拷貝樹tree_node * tree_copy(tree_node *root){  if (!root){ return NULL; }  tree_node* newroot = new tree_node();  newroot->key = root->key;  newroot->left = tree_copy(root->left);  newroot->right = tree_copy(root->right);  return newroot;}// 拷貝樹tree_node * tree_copy_norecursive(tree_node *root){  if (!root){ return NULL; }  tree_node* newroot = new tree_node();  newroot->key = root->key;  stack<tree_node*> s1, s2;  tree_node *p1 = root;  tree_node *p2 = newroot;  s1.push(root);  s2.push(newroot);  while (!s1.empty()){    tree_node* node1 = s1.top();    s1.pop();    tree_node* node2 = s2.top();    s2.pop();    if (node1->right){      s1.push(node1->right);      tree_node* newnode = new tree_node();      newnode->key = node1->right->key;      node2->right = newnode;      s2.push(newnode);    }    if (node1->left){      s1.push(node1->left);      tree_node* newnode = new tree_node();      newnode->key = node1->left->key;      node2->left = newnode;      s2.push(newnode);    }  }  return newroot;}int main(){  tree_node T[6];  for (int i = 0; i < 6; i++){    T[i].key = i*2;  }  T[0].key = 5;  tree_node* root = create_tree(T, 6);  //tree_walk_mid(root);  //tree_walk_mid_norecursive(root);  //tree_walk_pre(root);  //tree_walk_pre_norecursive(root);  //tree_walk_post(root);  //tree_walk_post_norecursive(root);  //tree_walk_level_norecursive(root);  visit(search_tree(root, 6)->key);  visit(tree_pre(root)->key);  visit(tree_suc(root)->key);  //tree_node* newroot = tree_copy_norecursive(root);  //tree_walk_mid(newroot);  return 0;}