首页 / 操作系统 / Linux / 二叉查找树

引言：使二叉树成为二叉查找树的性质是：对于树中的每个节点X，它的左子树中所有关键字值小于X的关键字值，而它的右子树中所有关键字值大于X的关键字值。二叉查找树声明struct TreeNode;
typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;struct TreeNode{
 ElementType Element;
 SearchTree  Left;
 SearchTree  Right;
};建立一棵空树的例程SearchTree MakeEmpty（SearchTree T）
{
 if（T ！= NULL）{
  MakeEmpty（T->Left）; 
  MakeEmpty（T->Right）; 
  free（T）;
 } return NULL;
}二叉查找树的Find操作Position Find（ElementType X, SearchTree T）
{
 if（T == NULL）
  return NULL;
 if（X < T->Element）
  return Find（X, T->Left）;
 else if（X > T->Element）
  return Find（X, T->Right）;
 return T;
}二叉查找树的FindMin递归与非递归实现Position FindMin（SearchTree T）
{
 if（T == NULL）
  return NULL; 
 else if（T->Left == NULL）
  return T;
 else
  return FindMin（T->Left）;
}Position FindMin（SearchTree T）
{
 if（T ！= NULL）
  while（T->Left ！= NULL）
   T = T->Left; 
 return T;
}二叉查找树的FindMax递归与非递归实现Position FindMax（SearchTree T）
{
 if（T == NULL）
  return NULL;
 else if（T->Right == NULL）
  return T;
 else
  return FindMax（T->Right）;
}Position FindMax（SearchTree T）
{
 if（T ！= NULL）
  while（T->Right ！= NULL） 
   T = T->Right; 
 return T;
}插入元素到二叉查找树的例程SearchTree Insert（ElementType X, SearchTree T）
{
 if（T == NULL）{
  T = （SearchTree）malloc（sizeof（struct TreeNode））; 
  if（T == NULL）{
   printf（"Out of space. "）;
   return NULL;
  }
 }else if（X < T->Element）{
  T->Left = Insert（X, T->Left）; 
 }else （X > T->Element）{
  T->Right = Insert（X, T->Right）; 
 } return T;
}二叉查找树的删除例程SearchTree Delete（ElementType X, SearchTree T）
{
 Position TmpCell; if（T == NULL）{
  fprintf（stderr,"Element not found. "）; 
  return NULL;
 }else if（X < T->Element）
  T->Left = Delete（X, T->Left）;
 else if（X > T->Element）
  T->Right = Dlelte（X, T->Right）;
 else if（T->Left && T->Right）{
  TmpCell = FindMin（T->Right）; 
  T->Element = TmpCell->Element;
  T->Right = Delete（T->Element, T->Right）;
 }else{
  TmpCell = T;
  if（T->Left == NULL） 
   T = T->Right;
  else if（T->Right == NULL）
   T = T->Left;
  free（TmpCell）;
 } return T;
}二叉树的常见问题及其解决程序 http://www.linuxidc.com/Linux/2013-04/83661.htm【递归】二叉树的先序建立及遍历 http://www.linuxidc.com/Linux/2012-12/75608.htm在JAVA中实现的二叉树结构 http://www.linuxidc.com/Linux/2008-12/17690.htm【非递归】二叉树的建立及遍历 http://www.linuxidc.com/Linux/2012-12/75607.htm二叉树递归实现与二重指针 http://www.linuxidc.com/Linux/2013-07/87373.htm二叉树先序中序非递归算法 http://www.linuxidc.com/Linux/2014-06/102935.htm轻松搞定面试中的二叉树题目 http://www.linuxidc.com/linux/2014-07/104857.htm本文永久更新链接地址：http://www.linuxidc.com/Linux/2014-08/105691.htm