二叉搜索树算法的实现

参考文献: 严为民和吴为民编辑的“数据结构（C语言版本）”

开发平台: Ubuntu11.04

编译器: gcc版本4.5.2（Ubuntu / Linaro 4.5.2-8ubuntu4）

树（树）是n（n≥0）个节点的有限集合. 在任何非空树中: （1）只有一个特定的节点称为Root； （2）当n> 1时，其余节点可分为m（m> 0）一组不相交的有限集T1，T2，...，Tm，每个本身都是树，称为根. 子树（SubTree）.

一个节点拥有的子树的数量称为该节点的度数（度）. 度为0的节点称为叶节点或终端节点. 度不为0的节点称为非终端节点或分支节点.

树的度是树中每个节点的度的最大值.

节点的子树的根称为节点的子节点实现二叉排序树，因此，该节点称为子节点的父节点.

节点的级别是根据根节点计算的. 根是第一层，根的子代是第二层，依此类推. 一棵树中节点的最大级别称为树的深度或高度.

如果树中节点的子树被视为从左到右是有序的（即它们不能互换），则该树称为有序树，否则称为无序树.

1. 二叉树

二叉树（Binary Tree）的特征在于每个节点最多具有两个子树（即，在二叉树中不存在度数大于2的节点），并且子树之间有左右分支.

二叉树的性质:

（1）. 二叉树的第i层上最多有2i-1个节点（i≥1）.

（2）深度为k的二叉树最多有2k-1个节点（k≥1）.

（3）对于任何二叉树，如果终端节点的数量为n0，度数为2的节点的数量为n2，则n0 = n2 + 1.

具有k个深度和2k-1个节点的二叉树称为完整二叉树.

您可以按顺序编号完整的二叉树的节点. 约定的编号从根节点开始，从上到下，从左到右，这可以导致定义完整的二叉树. 当且仅当其每个节点对应于深度为k的完整二叉树中编号为1到n的节点时，才将深度为k和n个节点的二叉树称为完整二叉树.

（4）具有n个节点的完整二叉树的深度是最大整数，不大于log2n加1.

（5）. 如果具有n个节点的完整二叉树的节点按顺序编号（从第一层到最后一层，每一层从左到右），则任何节点i（1≤i≤n），是

a. 如果i = 1，则节点i是没有父节点的二叉树的根. 如果i> 1，则其父节点是节点x（其中x是不大于i / 2的最大整数）.

b. 如果2i> n，则节点i没有左子节点（节点i是叶节点）;否则，其左子节点为节点2i.

c. 如果2i + 1> n，则节点i没有合适的子节点；否则，其右子节点为节点2i + 1.

二叉树的链式存储:

链式二叉树中的每个节点必须至少包含三个字段，即数据字段和左右指针字段.

二叉树遍历:

如果L，D和R分别表示遍历左子树，访问根节点和遍历右子树，则有六种遍历二叉树的方案: DLR，DRL，LRD，LDR，RLD和RDL . 如果先左后右再限制，则只有三种方案，分别称为第一（根）顺序遍历，中间（根）顺序遍历和最后（根）顺序遍历. 通过根节点的访问顺序来区分它们.

2. 二叉搜索树

二叉搜索树（BinarySearch Tree，也称为二叉搜索树或Binary Sort Tree）是空树或具有以下属性的二叉树:

（1）. 如果其左子树不为空，则左子树上所有节点的值小于其根节点的值;

（2）. 如果其右子树不为空，则右子树上所有节点的值都大于其根节点的值；

（3），它的左和右子树也是二叉搜索树.

3. 二叉搜索树的基本操作

[cpp]普通视图

/ * bst-binarysearch / sorttree * byRichardTang * /#include #include typedefintdata_type; typedefstructbst_node {data_typedata; structbst_node * lchild，* rchild;} bst_t ，* bst_p;

（1），插入

在二进制搜索树中插入新节点，以确保在插入新节点后仍能满足二进制搜索树的属性. 示例中的插入过程如下:

a. 如果二进制搜索树的根为空，则将新节点设置为根；

b. 如果二进制搜索树的根不为空，则使用search_bst_for_insert函数查找插入点并返回其地址（如果新节点中的关键字已经存在，则返回空指针）；

