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<len;i++) { NODE *p=(NODE *)malloc(sizeof(NODE)); p->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<NODE*> 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<<p->key<<" ";
s.pop();
p=p->right ;
}
}
}
//分层遍历
void printf_tree3(NODE* root) {
vector<NODE*> 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; }