数据结构 二叉树的增删改查 图解 详解 代码
二叉树的增删改查增-二叉树的建立1.解释图解我们要建立一个 左子树< 本节点 < 右子树的二叉树(例如下图)建立二叉树就是插入二叉树的过程,本次插入的位置都是叶子节点,将比较小的放到叶子节点的左边,比较大的放到叶子节点的右边。例如我们要将 6添加到上面的二叉树的中,比较 6 > 4 因此,接右子树比较 6 < 8 ,接左子树比较 6 < 7 接 ,左子树比较 6 &g
二叉树的 前序遍历,中序遍历,后续遍历的递归实现和非递归
二叉树的增删改查
二叉树的增删改查
增-二叉树的建立
1.解释图解
我们要建立一个 左子树 < 本节点 < 右子树的二叉树(例如下图)
建立二叉树就是插入二叉树的过程,本次插入的位置都是叶子节点,将比较小的放到叶子节点的左边,比较大的放到叶子节点的右边。
例如我们要将 6 添加到上面的二叉树的中,
- 比较 6 > 4 因此,接右子树
- 比较 6 < 8 ,接左子树
- 比较 6 < 7 接 ,左子树
- 比较 6 > 5 ,且 5的右子树为空,将6 作为 5 的右子树(结束)
2.代码 (建议按照代码将上面的二叉树在稿纸上进行一次复现)
private boolean insertItem(TreeNode<E> root,E element) {
TreeNode<E> node = new TreeNode<>();
node.setElement(element);
//第一个插入的元素为根节点.
if (root == null) {
this.root = node;
return true;
}
while (root != null){
int elemCompareRoot = element.compareTo(root.element);
//小的node插入到左子树中
if (elemCompareRoot < 0){
//叶子节点就插入
if (root.left == null){
root.left = node;
return true;
}
else {
//不是叶子节点就继续,直到叶子节点
root = root.left;
}
}//大的node就插入到右子树中
else if (elemCompareRoot > 0){
//如果是叶子节点就插入
if (root.right == null) {
root.right = node;
return true;
}else{
//如果不是叶子节点就继续,直到叶子节点
root = root.right;
}
}
}
//二个元素完全相等
return false;
}
查-二叉树的查询
1.解释图解
查询的本质类似,一个小游戏:“在100以内猜一个数,我会告诉你结果是大了还是小了。”
例如我们查询值为 6 的节点
- 6 > 4 ,继续右子树
- 6 < 8 ,继续左子树
- 6 < 7 ,继续左子树
- 6 > 5 ,继续右子树
- 6 == 6 ,找到节点,返回结果.
2.代码(建议按照代码复现,二叉树的查找过程)
private TreeNode<E> searchItem(TreeNode<E> root,E contactKey) {
while (root != null) {
//小的节点继续左子树
if (contactKey.compareTo(root.element) < 0){
root = root.left;
}//大的节点继续右子树
else if (contactKey.compareTo(root.element) > 0){
root = root.right;
} //相等就返回结果
else if (contactKey.compareTo(root.element) == 0) {
return root;
}
}
//遍历到根节点还找不到,就查找失败.
return null;
}
改 - 修改二叉树的值
- 使用查- 搜索二叉树找到二叉树需要修改的节点,
- 然后改变这个节点值即可
删- 二叉树的删除(难点)
二叉树的删除有点难理解
我们需要考虑下面几种情况
-
1.删除节点是叶子节点: 直接删除
(如图 K叶子节点)
-
2.删除节点是只有左子树(右子树):将删除节点的值(left,right)替换为该左子树(有节点)的值
如图中 D ,
1.将D节点的值替换D.left (H节点)的值,
2.H左子树不为空,将D.left = H.left,
3.H右子树不为空,D.right = H.right
-
3.(难点)删除节点同时有左子树和右子树:
因为第2.种情况的继承者successor,
直接可以确定为删除节点的左子树,我们不必担心寻找继承者的问题,
但是3.种情况我们需要找到删除节点的继承者(这里选择右子树的最小节点为继承者)
但是为了方便继承者的继承后删除,我们这里直接寻找继承者的父节点successorParent
总体步骤如下:
-
3.1.找到继承者的父节点: findSuccessorParent() 使用类似中序遍历的方式找(具体看代码)
-
3.2.替换删除节点的值和继承者(继承者一定为继承者父节点的左子树)的值
-
3.3.删除继承者(如果继承者有右子树,让继承者父节点的左子树指向继承者的右子树,继承者必不可能有左子树)
-
2.代码 (建议复现几次删除节点的操作)
private boolean removeElement(TreeNode<E> root, E removeElement) {
if (root != null){
//使用之前的二叉树查找找到删除节点
TreeNode<E> searchItem = searchItem(root, removeElement);
//1.叶子节点
if (searchItem.left == null && searchItem.right == null) {
searchItem = null;
return true;
}
//2.只有左子树或者右子树
else if (searchItem.left == null){
//store successor element value.
searchItem.element = searchItem.right.element;
//successor the right.right subtree.
if (searchItem.right.right!=null){
searchItem.right = searchItem.right.right;
}
//successor the right.left subtree
if (searchItem.right.left != null){
searchItem.left = searchItem.right.left;
}
return true;
}else if (searchItem.right == null){
searchItem.element = searchItem.left.element;
if (searchItem.left.right !=null){
searchItem.right = searchItem.left.right;
}
if (searchItem.left.left !=null){
searchItem.left = searchItem.left.left;
}
return true;
}else {
//【重点】3. 有左子树和右子树
//3.1 找到继承者的父节点
TreeNode<E> successorParent = findSuccessorParent(searchItem);
//3.2 替换删除节点的值为继承者的值
searchItem.element = successorParent.left.element;
//3.3 删除继承,
// 如果继承者是不是叶子
if (successorParent.left.right !=null){
successorParent.left = successorParent.left.right;
}
//继承者是叶子的时候. 删除
else {
successorParent.left = null;
}
return true;
}
}
return false;
}
private TreeNode<E> findSuccessorParent(TreeNode<E> currentNode){
TreeNode<E> node = currentNode;
TreeNode<E> parent;
Stack<TreeNode<E>> stack = new Stack<>();
while (node!=null || !stack.isEmpty()){
while (node != null){
stack.push(node);
node = node.left;
}
if (!stack.isEmpty()){
stack.pop();
//使用中序遍历的方式找到继承者的父节点.
return stack.pop();
}
}
return null;
}
代码总结
有了二叉树的增删改查,我们就能构建一个简单的二叉搜索树BinarySearchTree
public class TreeNode<E> {
E element;
TreeNode<E> left;
TreeNode<E> right;
}
import java.util.Stack;
/**
* @author Jarvan
* @version 1.0
* @create 2020/11/12 21:44
*/
public class BinarySearchTree<E extends Comparable<E>> {
private TreeNode<E> root;
public BinarySearchTree() {
root = null;
}
/**
* 增
*/
public boolean insertItem(E element) {
TreeNode<E> node = new TreeNode<>();
node.setElement(element);
//第一个插入的元素为根节点.
if (root == null) {
this.root = node;
return true;
}
while (root != null){
int elemCompareRoot = element.compareTo(root.element);
//小的node插入到左子树中
if (elemCompareRoot < 0){
//叶子节点就插入
if (root.left == null){
root.left = node;
return true;
}
else {
//不是叶子节点就继续,直到叶子节点
root = root.left;
}
}//大的node就插入到右子树中
else if (elemCompareRoot > 0){
//如果是叶子节点就插入
if (root.right == null) {
root.right = node;
return true;
}else{
//如果不是叶子节点就继续,直到叶子节点
root = root.right;
}
}
}
//二个元素完全相等
return false;
}
/**
* 查
*/
public TreeNode<E> searchItem(E contactKey) {
while (root != null) {
//小的节点继续左子树
if (contactKey.compareTo(root.element) < 0){
root = root.left;
}//大的节点继续右子树
else if (contactKey.compareTo(root.element) > 0){
root = root.right;
} //相等就返回结果
else if (contactKey.compareTo(root.element) == 0) {
return root;
}
}
//遍历到根节点还找不到,就查找失败.
return null;
}
/**
* 删
*/
public boolean removeElement(E removeElement) {
if (root != null){
//使用之前的二叉树查找找到删除节点
TreeNode<E> searchItem = searchItem( removeElement);
//1.叶子节点
if (searchItem.left == null && searchItem.right == null) {
searchItem = null;
return true;
}
//2.只有左子树或者右子树
else if (searchItem.left == null){
searchItem.element = searchItem.right.element;
if (searchItem.right.right!=null){
searchItem.right = searchItem.right.right;
}
if (searchItem.right.left != null){
searchItem.left = searchItem.right.left;
}
return true;
}else if (searchItem.right == null){
searchItem.element = searchItem.left.element;
if (searchItem.left.right !=null){
searchItem.right = searchItem.left.right;
}
if (searchItem.left.left !=null){
searchItem.left = searchItem.left.left;
}
return true;
}else {
//【重点】3. 有左子树和右子树
//3.1 找到继承者的父节点
TreeNode<E> successorParent = findSuccessorParent(searchItem);
//3.2 替换删除节点的值为继承者的值
searchItem.element = successorParent.left.element;
//3.3 删除继承,
// 如果继承者是不是叶子
if (successorParent.left.right !=null){
successorParent.left = successorParent.left.right;
}
//继承者是叶子的时候. 删除
else {
successorParent.left = null;
}
return true;
}
}
return false;
}
private TreeNode<E> findSuccessorParent(TreeNode<E> currentNode){
TreeNode<E> node = currentNode;
TreeNode<E> parent;
Stack<TreeNode<E>> stack = new Stack<>();
while (node!=null || !stack.isEmpty()){
while (node != null){
stack.push(node);
node = node.left;
}
if (!stack.isEmpty()){
stack.pop();
//使用中序遍历的方式找到继承者的父节点.
return stack.pop();
}
}
return null;
}
/**
* 迭代器
*/
public TreeIterator<E> iterator() {
return new TreeIterator<E>(this.root);
}
}
二叉树搜索树BinarySearchTree和迭代器TreeIterator的源码
https://gitee.com/bmft001/DataStructure_Grace/tree/master/project-04-version-02-blog/src/main/java/addressBook
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)