本文实例讲述了C语言实现二叉树的搜索及相关算法。分享给大家供大家参考，具体如下：

二叉树（二叉查找树）是这样一类的树，父节点的左边孩子的key都小于它，右边孩子的key都大于它。

二叉树在查找和存储中通常能保持logn的查找、插入、删除，以及前驱、后继，最大值，最小值复杂度，并且不占用额外的空间。

这里演示二叉树的搜索及相关算法：

#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所在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;
}
// 创建树
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;
}

希望本文所述对大家C语言程序设计有所帮助。

# C语言  # 二叉树  # 搜索  # 算法  # C语言二叉树的三种遍历方式的实现及原理  # C语言数据结构之线索二叉树及其遍历  # c语言_构建一个静态二叉树实现方法  # 如何使用C语言实现平衡二叉树数据结构算法  # C语言二叉排序树的创建  # 插入和删除  # 遍历  # 递归  # 是这样  # 给大家  # 所述  # 最小值  # 不占用  # 讲述了  # namespace  # std  # tree_node  # stack  # gt  # queue  # public  # NULL  # void  # visit  # int 

相关栏目： 【 网站优化151355 】 【 网络推广146373 】 【 网络技术251813 】 【 AI营销90571 】

相关推荐： 如何选择可靠的免备案建站服务器？  如何在橙子建站中快速调整背景颜色？  学生网站制作软件,一个12岁的学生写小说，应该去什么样的网站？  Bootstrap整体框架之JavaScript插件架构  Laravel怎么进行数据库事务处理_Laravel DB Facade事务操作确保数据一致性  Laravel怎么进行浏览器测试_Laravel Dusk自动化浏览器测试入门  Laravel中DTO是什么概念_在Laravel项目中使用数据传输对象(DTO)  如何在阿里云部署织梦网站？  Android仿QQ列表左滑删除操作  Laravel如何实现文件上传和存储？（本地与S3配置）  什么是JavaScript解构赋值_解构赋值有哪些实用技巧  html5的keygen标签为什么废弃_替代方案说明【解答】  如何自定义建站之星模板颜色并下载新样式？  高防服务器租用指南：配置选择与快速部署攻略  网站制作价目表怎么做,珍爱网婚介费用多少？  Win11怎么更改系统语言为中文_Windows11安装语言包并设为显示语言  Laravel怎么在Blade中安全地输出原始HTML内容  利用python获取某年中每个月的第一天和最后一天  浅谈redis在项目中的应用  车管所网站制作流程,交警当场开简易程序处罚决定书，在交警网站查询不到怎么办？  微信小程序 scroll-view组件实现列表页实例代码  如何在腾讯云服务器上快速搭建个人网站？  php做exe能调用系统命令吗_执行cmd指令实现方式【详解】  标题：Vue + Vuex 项目中正确使用 JWT 进行身份认证的实践指南  Laravel如何实现用户角色和权限系统_Laravel角色权限管理机制  香港网站服务器数量如何影响SEO优化效果？  Laravel的.env文件有什么用_Laravel环境变量配置与管理详解  Laravel如何从数据库删除数据_Laravel destroy和delete方法区别  Laravel如何处理CORS跨域请求？（配置示例）  Python自然语言搜索引擎项目教程_倒排索引查询优化案例  微信小程序 input输入框控件详解及实例（多种示例）  如何在IIS7上新建站点并设置安全权限？  浅述节点的创建及常见功能的实现  头像制作网站在线观看,除了站酷，还有哪些比较好的设计网站？  JS中使用new Date(str)创建时间对象不兼容firefox和ie的解决方法(两种)  Laravel如何使用Eloquent ORM进行数据库操作？（CRUD示例）  Laravel如何使用Guzzle调用外部接口_Laravel发起HTTP请求与JSON数据解析【详解】  购物网站制作费用多少,开办网上购物网站，需要办理哪些手续？  Laravel怎么使用Collection集合方法_Laravel数组操作高级函数pluck与map【手册】  Laravel如何实现数据导出到CSV文件_Laravel原生流式输出大数据量CSV【方案】  Laravel怎么实现观察者模式Observer_Laravel模型事件监听与解耦开发【指南】  中山网站制作网页,中山新生登记系统登记流程？  图片制作网站免费软件,有没有免费的网站或软件可以将图片批量转为A4大小的pdf？  品牌网站制作公司有哪些,买正品品牌一般去哪个网站买？  C#如何调用原生C++ COM对象详解  北京网站制作费用多少,建立一个公司网站的费用.有哪些部分,分别要多少钱？  如何在IIS7中新建站点？详细步骤解析  网站制作大概要多少钱一个,做一个平台网站大概多少钱？  Laravel如何创建自定义Facades？（详细步骤）  ,南京靠谱的征婚网站？