本文实例讲述了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 】

相关推荐： 什么是javascript作用域_全局和局部作用域有什么区别？  Android自定义控件实现温度旋转按钮效果  如何在浏览器中启用Flash_2025年继续使用Flash Player的方法【过时】  浏览器如何快速切换搜索引擎_在地址栏使用不同搜索引擎【搜索】  如何在万网自助建站中设置域名及备案？  PHP怎么接收前端传的文件路径_处理文件路径参数接收方法【汇总】  DeepSeek是免费使用的吗 DeepSeek收费模式与Pro版本功能详解  如何用西部建站助手快速创建专业网站？  瓜子二手车官方网站在线入口 瓜子二手车网页版官网通道入口  Laravel Fortify是什么，和Jetstream有什么关系  javascript日期怎么处理_如何格式化输出  HTML5空格在Angular项目里怎么处理_Angular中空格的渲染问题【详解】  Edge浏览器提示“由你的组织管理”怎么解决_去除浏览器托管提示【修复】  Laravel如何实现文件上传和存储？（本地与S3配置）  Laravel如何实现用户角色和权限系统_Laravel角色权限管理机制  如何用y主机助手快速搭建网站？  如何在云服务器上快速搭建个人网站？  如何快速辨别茅台真假？关键步骤解析  Laravel Artisan命令怎么自定义_创建自己的Laravel命令行工具完全指南  详解Huffman编码算法之Java实现  如何在IIS中新建站点并解决端口绑定冲突？  Laravel如何生成URL和重定向？（路由助手函数）  如何在阿里云服务器自主搭建网站？  使用豆包 AI 辅助进行简单网页 HTML 结构设计  米侠浏览器网页背景异常怎么办 米侠显示修复  大连企业网站制作公司,大连2025企业社保缴费网上缴费流程？  韩国网站服务器搭建指南：VPS选购、域名解析与DNS配置推荐  邀请函制作网站有哪些,有没有做年会邀请函的网站啊？在线制作，模板很多的那种？  宙斯浏览器文件分类查看教程 快速筛选视频文档与图片方法  Bootstrap CSS布局之列表  Laravel如何实现多表关联模型定义_Laravel多对多关系及中间表数据存取【方法】  laravel怎么配置Redis作为缓存驱动_laravel Redis缓存配置教程  宙斯浏览器怎么屏蔽图片浏览 节省手机流量使用设置方法  Laravel怎么在Blade中安全地输出原始HTML内容  如何用景安虚拟主机手机版绑定域名建站？  php中::能调用final静态方法吗_final修饰静态方法调用规则【解答】  如何获取上海专业网站定制建站电话？  魔毅自助建站系统：模板定制与SEO优化一键生成指南  微博html5版本怎么弄发超话_超话进入入口及发帖格式要求【教程】  如何挑选最适合建站的高性能VPS主机？  Laravel中的withCount方法怎么高效统计关联模型数量  Linux系统命令中screen命令详解  独立制作一个网站多少钱,建立网站需要花多少钱？  Chrome浏览器标签页分组怎么用_谷歌浏览器整理标签页技巧【效率】  Laravel的Blade指令怎么自定义_创建你自己的Laravel Blade Directives  Python文件异常处理策略_健壮性说明【指导】  儿童网站界面设计图片,中国少年儿童教育网站-怎么去注册？  网站建设保证美观性，需要考虑的几点问题！  laravel服务容器和依赖注入怎么理解_laravel服务容器与依赖注入解析  阿里云高弹*务器配置方案｜支持分布式架构与多节点部署