[C语言实现]实现二叉搜索树（迭代版）的基本操作

实现二叉搜索树的基本操作

在此博客中c语言二叉排序树，我们记录了二叉搜索树插入搜索和删除的思想. 使用递归很容易实现，因为树的定义是递归实现的，因此与递归相比，使用迭代来完成上面的操作比较复杂.

您需要手动记录节点的父节点，因为您要将父节点的子树指向新节点

插入的节点是父节点的左或右子树，可以通过比较大小来确定

void SearchTreeInsert_ByLooP(SearchTreeNode* root, SearchTreeType key)
{
  SearchTreeNode* pre_node = root;
  SearchTreeNode* node = root;
  for(node = root; node != NULL;  )
  {
    if(node->key > key)
    {
      pre_node = node;
      node = node->rchild;
    }
   else  if(node->key < key)
    {
      pre_node = node;
      node = node->lchild;
    }
   else if(node->key == key)
   {
     break;
   }
  }
  //为空 插入新元素
  if(node == NULL)
  {
    node  = (SearchTreeNode*)malloc(sizeof(SearchTreeNode));
    node->key = key;
    node->lchild = NULL;
    node->rchild = NULL;
      //父节点的左边或者右边插入节点
    if(pre_node->key < node->key)
    {
      pre_node->rchild = node;
    }
    else 
    {
      pre_node->lchild = node;
    }
  }
}

搜索什么都没有. 像递归一样c语言二叉排序树，比较大小. 在循环结束时，node = NULL表示搜索丢失

删除递归版本非常复杂，并且迭代更加困难.

但是，这个想法是记录两个节点，即pre_node（父节点），node（当前节点），

您需要根据大小比较节点是pre_node的左子树还是右子树

然后像递归一样将其分为四个类别

以下是删除这四种情况的图标

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-226530-1.html