二叉树（四）---查找二叉树

深碍√TFBOYSˉ_ 2022-05-25 09:37 192阅读 0赞

上次我说了如何去遍历一棵二叉树，今天我来说一说查找二叉树是怎样实现的。

首先我来介绍一下查找二叉树是怎样生成的。

这个是我为我的二叉树设置的一些基础的组成数据结构

private TreeNode root;
    	int count = 1;
    	public SearchBinaryTree(){
    		root=null;
    	}

我们可以设置一个数组，里面的数字可以是乱序的。那么我们的查找二叉树就是将他们进行排序，将其存储为二叉树的形式。

规则就是值小的数作为左子树，值大的数作为右子树。

那么首先来看一些我的代码

/**
    	 * 创建查找二叉树
    	 * @author Administrator
    	 *
    	 */
    	public TreeNode put(int data){
    		TreeNode node = null;
    		TreeNode parent = null;
    		node = new TreeNode(0,data);
    		//创建根节点
    		if(root == null){
    			root =node;
    		}
    		//从根节点开始查找
    		node = root;
    		//查找node应该添加的位置
    		//如果比当前结点小则在其左孩子中查找
    		//如果比当前结点大则在其右孩子中查找
    		//如果相等则不进行添加
    		while(node!=null){
    			parent = node;//把当前结点假定为目标结点的父节点
    			if(data>node.data){
    				node = node.rightChild;
    			}else if(data<node.data){
    				node = node.leftChild;
    			}else{
    				return node;
    			}
    		}
    		//遍历出来之后node就是null
    		//表示将此结点添加到相应位置
    		node =new TreeNode(0,data);
    		if(data>parent.data){
    			parent.rightChild = node;
    			node.parent = parent;
    		}else{
    			parent.leftChild =node;
    			node.parent = parent;
    		}
    		return node;
    		
    	}

这个方法的入参是这个数组中每个数值。首先声明两个变量node,parent。

刚开始的时候这棵二叉树是空的，所以它的root节点也是空的。那么我们需要实例化node节点并将它的值赋给root。

接下来开始查找，从这个root节点开始查找。这时候就需要使用我们的parent节点了。我们可以先假设要添加的节点是当前节点的子树，也就是说当前节点是要添加的节点的父亲节点。如果比当前节点小则去它的左子树查找（理由就是根据查找二叉树的组成性质来决定的，值小的都放在树的左侧），反之如果比当前节点大就去它的右子树中去查找。如果相等则不添加。当我们发现node的值为空时，这个时候说明我们已经完成了遍历，也就是说我们找到了应该添加的地方。这个时候node的值变成了null。

所以需要重新为node实例化。然后添加到parent节点的相应位置。并且完成关系的指向工作。

这个是二叉树的添加。相对来说是建立在二叉树的组成上来进行搜索。这样的好处是查找一个数字的时间复杂度仅为logn

接下来我来说说如何遍历一个查找二叉树。前面我说过，查找二叉树的建造目的就是把一组乱序的数据以二叉树的形式进行有效的排列。那么我们该怎样让这些数据有序的显示出来呢。我们可以思考一下。前序，中序，后序哪个更符合我们对查找二叉树的理解。

选取查找二叉树的一棵子树来进行分析，可以看到左子树的值<根节点的值<右子树的值。所以我们需要使用的是使用中序遍历法

遍历算法如下我不做过多解释

/**
    	 * 遍历查找二叉树
    	 * @param node
    	 */
    	public void midOrder(TreeNode node){
    		
    		if(node ==null){
    			return;
    		}else{
    			midOrder(node.leftChild);
    			node.key  = count++;
    			System.out.println(node.key+"<-------->"+node.data);
    			midOrder(node.rightChild);
    		}
    	}

最后也是最为复杂的就是查找二叉树的节点删除了。这个之所以困难是因为删除一个节点是牵一发而动全身的。

我将用一个图来解释一下删除算法。

首先我先构造了一个树，这个树是按照我所写的构造算法设置的。

![70][]

这个是我构造的一棵二叉树，我来根据这个二叉树来解释一下怎样实现二叉树的删除。

首先二叉树的删除有四种情况

第一种如果这个节点没有左子树和右子树，那么就直接将这个节点删除。例如15，41

第二种，如果这个节点只有左子树，那么就让这个左子树成为这个节点的父节点的左子树或者右子树

