二叉搜索树

二叉搜索树

文章目录

​​一，二叉搜索树​​​​二，二叉查找树相关操作​​

​​1.判断是否存在指定节点​​​​2.构造二叉搜索树​​​​3.删除节点​​​​4.遍历​​​​5.寻找最大节点​​​​6.寻找最小节点​​

一，二叉搜索树

性质：

对于树中的每个节点，他的左子树中的所有项都小于根节点，他的右子树中的所有项都大于根节点二叉查找树的平均深度是O(logN)所有一般不必担心栈空间溢出二叉查找树要求所有的项都能够被排序

二，二叉查找树相关操作

1.判断是否存在指定节点

/** * 判断是否包含指定节点 * @param x * @param node * @return */ public boolean contain(T x,Node node){ if(node == null){ return false; } int result = x.compareTo((T)node.getElement()); if(result < 0){ return contain(x,node.getLeft()); }else if(result > 0){ return contain(x,node.getRight()); }else { return true; } }

2.构造二叉搜索树

思路：

根据二叉搜索树的性质，左子节点 < 根节点 < 右子节点

/** * 构造二叉树 * 【递归】 * @param x * @param t * @return */ public Node insert(T x,Node t){ if(t == null){ return new Node(x,null,null); } int result = x.compareTo(t.element); if(result < 0){ t.left = insert(x,t.getLeft()); }else if(result > 0){ t.right = insert(x,t.getRight()); }else{ //dosomething t.element = x; } return t; }

构造二叉搜索树

public static void main(String[] args) { System.out.println("*******构造二叉查找树*******"); BinarySearchTree binarySearchTree = new BinarySearchTree<>(); Node root = new Node(12); binarySearchTree.setRoot(root); binarySearchTree.insert(10, root); binarySearchTree.insert(13, root); binarySearchTree.insert(11,root); binarySearchTree.insert(15, root); }

3.删除节点

删除节点其实有三种情况需要考虑：

没有左右子节点，可以直接删除只有左子节点或只有右子节点，删除后需要进行节点移动同时存在左右子节点，则将删除节点和中序遍历结果中该节点的后继节点交换

二叉搜索树中的中序遍历结果就是一个排序后的序列

/** * 删除平衡树中的指定节点 * @param x * @param root * @return */ public AvlNode remove(int x,AvlNode root){ if(root == null){ return root; } //寻找指定节点 if(x > root.val){ root.right = remove(x,root.right); }else if(x < root.val){ root.left = remove(x,root.left); }else{ //找到了指定节点 //判断是否存在子节点，以及是单个子节点还是两个子节点 if(root.left != null && root.right != null){ //左右子节点都存在 //找出右子树中的最小值 root.val = findMin(root.right).val; //转成一个子节点的情况 root.right = remove(root.val,root.right); }else{ //存在一个子节点,不空则覆盖 if(root.left != null){ root = root.left; } else if(root.right != null){ root = root.right; } //叶节点情况 else { root = null; } } } return root; }

4.遍历

广度优先遍历

/** * 广度优先遍历 * @param root */ public void breathFirst(Node root){ if(root == null){ return; } ArrayList resultList = new ArrayList<>(); Queue queue = new ArrayDeque<>(); if(root != null){ queue.add(root); while(!queue.isEmpty()){ root = queue.remove(); resultList.add((T) root.getElement()); if(root.getLeft() != null){ queue.add(root.getLeft()); } if(root.getRight() != null){ queue.add(root.getRight()); } } } for(T i : resultList){ System.out.println(i); } }

前序遍历

/** * 前序遍历 * 【递归实现】 * @param root */ public void preOrder(Node root){ if(root != null){ System.out.println(root.getElement()); preOrder(root.getLeft()); preOrder(root.getRight()); } } /** * 前序遍历 * 【非递归实现】 * @param root */ public void preOrder2(Node root){ if(root == null){ return; } ArrayList list = new ArrayList<>(); Stack stack = new Stack<>(); stack.push(root); while(!stack.isEmpty()){ Node node = stack.pop(); list.add((T) node.getElement()); if(node.getRight() != null){ stack.push(node.getRight()); } if(node.getLeft() != null){ stack.push(node.getLeft()); } } for(T i : list){ System.out.println(i); } }

中序遍历

/** * 中序遍历 * 【递归实现】 * @param root */ public void inOrder(Node root){ if(root != null){ inOrder(root.getLeft()); System.out.println(root.element); inOrder(root.getRight()); } } /** * 中序遍历 * 【非递归实现】 * @param root */ public void inOrder2(Node root){ if(root == null){ return; } ArrayList list = new ArrayList<>(); Stack stack = new Stack<>(); while(!stack.isEmpty() || root != null){ if(root != null){ stack.push(root); root = root.getLeft(); }else { root = stack.pop(); list.add((T)root.element); root = root.getRight(); } } for(T i : list){ System.out.println(i); } }

后序遍历

/** * 后序遍历 * 【递归实现】 * @param root */ public void proOrder(Node root){ if(root != null){ proOrder(root.getLeft()); proOrder(root.getRight()); System.out.println(root.getElement()); } } /** * 后序遍历 * 【非递归实现】 * @param root */ public void proOrder2(Node root){ if(root == null){ return ; } ArrayList resultList = new ArrayList<>(); //操作栈 Stack stack = new Stack<>(); //结果栈，用于存放后序遍历的结果 Stack resultStack = new Stack<>(); Node p = root; while(!stack.isEmpty() || p != null){ if(p != null){ stack.push(p); resultStack.push(p); p = p.getRight(); }else{ p = stack.pop(); p = p.getLeft(); } } while(!resultStack.isEmpty()){ Node node = resultStack.pop(); resultList.add((T) node.element); } for(T i : resultList){ System.out.println(i); } }

5.寻找最大节点

/** * 找出最大节点 * @param node * @return */ public Node findMax(Node node){ Node maxNode = null; while(node != null){ maxNode = node; node = node.right; } return maxNode; }

6.寻找最小节点

/** * 找到最小节点 * @param node * @return */ public Node findMin(Node node){ Node minNode = null; while(node != null){ minNode = node; node = node.left; } return minNode; }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。