首页 > 代码库 > 二叉查找树(二叉排序树)创建,插入,删除操作。
二叉查找树(二叉排序树)创建,插入,删除操作。
二叉排序树
- 二叉排序树是一个基础的树的数据结构。应用非常多。
- 它的特性就是,左孩子小于parent,右孩子大于parent.
寻找节点
寻找节点就是直接根据数值的大小,从root节点开始遍历,大于当前遍历节点就向它的右子树查找,相反则查找它的左子树。然后返回。
查找最大最小节点
直接根据root节点,遍历到最右就是最大节点,遍历到最左,就是最小节点。
插入节点
插入节点我这里插入的节点都会成为叶子节点。根据大小的关系向下遍历,遍历到最后的节点,然后插入就可以了。
删除节点
这里删除节点是相对麻烦一点的。在删除的节点是一个叶子节点的时候,或者只有一个孩子的时候,那么直接把当前节点删除让孩子代替自己的位置就可以了,在被删除的节点左右孩子都存在的时候,要删除当前节点,就需要用自己右子树的最小节点来代替被删除的节点。
代码如下
// // main.cpp // BSTree // // Created by Alps on 14-7-31. // Copyright (c) 2014年 chen. All rights reserved. // #include <iostream> #define ElementType int using namespace std; struct Node; typedef Node* PtrToNode; typedef PtrToNode TreeNode; TreeNode makeEmpty(TreeNode T); int isEmpty(TreeNode T); TreeNode findTree(ElementType X,TreeNode T); TreeNode findMin(TreeNode T); TreeNode findMax(TreeNode T); TreeNode insertTree(ElementType X, TreeNode T); TreeNode deleteTree(ElementType X, TreeNode T); struct Node{ ElementType element; TreeNode left; TreeNode right; }; TreeNode makeEmpty(TreeNode T){ if (T != NULL) { makeEmpty(T->left); makeEmpty(T->right); free(T); } return NULL; } int isEmpty(TreeNode T){ return T == NULL; } TreeNode findTree(ElementType X,TreeNode T){ if (T == NULL) { return NULL; } if (X < T->element) { return findTree(X, T->left); }else if(X > T->element){ return findTree(X, T->right); }else{ return T; } } TreeNode findMin(TreeNode T){ if (T == NULL) { return NULL; } if (T->left == NULL) { return T; }else{ return findMin(T->left); } // return NULL; } TreeNode findMax(TreeNode T){ if (T == NULL) { return NULL; } if (T->right == NULL) { return T; }else{ return findMax(T->right); } // return NULL; } TreeNode insertTree(ElementType X, TreeNode T){ if (T == NULL) { T = (TreeNode)malloc(sizeof(Node)); T->element = X; T->left = NULL; T->right = NULL; }else if(X > T->element){ T->right = insertTree(X, T->right); }else if(X < T->element){ T->left = insertTree(X, T->left); } return T; } TreeNode deleteTree(ElementType X, TreeNode T){ TreeNode XNode = findTree(X, T); if (XNode == NULL || T == NULL) { printf("can't find the node is : %d",X); exit(1); } if (X > T->element) { T->right = deleteTree(X, T->right); }else if(X < T->element){ T->left = deleteTree(X, T->left); }else{ TreeNode tmp; if (T->left && T->right) { tmp = findMin(T->right); T->element = tmp->element; T->right = deleteTree( T->element, T->right); }else{ tmp = T; if (T->left == NULL) { T = T->right; }else if (T->right == NULL) { T = T->left; } free(tmp); } } return T; } void PreOrderTree(TreeNode T){ if (T != NULL) { printf("%d ",T->element); PreOrderTree(T->left); PreOrderTree(T->right); } } int main(int argc, const char * argv[]) { TreeNode T = (TreeNode)malloc(sizeof(Node)); T = makeEmpty(T); T = insertTree(6, T); T = insertTree(2, T); T =insertTree(8, T); T =insertTree(1, T); T = insertTree(5, T); T =insertTree(3, T); T = insertTree(4, T); // printf("%d\n",T->element); PreOrderTree(T); printf("\n"); TreeNode tmp; tmp = findTree(2, T); printf("%d\n",tmp->element); T = deleteTree(2, T); PreOrderTree(T); printf("\n"); tmp = findMax(T); printf("%d\n",tmp->element); tmp = findMin(T); printf("%d\n",tmp->element); // std::cout << "Hello, World!\n"; return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。