Java实现链式存储的二叉查找树（递归方法） - linux编程基础

de.getRchild());
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? delNode.setRchild(null); //设置被删除结点的右孩子为null
? ? ? ? ? ? ? ? return true;
? ? ? ? ? ? }
? ? ? ? ? ? //c.若结点z有左、右两颗子树，则删除该结点的后继结点，并用该后继结点取代该结点
? ? ? ? ? ? if(delNode.getLchild()!=null && delNode.getRchild()!=null){
? ? ? ? ? ? ? ? TreeNode successorNode = getSuccessor(node,delNode); //得到被删除结点的后继节点
? ? ? ? ? ? ? ? deleteNode(node,successorNode.getData()); //删除该结点的后继结点
? ? ? ? ? ? ? ? delNode.setData(successorNode.getData()); //用该后继结点取代该结点
? ? ? ? ? ? ? ? return true;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return false;
? ? }
? ?
? ?
? ? public static void main(String args[]){
? ? ? ? Scanner input = new Scanner(System.in);
? ? ? ? Integer[] array = {8,3,10,1,6,14,4,7,13};
? ? ? ? BinarySearchTree bst = new BinarySearchTree();
? ? ? ? TreeNode root = bst.buildBST(array);
? ? ? ? System.out.print("层次遍历：");?
? ? ? ? bst.levelOrder(root);
? ? ? ? System.out.print("\n"+"中序遍历：");?
? ? ? ? bst.inOrder(root);?
? ? ? ? System.out.println();
? ? ? ? System.out.print("得到最大值：");?
? ? ? ? System.out.println(bst.getMaxData(root).getData());?
? ? ? ? System.out.print("得到最小值：");?
? ? ? ? System.out.println(bst.getMinData(root).getData());
? ? ? ? System.out.print("向二叉查找树中插入一个节点，请输入需插入节点的数据域：");
? ? ? ? int data = input.nextInt();
? ? ? ? System.out.print("插入节点"+ data +"后，中序遍历的结果：");
? ? ? ? root = bst.insertNode(root, data);
? ? ? ? bst.inOrder(root);?
? ? ? ? System.out.println("\n"+"在二叉查找树中查找元素,"+"请输入需要查找的结点值：");
? ? ? ? data = input.nextInt();
? ? ? ? if(bst.searchNode(root, data) == null){
? ? ? ? ? ? System.out.println("false");
? ? ? ? }else{
? ? ? ? ? ? System.out.println("true");
? ? ? ? }
? ? ? ? System.out.println("查找节点的直接父节点,"+"请输入需要查找的结点值：");
? ? ? ? data = input.nextInt();
? ? ? ? System.out.print("节点"+ data +"的父节点是：");
? ? ? ? if(bst.getParentNode(root, data) == null){
? ? ? ? ? ? System.out.println("null");
? ? ? ? }else{
? ? ? ? ? ? System.out.println(bst.getParentNode(root, data).getData());
? ? ? ? }
? ? ? ? System.out.println("删除结点,"+"请输入需要删除的结点值：");
? ? ? ? data = input.nextInt();
? ? ? ? if(bst.deleteNode(root, data)){
? ? ? ? ? ? System.out.print("删除结点后的层次遍历：");?
? ? ? ? ? ? bst.levelOrder(root);
? ? ? ? ? ? System.out.print("\n"+"删除结点后的中序遍历：");?
? ? ? ? ? ? bst.inOrder(root);
? ? ? ? }? ? ?
? ? }? ?
}

程序运行结果：

层次遍历：8 3 10 1 6 14 4 7 13
中序遍历：1 3 4 6 7 8 10 13 14
得到最大值：14
得到最小值：1
向二叉查找树中插入一个节点，请输入需插入节点的数据域：15
插入节点15后，中序遍历的结果：1 3 4 6 7 8 10 13 14 15
在二叉查找树中查找元素,请输入需要查找的结点值：
true
查找节点的直接父节点,请输入需要查找的结点值：
节点10的父节点是：8
删除结点,请输入需要删除的结点值：
删除结点后的层次遍历：8 3 10 1 6 14 7 13 15
删除结点后的中序遍历：1 3 6 7 8 10 13 14 15

某些方法的非递归实现：

1. 插入节点insertNode():

//在二叉查找树中插入一个数据域为data的结点，新插入的结点一定是某个叶子节点
? ? public TreeNode insertNode(TreeNode node, Integer data){
? ? ? ? TreeNode newNode = new TreeNode(data,null,null);
? ? ? ? TreeNode tmpNode = node;? //遍历节点
? ? ? ? TreeNode pnode = null;? //记录当前节点的父节点? ?
? ? ? ?
? ? ? ? if(node == null){? //原树为空，新插入的记录为根节点
? ? ? ? ? ? node = newNode;? ?
? ? ? ? ? ? return node;
? ? ? ? }
? ? ? ? while(tmpNode != null){
? ? ? ? ? ? pnode = tmpNode;
? ? ? ? ? ? if(tmpNode.getData() == data){ //树中存在相同关键字的结点,什么也不做
? ? ? ? ? ? ? ? return node;
? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? if(tmpNode.getData() > data){ //根节点>插入数据，插入到左子树中
? ? ? ? ? ? ? ? ? ? tmpNode = tmpNode.getLchild();
? ? ? ? ? ? ? ? }else{ //根节点<插入数据，插入到右子树中
? ? ? ? ? ? ? ? ? ? tmpNode = tmpNode.getRchild();
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? if(pnode.getData() > data){
? ? ? ? ? ? pnode.setLchild(newNode);
? ? ? ? }else{
? ? ? ? ? ? pnode.setRchild(newNode);
? ? ? ? }? ?
? ? ? ? return node;
? ? }

2. 二叉查找树的中序遍历：

//二叉查找树的中序遍历LNR，可以得到一个递增的有序数列
? ? public void inOrder(TreeNode node){
? ? ? ? Stack> nodeStack = new Stack>();
? ? ? ? T

Java实现链式存储的二叉查找树（递归方法）(三)