学步园

在关于数据结构中，运用最多的树莫过于二叉树，当然，也有B树，B+树，红黑树...
虽然种类很多，但是基本的还是二叉查找树。这里我们就二叉树的一些基本特征作一些讨论，
然后给出一些基本的二叉查找树的常用操作代码。

实现二叉树的方法可以是在每个节点除数据外还要有一些指针，使得该节点的每一个儿子都有一个指针
指向它。二叉树的典型声明如下(为了方便起见，二叉数里的元素都是int型)：

#include <stdio.h>
#include <stdlib.h>

struct node
...{
    int data;
    struct node *left;
    struct node *right;
};

typedef struct node* Node;

给一个数据，返回一个二叉树的节点

Node newNode(int data)
...{
    Node node=(Node)malloc(sizeof(struct node));
    if(node==NULL)
          return NULL;
    node->data=data;
    node->left=NULL;
    node->right=NULL;

    return node;
}

下面介绍一些简单的二叉树的操作代码：

/**//*1.递归计算二叉树中的节点数
 */
int size(Node root)
...{
     Node node=root;
     if (node==NULL)
          return 0;
     else
          return (size(node->left)+1+size(node->right));
}

 

/**//*2.计算二叉树的深度
 */
int maxDepth(Node root)
...{
      Node node=root;
      if (node==NULL)
          return 0;
      else 
     ...{
          int depleft=maxDepth(node->left);
          int depright=maxDepth(node->right);

          return (depleft>depright)?(depleft+1):(depright+1);
     }
}

 

/**//*3.给定一个BST,返回最小的值，即最左端的值
 */
int minValue(Node root)
...{
    Node current=root;

    /**//*循环，直到找到最左端的那个值，即为最小值，并返回*/
    while (current->left != NULL)
    ...{
           current=current->left;
    }
    return current->data;
}

 

/**//*4.1 BST的查找操作，递归操作
 */
Node SearchBST(Node root, int num)
...{
     Node node=root;
     if (node==NULL || node->data == num)
          return node;
     else if(node->data <num)
          return SearchBST(node->left,num);
     else
          return SearchBST(node->right,num);
}

/**//*4.2 BST的查找操作，非递归算法
 */
Node SearchBSTNoRec(Node root, int num)
...{
      Node node=root; 
      while (node != NULL) 
      ...{
           if (node->data==num)
                 return node;
           else if(node->data > num)
                 node=node->left;
           else
                 node=node->right;
        }
        return node;
}

 

/**//*5.1 BST的插入操作,递归算法
 */
Node Insert(Node root, int num)
...{
   Node node=root;
   if(node==NULL)
       return newNode(num);
   else...{
      if(node->data > num)
           node->left=Insert(node->left,num);
      else if(node->data <num)
           node->right=Insert(node->right,num);
                    
      return node;       
   }
}
 
/**//*5.2 BST的插入操作，非递归算法
 */
Node InsertNoRec(Node root, int num)
...{
   Node node=root;
   Node parent; 
   
   if(node==NULL)//如果头节点为空，将该数据插入头节点
       node=newNode(num);   
   else...{
       while(node!=NULL)...{//寻找插入的位置
                 if(node->data==num)//如果存在该节点，直接返回
                         return node;
             else...{
                        parent=node;   //记录父节点位置，用于在该节点后插入数据
                        if(node->data >num)
                              node=node->left;
                        else 
                              node=node->right;
                 }
           }
           node=newNode(num); 
           if(parent->data>num) //根据父节点的值，确定插在其左节点或右节点
                 parent->left=node;
           else
                 parent->right=node; 
       }
       return node;
}

 

/**//*6.BST的删除操作，递归处理，该代码来自数据结构与算法分析
 */
Node Delete(Node root, int num)
...{ 
    Node node=root;
    Node pTemp;
       
    if(node==NULL)
       fprintf(stderr,"Error!Try to delete a NULL tree ");
    else if(node->data > num)
       node->left=Delete(node->left,num);
    else if(node->data < num)
       node->right=Delete(node->right,num);
    else if (node->left!=NULL && node->right !=NULL)...{//要删除的节点有两个子节点
       pTemp=Findmin(node->right);//找到该节点右子树的最小的那个节点，来代替这个被删除的节点
       node->data=pTemp->data;
       node->right=Delete(node->data,node->right);
    }
    else...{//有一个子节点或者是叶子节点
       pTemp=node;
       if(node->left==NULL)
           node=node->right;
       else if(node->right==NULL)
           node=node->left;
       free(pTemp);
    }
    return node;
}         
 
/**//*辅助函数，用于查找二叉树的最小值节点，并返回
 */
Node Findmin(Node node)
...{
    Node current=node;

    /**//*循环，直到找到最左端的那个值，即为最小值，并返回*/