c. 如果新节点的关键字小于插入点的关键字，则新节点将插入到插入点的左侧子树中，如果较大，则将其插入到插入点的右侧子树中.

[cpp]普通视图

staticbst_psearch_bst_for_insert（bst_p * root，data_typekey）（bst_ps，p = * root; while（p）（s = p; if（p-> data == key）returnNULL; p =（key data） ？p-> lchild: p-> rchild;}返回；} voidinsert_bst_node（bst_p * root，data_typedata）{bst_ps实现二叉排序树，p; s = malloc（sizeof（structbst_node））; if（！s）perror（“ Allocatedynamicmemory”）； s-> data = data; s-> lchild = s-> rchild = NULL; if（* root == NULL）* root = s; else（p = search_bst_for_insert（root，data）; if（p == NULL） {fprintf（stderr，“％dalreadyexists. \ n”，data）;免费；返回；} if（data data）p-> lchild = s; elsep-> rchild = s;}}

（2），遍历

[cpp]普通视图

staticintprint（data_typedata）{printf（“％d”，data）; return1;} intpre_order_traverse（bst_proot，int（* visit）（data_typedata））{if（root）{if（visit（root-> data）） if（pre_order_traverse（root-> lchild，visit））if（pre_order_traverse（root-> rchild，visit））return1; return0;} elsereturn1;} intpost_order_traverse（bst_proot，int（* visit）（data_typedata））（if（root） {if（post_order_traverse（root-> lchild，visit））if（visit（root-> data））if（post_order_traverse（root-> rchild，visit））return1; return0;} elsereturn1;}

依次遍历二叉搜索树可以获得关键字的有序序列.

（3），删除

删除节点后，必须保留二进制搜索树的特征. 示例中的删除过程如下:

a. 如果删除点是叶节点，则将其父节点的指针设置为空.

b. 如果删除点只有左侧子树或右侧子树，则将父节点的指针设置为指向左侧或右侧子树.

c. 如果删除点的左右子树不为空，则:

1）. 查询删除点右子树的左子树是否为空. 如果为空，则将删除点的左子树设置为删除点的右子树的左子树.

2）如果不为空，请继续查询左子树，直到找到左下子树.

[cpp]普通视图

voiddelete_bst_node（bst_p * root，data_typedata）{bst_pp = * root，parent，s; if（！p）{fprintf（stderr，“ Notfound％d. \ n”，data）; return;} if（p- > data == data）{/ *它是aleafnode * / if（！p-> rchild &&！p-> lchild）{* root = NULL; free（p）;} / * therightchildisNULL * / elseif（！p-> rchild）{* root = p-> lchild; free（p）;} / * theleftchildisNULL * / elseif（！p-> lchild）{* root = p-> rchild; free（p）;} / * thenodehasbothchildren * / else {s = p-> rchild; / *没有剩下的孩子* / if（！s-> lchild）s-> lchild = p-> lchild; / * theshaveleftchild * / else {/ *在左子树中找到最小的节点* / while（s-> lchild ）{/ *记录父节点的数量* / parent = s; s = s-> lchild;} parent-> lchild = s-> rchild; s-> lchild = p-> lchild; s-> rchild = p-> rchild;} * root = s; free（p）;}} elseif（data> p-> data）{delete_bst_node（＆（p-> rchild），data）;} elseif（data data）{delete_bst_node（＆（ p-> lchild），data）;}}

4. 二叉搜索树的搜索分析

相同的关键字，以不同的插入顺序，将产生不同形式的二进制搜索树.

[cpp]普通视图

intmain（intargc，char * argv []）{inti，num; bst_proot = NULL; if（argc <2）{fprintf（stderr，“用法: ％snum \ n”，argv [0]）;退出（ -1）;} num = atoi（argv [1]）; data_typearr [num]; printf（“ Pleaseenter％dintegers: \ n”，num）; for（i = 0; i

运行两次，然后以不同的顺序输入相同的六个关键字:

根据前一个序列遍历的结果，两次运行生成的二叉搜索树的形状不同，如下图所示:

发布于@ 2015-08-29 14: 50hust_liyeRead（...）评论（...）编辑

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-278696-1.html