本文實(shí)例講述了C語言實(shí)現(xiàn)二叉樹的搜索及相關(guān)算法。分享給大家供大家參考，具體如下：

東坡網(wǎng)站建設(shè)公司創(chuàng)新互聯(lián)公司,東坡網(wǎng)站設(shè)計(jì)制作，有大型網(wǎng)站制作公司豐富經(jīng)驗(yàn)。已為東坡1000多家提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\成都外貿(mào)網(wǎng)站建設(shè)公司要多少錢，請(qǐng)找那個(gè)售后服務(wù)好的東坡做網(wǎng)站的公司定做！

二叉樹（二叉查找樹）是這樣一類的樹，父節(jié)點(diǎn)的左邊孩子的key都小于它，右邊孩子的key都大于它。

二叉樹在查找和存儲(chǔ)中通常能保持logn的查找、插入、刪除，以及前驅(qū)、后繼，大值，最小值復(fù)雜度，并且不占用額外的空間。

這里演示二叉樹的搜索及相關(guān)算法：

#include
#include
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所在node
tree_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;
}
// 創(chuàng)建樹
tree_node* create_tree(tree_node *t, int n){
  tree_node * root = t;
  for (int i = 1; ileft){ return NULL; }
  tree_node* p = root->left;
  while (p->right){
    p = p->right;
  }
  return p;
}
// 節(jié)點(diǎn)后繼
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 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 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 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();
    }
  }
}
// 層級(jí)遍歷非遞歸
void tree_walk_level_norecursive(tree_node *root){
  if (!root){ return; }
  queue 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 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;
}

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)建站www.cdcxhl.com，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

本文標(biāo)題：C語言實(shí)現(xiàn)二叉樹的搜索及相關(guān)算法示例-創(chuàng)新互聯(lián)
文章轉(zhuǎn)載：http://weahome.cn/article/dssops.html