二叉查找树

二叉查找树

引言：

使二叉树成为二叉查找树的性质是：对于树中的每个节点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.\n");
   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.\n"); 
  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;
}

二叉树的常见问题及其解决程序

【递归】二叉树的先序建立及遍历

在JAVA中实现的二叉树结构

【非递归】二叉树的建立及遍历

二叉树递归实现与二重指针

二叉树先序中序非递归算法

轻松搞定面试中的二叉树题目

本文永久更新链接地址：