基本概念：每个节点的子树最多为2个的树。
几个基本性质：
1、二叉树第i层上的结点数目最多为 2^(i-1) (i≥1)。
2、深度为k的二叉树至多有2^(k)-1个结点(k≥1)。
3、包含n个结点的二叉树的高度至少为log2 (n+1)。
4、在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1。
先序遍历：
void preorder_bstree(BSTree tree)
{
if(tree != NULL)
{
printf("%d ", tree->key);
preorder_bstree(tree->left);
preorder_bstree(tree->right);
}
}
中序遍历：
void inorder_bstree(BSTree tree)
{
if(tree != NULL)
{
inorder_bstree(tree->left);
printf("%d ", tree->key);
inorder_bstree(tree->right);
}
}
后序遍历：
void postorder_bstree(BSTree tree)
{
if(tree != NULL)
{
postorder_bstree(tree->left);
postorder_bstree(tree->right);
printf("%d ", tree->key);
}
}
查找某个结点：
Node* bstree_search(BSTree x, Type key)
{
if (x==NULL || x->key==key)
return x;
if (key < x->key)
return bstree_search(x->left, key);
else
return bstree_search(x->right, key);
}
查找最大值：
Node* bstree_maximum(BSTree tree)
{
if (tree == NULL)
return NULL;
while(tree->right != NULL)
tree = tree->right;
return tree;
}
查找最小值：
Node* bstree_minimum(BSTree tree)
{
if (tree == NULL)
return NULL;
while(tree->left != NULL)
tree = tree->left;
return tree;
}
插入节点：
static Node* bstree_insert(BSTree tree, Node *z)
{
Node *y = NULL;
Node *x = tree;
// 查找z的插入位置
while (x != NULL)
{
y = x;
if (z->key < x->key)
x = x->left;
else if (z->key > x->key)
x = x->right;
else
{
free(z); // 释放之前分配的系统。
return tree;
}
}
z->parent = y;
if (y==NULL)
tree = z;
else if (z->key < y->key)
y->left = z;
else
y->right = z;
return tree;
}
Node* insert_bstree(BSTree tree, Type key)
{
Node *z; // 新建结点
// 如果新建结点失败，则返回。
if ((z=create_bstree_node(key, NULL, NULL, NULL)) == NULL)
return tree;
return bstree_insert(tree, z);
}
bstree_insert(tree, z)是内部函数，它的作用是：将结点(z)插入到二叉树(tree)中，并返回插入节点后的根节点。
insert_bstree(tree, key)是对外接口，它的作用是：在树中新增节点，key是节点的值；并返回插入节点后的根节点。
删除结点：
static Node* bstree_delete(BSTree tree, Node *z)
{
Node *x=NULL;
Node *y=NULL;
if ((z->left == NULL) || (z->right == NULL) )
y = z;
else
y = bstree_successor(z);
if (y->left != NULL)
x = y->left;
else
x = y->right;
if (x != NULL)
x->parent = y->parent;
if (y->parent == NULL)
tree = x;
else if (y == y->parent->left)
y->parent->left = x;
else
y->parent->right = x;
if (y != z)
z->key = y->key;
if (y!=NULL)
free(y);
return tree;
}
Node* delete_bstree(BSTree tree, Type key)
{
Node *z, *node;
if ((z = bstree_search(tree, key)) != NULL)
tree = bstree_delete(tree, z);
return tree;
}
bstree_delete(tree, z)是内部函数，它的作用是：删除二叉树(tree)中的节点(z)，并返回删除节点后的根节点。
delete_bstree(tree, key)是对外接口，它的作用是：在树中查找键值为key的节点，找到的话就删除该节点；并返回删除节点后的根节点。
销毁二叉树：
void destroy_bstree(BSTree tree)
{
if (tree==NULL)
return ;
if (tree->left != NULL)
destroy_bstree(tree->left);
if (tree->right != NULL)
destroy_bstree(tree->right);
free(tree);
}
网友评论