递归方法实现二叉排序树的构建、打印、删除和搜索

递归实现二叉排序树一二叉排序树的基本知识二叉排序树的基础知识如下： 二叉排序树首先是一棵树， 具有树的数据结构具备的所有性质， 并且同时还具有以下这 些特殊的性质。 （1） 二叉排序树的节点是有限个元素的集合，并且每个节点上最多只能存在两个子节点 （分别是左子树和右子树） （2） 对于二叉排序树而言，每个存在子结点的节点都存在左子树小于其本来，而右子树 大于其本来 除了前面讲到的内容，我们还必须了解两个名词： （1） 满二叉树：所有节点都超过最大的二叉树称为满二叉树 （2） 完全二叉树：叶子结点仅在层次最大的两层出现，对于任意一个结点，左子树高度 只能等于右子树高度或右子树高度加一二抽象二叉排序树的数据种类对于使用 Java 实现二叉排序树，首先应该抽象其二叉树的数据种类。也就是需要构造 一个基本二叉树的基础操作的类和一个二叉树结点数据类别。 第一步分析节点数据类别：二叉树的节点包含本身的数据和左右子树的位置。在 Java 中可以构造一个类来推动这种的数据结构。 第二步是去设计二叉树的基本操作， 这里应该预测二叉排序树的基本功能之后去构造一 个类来完成，这应该用到上一步中的自定义类型。 二叉树基本功能：构造一个空树、插入元素、查找元素、删除元素，打印树的全部元素 等很多基本操作。