第三种，如果这个节点只有右子树，那么就让这个右子树成为这个节点的父节点的左子树或者右子树。

第四种，如果这个节点有左子树和右子树，那么我们就要删除它的后继节点了。

什么是后继节点呢。就是如果将这个二叉树进行排序排在这个节点后面的节点。

例如，40的后继节点是41。一般情况下一个节点的后继节点是要从它的右孩子中去查找的.

如果这个节点的右孩子有左孩子，那么它的后继节点就是左孩子的最左侧。如果这个节点的右孩子没有左孩子，则这个右孩子就是这个节点的后继节点。

下面我将根据我的代码来进行解释。

/**
    	 * 删除节点
    	 * 
    	 * @param data
    	 * @return
    	 */
    	public TreeNode delete(int data){
    		TreeNode node = searchNode(data);
    		if(node ==null){
    			try {
    				throw new Exception("该结点不存在");
    			} catch (Exception e) {
    				e.printStackTrace();
    			}
    		}else{
    			delete(node);
    		}
    		return node;
    	}

下面是这个方法中调用的一些方法

private void delete(TreeNode node) {
    		if(node==null){
    			try {
    				throw new Exception("该结点为空");
    			} catch (Exception e) {
    				e.printStackTrace();
    			}
    		}else{
    			TreeNode parent = node.parent;
    			//第一种情况，如果这个结点没有左孩子和右孩子，那么只要将这个结点为空就行了
    			if(node.leftChild==null&&node.rightChild==null){
    				//判断被删除的结点是它的父节点的左孩子还是右孩子
    				if(node.data<parent.data){
    					parent.leftChild=null;
    				}else{
    					parent.rightChild=null;
    				}
    				return ;
    				
    			}
    			//被删除的结点有左孩子无右孩子
    			if(node.leftChild!=null&&node.rightChild==null){
    				if(parent.leftChild == node){
    					//如果被删除结点是父节点的左孩子，那么父节点的左孩子将是该结点的左孩子
    					 parent.leftChild=node.leftChild;
    				}else{
    					//如果被删除结点是父节点的右孩子，那么父节点的左孩子将是该结点的右孩子
    					parent.rightChild =node.leftChild;
    				}
    				return ;
    			}
    			//被删除的结点有右孩子无左孩子
    			if(node.leftChild==null&&node.rightChild!=null){
    				if(parent.leftChild == node){
    					//如果被删除结点是父节点的左孩子，那么父节点的左孩子将是该结点的右孩子
    					 parent.leftChild=node.rightChild;
    				}else{
    					//如果被删除结点是父节点的右孩子，那么父节点的右孩子将是该结点的右孩子
    					parent.rightChild =node.rightChild;
    				}
    				return ;
    			}
    			//被删除的结点有右孩子和左孩子
    			//找到该结点的后继结点
    			TreeNode next = getNextNode(node);
    			delete(next);
    			node.data = next.data;
    		}
    		
    	}

/**
    	 * 获取一个结点的后继结点
    	 * @param node
    	 * @return
    	 */
    	private TreeNode getNextNode(TreeNode node) {
    		if(node==null){
    			try {
    				throw new Exception("该结点为空");
    			} catch (Exception e) {
    				e.printStackTrace();
    			}
    		}else{
    			if(node.rightChild.leftChild!=null){
    				//找某结点的最小值结点，如果它的右孩子的左孩子不为空，去它的右孩子所有左子树中查找最底左子树
    				return getMinTreeNode(node.rightChild);
    			}else{
    				return node.rightChild;
    			}
    			}
    		return null;
    	}

/**
    	 * 找一棵树的最小后继
    	 * @param rightChild
    	 * @return
    	 */
    	private TreeNode getMinTreeNode(TreeNode node) {
    		if(node ==null){
    			return null;
    		}else{
    			while(node.leftChild!=null){
    				node = node.leftChild;
    			}
    		}
    		return node;
    	}

首先来看总方法，首先我们要找到我们需要删除的节点。方法是searchNode(int)。之后就是根据删除这个节点。前三种情况代码非常清楚。第四种情况分为两种比较简单的情况代码也在上方。

查找二叉树保证查找比较快速，而且不会重复。

[70]: /images/20220525/4db78a7d3875423c8ba8f4492bb6c7b6.png