1，定义：对于任何结点x,其左子树中的关键字最大不超过x->key,其右子树的关键字最小不小于x->key。 如图所示：

 

            为了简单起见，这里设结点包括key和eft,right,和p，分别为关键字、左结点、右结点、父结点。

typedef struct node{    int key;    struct node *left,*right,*p;//左结点，右结点，父结点}NODE;

2，二叉树的初始化

//数组a为初始化数据，len为数组长度 NODE *init(int a[],int len){    if(len==0)        return NULL;     NODE *root;     root=(NODE *)malloc(sizeof(NODE));     root->key=a[0];     root->left=NULL;     root->right=NULL;     root->p=NULL;     for(int i=1;i
     
      key=a[i];p->right=NULL;         p->left=NULL;         p->p=NULL;         NODE* m=root;         NODE* n=NULL;         while(m!=NULL)         {             n=m;             if(p->key>m->key)                 m=m->right;             else                 m=m->left;                      }         p->p=n;         if(p->key>=n->key)             n->right=p;         else             n->left=p;     }         return root;}
     

3，二叉树的遍历（中序遍历）

void printf_tree(NODE *root) //递归{    if(root)    {        printf_tree(root->left);        printf("%d  ",root->key);        printf_tree(root->right);    }} void printf_tree2(NODE *root)    //非递归中序遍历 {
        stack
     
       s;     NODE *p=root;     while(p!=NULL||!s.empty())     {
            while(p!=NULL)         {
                s.push(p);             p=p->left;         }         if(!s.empty())         {
                p=s.top();             cout<
      
       key<<" ";             s.pop();             p=p->right ;         }     }     } //分层遍历 void printf_tree3(NODE* root) {
        vector
       
         vec;     vec.push_back(root);     int cur = 0;     int last = 1;     while(cur < vec.size()) {
            last = vec.size();         while(cur < last) {
                printf("%d ",vec[cur]->key);             if(vec[cur] -> left)                 vec.push_back(vec[cur]->left);             if(vec[cur] -> right)                 vec.push_back(vec[cur] -> right);             cur++;         }         printf("\n");     } }
       
      
     

 

4, 二叉树结点的后继

     a,当p的右结点不为空时：后继为p的右子树中的最小值

     b,当p的右结点为空: 为祖先中的最小值

            (a)，p为父结点左结点：后继为父节点

            (b), p为父结点的右结点：

 

                             

                            

         a                                                                        a(a)                                                                a(b)

NODE *successor(NODE *p){    NODE *q;    if(p->right!=NULL)    //p的右结点不为空    {        q=p->right;        while(q->left)            q=q->left;        return q;    }   NODE *m=p;    q=m->p;    while(q&&(q==m->right))    {        m=q;        q=m->p;    }    return q;}

5，二叉树的插入

 

bool insert(NODE *root,int x){    NODE *p=(NODE *)malloc(sizeof(NODE));    p->key=x;p->right=NULL;    p->left=NULL;    p->p=NULL;    NODE* m=root;    NODE* n=NULL;    while(m!=NULL)    {        n=m;        if(p->key>m->key)            m=m->right;        else            m=m->left;            }    p->p=n;    if(p->key>n->key)        n->right=p;    else        n->left=p;    return true;}

6，查找最小值，或者最大值

NODE *search_min(NODE *root){    if(root==NULL)        return NULL;    NODE *p;    p=root;    while(p->left)        p=p->left;    return p;}NODE  *search_max(NODE *root){    if(root==NULL)        return NULL;    NODE *p;    p=root;    while(p->right)        p=p->right;    return p;}

7，删除

bool del(NODE *root,NODE *t){    if(NULL==t)        return false;    if(t->left==NULL&&t->right==NULL)    {        NODE *parent=t->p;        if(parent->left==t)            parent->left=NULL;        else            parent->right=NULL;        free(t);        return  true;    }    if (t->left==NULL)  //有右子树    {    /*    NODE *parent=t->p;        if(parent->left==t)            parent->left=t->right;        else            parent->right=t->right;        t->right->p=parent;        free(t);        return true;*/        NODE *p=search_min(t->right);        t->key=p->key;        if(del(root,p))              return true;        else            return false;    }        if (t->right==NULL)  //有左子树    {    /*    NODE *parent=t->p;        if(parent->left==t)            parent->left=t->left;        else            parent->right=t->left;        t->left->p=parent;        free(t);        return true;*/        NODE *p=search_max(t->left);        t->key=p->key;        if(del(root,p))            return true;        else            return false;            }    //有左右子树    NODE *m=successor(t);//m为t的后继结点            t->key=m->key;    if(del(root,m))        return true;    return false;}