根据这种基本用途， 可以得出该类需要完成包含构造函数 （构造一个空树） 、 插入元素（成员变量） 、查找元素（成员变量） 、删除元素（成员变量）和数组打印树（成员 函数）的基本操作。三实现二叉排序树的数据类别3.1 构造二叉树的节点的数据类别首先构造二叉树的节点的数据类别。该节点包含结点数据、左子树链接和右子树链接。 其中左右子树与该节点的结点类型是一样的。 该类还必须一个构造函数， 用来初始化左右子 树为空。同时，提供成员函数的读写器。代码如下： （成员变量）package com.xxs.java; /** * 二叉树结点的Java实现 * 用数组的方法表述二叉树的构建、打印、删除和搜索 * @author Administrator * */ publicclass BinaryTreeNode { privateintdata; //结点数据 private BinaryTreeNode leftTreeNode;//左子树 private BinaryTreeNode rightTreeNode;//右子树 /** * 构造函数 */ public BinaryTreeNode(){ leftTreeNode=null; rightTreeNode=null; } /** * @return the data */ publicint getData() { returndata; } /** * @param data the data to set */ publicvoid setData(int data) { this.data = data; }/** * @return the leftTreeNode */ public BinaryTreeNode getLeftTreeNode() { returnleftTreeNode; } /** * @param leftTreeNode the leftTreeNode to set */ publicvoid setLeftTreeNode(BinaryTreeNode leftTreeNode) { this.leftTreeNode = leftTreeNode; } /** * @return the rightTreeNode */ public BinaryTreeNode getRightTreeNode() { returnrightTreeNode; } /** * @param rightTreeNode the rightTreeNode to set */ publicvoid setRightTreeNode(BinaryTreeNode rightTreeNode) { this.rightTreeNode = rightTreeNode; } }3.2 构造二叉排序树的基本操作封装类 3.2.1 二叉树类的基本框架构造好了二叉树的节点的数据类别后， 现在要做的就是构造一个封装类， 封装了二叉排 序树的基本操作，包括添加、查找、打印和删除操作。

该类中包括一个成员函数为二叉树的 结点类型的 root，基本操作只是类的成员变量。该类的基本框架如下：package com.xxs.java; /** * 二叉树类的Java实现用数组的方法表述二叉树的构建、插入、打印、删除和搜索 ** @author Administrator * */ publicclass BinaryTree { private BinaryTreeNode root;// 根结点 /** * 构造函数 */ public BinaryTree() { root = null; } /** * 删除结点 * @param data */ publicvoid remove(int data) { } /** * 插入一个元素，数据为data * @param data 插入元素的数据 */ publicvoid insert(int data){ } /** * 递归查找数据为data的节点 * @param data 结点数据 * @return存在则返回true，否则返回false */ publicboolean isExist(int data){ returnfalse; } /** * 遍历打印二叉树 */ publicvoid print(){ } }3.2.2 插入元素的基本步骤（1）插入一个数据时，首先判断树是否为空，如果为空则建立一个新的节点，将数据存入 结点即可。

如果不为空，则进行（2） （2）先判定数据与当前节点的数据能否相同，如果相同，则不用再插入，直接返回。如果 当前节点的数据小于该数据， 则将当前节点的左子树设置为当前节点， 否则将右子树设置为 当前节点，然后跳转到（3） （3）先判定当前节点是否为空，为空就建立一个新的节点，将数据存入结点即可。否则就 跳转到（2） Insert 函数代码如下：/** * 插入一个元素，数据为data * @param data 插入元素的数据 */ publicvoid insert(int data){ if(root==null){ root=new BinaryTreeNode(); root.setData(data); } else{ insert(root,data); } } /** * 递归插入元素 * @param node * @param data */ privatevoid insert(BinaryTreeNode node, int data) { if((node==null)||(node.getData()==data)){ return;//结点不存在或数据已存在，返回 } if(node.getData() > data){//将数据添加到左子树 if(node.getLeftTreeNode()==null){//左子树为空则创建 BinaryTreeNode temp=new BinaryTreeNode(); temp.setData(data); node.setLeftTreeNode(temp); } else{//否则递归读取 insert(node.getLeftTreeNode(),data); } }else{//将数据添加到右子树 if(node.getRightTreeNode()==null){//右子树为空则创建 BinaryTreeNode temp=new BinaryTreeNode(); temp.setData(data); node.setRightTreeNode(temp); } else{//否则递归读取 insert(node.getRightTreeNode(),data); } } }3.2.3 查找变量的基本步骤（1）查找一个数据时，首先判定根节点是否为空，如果为空则返回 false，否则进行（2） （2）先判定数据与当前节点的数据能否相同，如果相同，则直接返回 true。

如果当前节点 的数据小于该数据， 则将当前节点的左子树设置为当前节点， 否则将右子树设置为当前节点， 然后跳转到（3） （3）先判定当前节点是否为空，为空就返回 false。否则就跳转到（2） isExist 函数代码如下：privatebooleanisExist=false;//查找元素是否存在创建二叉排序树，默认为false /** * 递归查找数据为data的节点 * @param data 结点数据 * @return存在则返回true，否则返回false */ publicboolean isExist(int data){ if(root==null){ isExist=false; } else{ if(root.getData()==data){ isExist=true; } else{ isExist(root,data); } } returnisExist; } /** * 递归查找数据元素是data的节点* @param node node节点 * @param data 结点数据 * @return存在则返回true，负责返回false */ privatevoid isExist(BinaryTreeNode node, int data) { if(node.getData()==data){ isExist=true; } elseif(node.getData()>data){ if(node.getLeftTreeNode()!=null){ isExist(node.getLeftTreeNode(),data); } else { isExist=false; } } else{ if(node.getRightTreeNode()!=null){ isExist(node.getRightTreeNode(),data); } else{ isExist=false; } } }3.2.4 删除元素的基本步骤（1）删除一个数据时，首先判定根节点是否为空，如果为空则直接返回，否则进行（2） （2）先判定数据与根节点的数据能否同样。

如果当前节点的数据小于该数据，则将当前结 点的左子树设置为当前节点，否则将右子树设置为当前节点，然后跳转到（4） 。如果同样， 则跳转到（3） （3）寻找根节点的右子树的最小左子树树叶节点 temp，如果 temp 为空，则将根节点设置 为根结点的左子树后返回，否则将 temp 的值赋给根节点，然后删除 temp 结点（将根节点 的右子树设置为当前结点，根节点的数据设为 data，跳转到 4） （4）先判定数据与当前节点的数据能否同样。如果当前节点的数据小于该数据，则将当前 结点的左子树设置为当前节点， 否则将右子树设置为当前节点， 然后跳转到 （4） 如果同样， 。 则跳转到（5） （5）查找到了待删除结点，若待删除节点没有左子树且待删除节点是父结点的左子树，则 将父结点的左子树结点指向待删除节点的右子树， 然后返回； 若待删除节点没有左子树且待 删除节点是父结点的右子树， 则将父节点的右子树结点指向待删除节点的右子树， 然后返回。 否则跳转到（6） （6）查找到了待删除结点，若待删除节点没有右子树且待删除节点是父结点的左子树，则 将父结点的左子树结点指向待删除节点的左子树， 然后返回； 若待删除节点没有右子树且待删除节点是父结点的右子树， 则将父节点的右子树结点指向待删除节点的左子树， 然后返回。

否则跳转到（7） （7）查找到了待删除节点，若待删除结点同时有左右子树，则寻找当前节点的右子树的最 小左子树叶子结点 temp，将 temp 的值赋给当前节点，然后删除 temp 结点（将当前节点的 右子树设置为当前节点，temp 的数据设为 data，跳转到 4） remove 函数代码如下：/** * 获得该节点的最小左子树的叶子结点用于删除元素时使用 * * @param parent * @return该节点的最小左子树的叶子节点，不存在则返回空 */ private BinaryTreeNode minLeftTreeNode(BinaryTreeNode parent) { BinaryTreeNode temp = parent; while (temp != null) { if (temp.getLeftTreeNode() == null) { return temp; } else { temp = temp.getLeftTreeNode(); } } returnnull;//结点为空时创建二叉排序树，返回空 } /** * 删除结点 * * @param data */ publicvoid remove(int data) { if (root == null) { return; } if (root.getData() == data) { BinaryTreeNode temp = minLeftTreeNode( root.getRightTreeNode());//查找根节点的右子树的最小左子 树节点 if(temp==null){ root=root.getLeftTreeNode();//根节点没有右子树，直接删除根结 点即可 } else{ //将找到的右子树的最小左子树的节点temp的数据赋给root节点 root.setData(temp.getData());remove(root,root.getRightTreeNode(),1,root.getData());//并删除temp 结点 } } elseif(root.getData()< data){ remove(root,root.getRightTreeNode(),1,data);//在右子树中查找 并删除元素 } else{ remove(root,root.getLeftTreeNode(),0,data);//在左子树中查找并 删除元素 } } /** * 递归删除值为data的结点 * @param parent 当前节点的父结点 * @param cur 当前节点 * @param direction 方向，代表左右子树 0代表左子树，1代表右子树 * @param data 结点数据 */ privatevoid remove(BinaryTreeNode parent, BinaryTreeNode cur, int direction, int data) { if(cur.getData()==data){//查找到待删除结点 if(cur.getLeftTreeNode()==null){//待删除节点没有左子树 if(direction==0){ //父结点的左子树结点指向当前节点的右子树 parent.setLeftTreeNode(cur.getRightTreeNode()); } else{//父结点的右子树结点指向当前节点的右子树 parent.setRightTreeNode(cur.getRightTreeNode()); } } elseif(cur.getRightTreeNode()==null){//待删除节点没有右子树 if(direction==0){//父结点的左子树结点指向当前节点的左子树 parent.setLeftTreeNode(cur.getLeftTreeNode()); } else{//父结点的右子树结点指向当前节点的左子树 parent.setRightTreeNode(cur.getLeftTreeNode()); } } else{ //获取当前节点右子树的最小左子树结点temp BinaryTreeNode temp=minLeftTreeNode(cur.getRightTreeNode()); cur.setData(temp.getData());//将当前节点的数据修改为temp的 数据 //删除temp结点，相当于间接删除了cur结点 remove(cur,cur.getRightTreeNode(),1,temp.getData()); } } elseif(cur.getData()<data){ remove(cur,cur.getRightTreeNode(),1,data); } else{ remove(cur,cur.getLeftTreeNode(),0,data); } }3.2.5 遍历二叉树的基本步骤数组枚举二叉数，根据递归枚举类来判定遍历次序，分为前序遍历、中序遍历和后序遍 历。

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