排序二叉树的基本操作(1)插入,查找,最大,最小
排序二叉树(BST, Binary Search Tree)具有这样的性质。对于二叉树中的任意节点,如果它有左子树或右子树,则该节点的数据成员大于左子树所有节点的数据成员,且小于右子树所有节点的数据成员。排序二叉树的中序遍历结果是从小到大排列的。
基本操作包括,插入,查找,前驱,后继,删除,最小节点,最大节点
1插入:从零开始把节点一个一个地插入从而创建一棵树,每进行一次插入,要维护BST的性质。
2查找:给定一个数据,查找是否有节点包含此书
3最大节点:返回当前树的的最大节点,即最右的右儿子。
4最小节点:返回当前树的的最小节点,即最左的左儿子。
5前驱:在中序遍历下,当前节点的前一个节点。
6后继:在中序遍历下,当前节点的后一个节点。
7删除:删除一个指定节点,每进行一次删除,要维BST的性质。
1 插入
根据BST的特性,总能把待插入的key和树中的已有节点不停地做大小比较,直到到达当前树的叶节点的位置。
1.1 递归插入
link insert_recur(link t, int key) { if(!t) return make_node(key); if(t->item>key) t->l = insert_recur(t->l,key);//错误写法:insert(t->l,key); 错误原因在于,这是一个需要逐层搜寻,逐层返回的函数。 else t->r = insert_recur(t->r,key); return t; }
1.2 非递归插入
先找到key应当插入的节点,pp为此节点的父节点。然后把key作为pp的子节点插入。
link insert_norecur(link t, int key) { link p = t; link pp = NULL; while(p) { pp=p; if(key > p->item) p = p->r; else p = p->l; } if(t==NULL) { t = make_node(key); return t; }else { if(key>pp->item) pp->r = make_node(key); else pp->l= make_node(key); return t; } }
1.3 插入时的辅助函数make_node
1.3.1 表示树的节点的结构体
typedef struct node* link; struct node{ int item; link l,r; };
1.3.2 创建节点
static link make_node(int item) { link p = new node; p->item = item; p->l = p->r = NULL; return p; }
2 查找
从当前树的root开始向下,找寻是否有节点的值为key。若找到则返回此节点,若直到叶节点仍找不到,走返回NULL。
2.1 递归查找
link search_recur(link t, int key) { if(!t) return NULL; if(t->item>key) return search_recur(t->l,key); //错误写法:search(t->l,key); 错误原因在于,这是一个需要逐层搜寻,逐层返回的函数。 if(t->item<key) return search_recur(t->r,key); return t; }
2.2 非递归查找
link search_norecur(link t, int key) { if(!t) return NULL; link p = t; while(p) { if(key > p->item) p = p->r; else if (key < p->item) p = p->l; else return p; } return NULL; }
3 最大节点
返回当前树的的最大节点,即最右的右儿子。
3.1 递归版本最大节点
link max_node_recur(link t) { if(t->r == NULL) return t; else return max_node_recur(t->r); //可写为max_node_recur(t->r);也可写为return max_node_recur(t->r); }
3.2 非递归版本最大节点
link max_node_norecur(link t) { link p = t; while(p->r) { p = p->r; } return p; }
4 最小节点
4.1 递归版本最小节点
link min_node_recur(link t) { if(t->l == NULL) return t; else return min_node_recur(t->l); }
4.2 非递归版本最小节点
link min_node_norecur(link t) { link p = t; while(p->l) { p=p->l; } return p; }