【数据结构】二叉查找树
1、概念: 二叉查找树,也称排序二叉树,是指一棵空树或者具备下列性质的二叉树(每个节点都不能有多于两个儿子的树): 1. 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;2. 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值; 3. 任意节点的左、右子树也分别为二叉查找树 4. 没有键值相等的节点 从其性质可知,定义排序二叉树树的一种自然的方式是递归的方法,其算法的核心为递归过程,由于它的平均深度为O(logN),所以递归的操作树,一般不必担心栈空间被耗尽。 树的深度:对于任意节点Ni,Ni的深度为从根到Ni的惟一路径的长。 2、二叉查找树的数据节点 typedef struct _BinaryTree { ?? ?int value; ?? ?struct _BinaryTree *left_child;???? //左儿子 ?? ?struct _BinaryTree *right_child; }BinaryTree;3、创建二叉查找树节点 /*创建一个树节点*/ BinaryTree* createTreeNode(int value) { BinaryTree* pBinaryTree = NULL; pBinaryTree = (BinaryTree *)malloc(sizeof(BinaryTree)); memset(pBinaryTree,sizeof(BinaryTree)); pBinaryTree->value = value; return pBinaryTree; } 4、插入节点 鉴于二叉查找树的性质1234,用递归可以很方便的对二叉查找树插入节点 /*这里可能会修改根节点指针,所以采用二级指针传递 任意左右子树也是二叉查找树,也有相应的“根节点”*/ bool insertNode(BinaryTree **ppBinaryTree,int value) { if (NULL == ppBinaryTree) return false; if (NULL == *ppBinaryTree) //空树及递归终止条件 { *ppBinaryTree = createTreeNode(value); //创建树节点插入 assert(NULL != *ppBinaryTree); return true; } else { //插入值小于其根节点键值,遍历左子树 if (value < (*ppBinaryTree)->value) return insertNode(&(*ppBinaryTree)->left_child,value); //插入值大于其根节点键值,遍历右子树 else if (value > (*ppBinaryTree)->value) return insertNode(&(*ppBinaryTree)->right_child,value); //重复元插入,直接返回 else return false; } }5、查找指定键值树节点 由二叉查找树的特性可知,二叉查找树在查找和插入方面相对于其余数据结构有很好的优势 BinaryTree* findTreeNode(BinaryTree *pBinaryTree,int key) { if (NULL == pBinaryTree) //二叉树不存在或递归终止条件(键值未找到) return NULL; if (key == pBinaryTree->value) //根节点为键值或递归终止条件(找到对应键值) return pBinaryTree; else if (key < pBinaryTree->value) return findTreeNode(pBinaryTree->left_child,key); else return findTreeNode(pBinaryTree->right_child,key); } 6、查找最小、最大键值节点 /*二叉查找树的性质让我们可以很方便的查找最小最大键值*/ /*查找最小键值节点:直接递归遍历左子树叶子节点*/ BinaryTree* findMin(BinaryTree *pBinaryTree) { if (NULL == pBinaryTree) return NULL; else if (NULL == pBinaryTree->left_child) return pBinaryTree; else return findMin(pBinaryTree->left_child); } /*非递归实现查找最大键值节点*/ BinaryTree* findMax(BinaryTree *pBinaryTree) { if (pBinaryTree != NULL) { while (pBinaryTree->right_child) pBinaryTree = pBinaryTree->right_child; } return pBinaryTree; } 7、删除指定元素节点 每种数据结构有利有弊,二叉查找树的删除操作不比链表操作那样方便,它必须保证每次删除操作之后,还是二叉查找树。所以需要考虑下列这样几种情况: 1. 删除节点为叶子节点即没有左右儿子,存在特殊情况就是该叶子节点也为根节点2. 删除节点有两个儿子 3. 删除节点只有左儿子(左儿子是叶子节点和非叶子节点情况),没有右儿子 4. 删除节点只有右儿子(右儿子是叶子节点和非叶子节点情况),没有左儿子 还需清楚的是节点的左子树的所有节点键值均小于该节点键值,其右子树的所有节点键值均大于该节点键值,清楚这点可以更好的理解删除节点之后的处理情况,以下列二叉查找树为例进行说明: /* * 6 * / \ * 2 8 * / \ \ * 1 4 10 * / * 3 */ 2)删除节点有两个儿子:一般的删除策略是用其右子树的最小的数据代替该节点的数据,并递归地删除那个右子树的最小节点。如果删除节点2,那么先用其右子树的最小数据节点3代替该节点的数据,然后再递归地删除节点3。数据结构的各个数据节点仅数值不同,修改数据其实就是修改数据节点。如下所示 /* * 6 6 6 * / \ / \ / \ * 2 8 3 8 3 8 * / \ \ --> / \ \ --> / \ \ * 1 4 10 1 4 10 1 4 10 * / / * 3 3 */ (编辑:ASP站长网) |