二叉查找树

我就是我 2022-05-13 01:40 279阅读 0赞

<table> 
 <tbody> 
 <tr> 
 <td> package 树; import java.util.Stack; /** &nbsp;* 定义一个结点 &nbsp;*/ class Node{ &nbsp;&nbsp; &nbsp;Node left = null; &nbsp;&nbsp; &nbsp;Node right = null; &nbsp;&nbsp; &nbsp;Integer data; &nbsp;&nbsp; &nbsp;public Node(Integer data){ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;this.data = data; &nbsp;&nbsp; &nbsp;} } public class BinarySearchTree { &nbsp;&nbsp; &nbsp;Node root = null; &nbsp;&nbsp; &nbsp; &nbsp;&nbsp; &nbsp;/** &nbsp;&nbsp; &nbsp; * 添加元素 &nbsp;&nbsp; &nbsp; */ &nbsp;&nbsp; &nbsp;public void addNode(Integer data){ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;Node node = new Node(data); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;if(root == null){ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;root = node; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;return; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;Node temp = root; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;while(true){ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;if(data&lt;temp.data){//小于的情况 &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;if(temp.left == null){ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;temp.left = node; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;return; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;}else{ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;temp = temp.left; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;}else if(data&gt;temp.data){//大于的情况 &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;if(temp.right == null){ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;temp.right = node; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;return; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;}else{ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;temp = temp.right; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;}else{ //相等的情况（去重复） &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;return; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp; &nbsp;&nbsp; &nbsp;/** &nbsp;&nbsp; &nbsp; * 删除元素 &nbsp;&nbsp; &nbsp; * 思路： &nbsp;&nbsp; &nbsp; * &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;如果节点是叶子结点，可以直接删除。 &nbsp;&nbsp; &nbsp; * &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;如果节点有一个子节点，则将父节点直接指向其子节点。 &nbsp;&nbsp; &nbsp; * &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;如果节点有两个子节点（最为复杂），用其右子树中的最小的数据代替该节点的数据并递归地删除那个节点。 &nbsp;&nbsp; &nbsp; */ &nbsp;&nbsp; &nbsp; &nbsp;&nbsp; &nbsp;/** &nbsp;&nbsp; &nbsp; * 判断是否包含某元素 &nbsp;&nbsp; &nbsp; */ &nbsp;&nbsp; &nbsp;public boolean isContains(Integer data){ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;if(root == null){ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;return false; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;Node temp = root; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;while(true){ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;if(data&lt;temp.data){//小于的情况 &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;if(temp.left == null){ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;return false; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;}else{ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;temp = temp.left; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;}else if(data&gt;temp.data){//大于的情况 &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;if(temp.right == null){ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;return false; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;}else{ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;temp = temp.right; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;}else{ //相等的情况 &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;return true; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp; &nbsp;&nbsp; &nbsp;/** &nbsp;&nbsp; &nbsp; * 求二叉搜索树的高度 &nbsp;&nbsp; &nbsp; */ &nbsp;&nbsp; &nbsp;public int getHeight(){ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;return getHeight(root); &nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp; &nbsp;&nbsp; &nbsp;private int getHeight(Node node) { &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;if(node == null){ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;return 0; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;int i = getHeight(node.left); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;int j = getHeight(node.right); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;return (i&gt;j)?i+1:j+1; &nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;/** &nbsp;&nbsp; &nbsp; * 求二叉搜索树的节点个数 &nbsp;&nbsp; &nbsp; */ &nbsp;&nbsp; &nbsp;public int getSize(){ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;return getSize(root); &nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp; &nbsp;&nbsp; &nbsp;private int getSize(Node node) { &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;if(node == null){ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;return 0; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;return 1+getSize(node.left)+getSize(node.right); &nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp; &nbsp;&nbsp; &nbsp;/** &nbsp;&nbsp; &nbsp; * 求二叉搜索树中的最大值 &nbsp;&nbsp; &nbsp; */ &nbsp;&nbsp; &nbsp;public Integer getMax(){ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;if(root == null){ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;return null; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;Node temp = root; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;while(temp.right!=null){ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;temp = temp.right; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;return temp.data; &nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp; &nbsp;&nbsp; &nbsp;/** &nbsp;&nbsp; &nbsp; * 求二叉搜索树中的最小值 &nbsp;&nbsp; &nbsp; */ &nbsp;&nbsp; &nbsp;public Integer getMin(){ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;if(root == null){ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;return null; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;Node temp = root; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;while(temp.left!=null){ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;temp = temp.left; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;return temp.data; &nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;/** &nbsp;&nbsp; &nbsp; * 前序遍历方法递归实现 &nbsp;&nbsp; &nbsp; */ &nbsp;&nbsp; &nbsp;private void preOrder(Node root) { &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;if(root == null){ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;return; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;}else{ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;System.out.print(root.data+" "); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;preOrder(root.left); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;preOrder(root.right); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp; &nbsp;&nbsp; &nbsp;/** &nbsp;&nbsp; &nbsp; * 前序遍历方法非递归实现 &nbsp;&nbsp; &nbsp; *&nbsp; &nbsp;&nbsp; &nbsp; * 思路： &nbsp;&nbsp; &nbsp; * &nbsp;&nbsp; &nbsp;栈s初始化 &nbsp;&nbsp; &nbsp; * &nbsp;&nbsp; &nbsp;在while(true)中循环 &nbsp;&nbsp; &nbsp; * &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;当root不空时循环 &nbsp;&nbsp; &nbsp; * &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;输出root.data &nbsp;&nbsp; &nbsp; * &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;将指针root的值保存到栈中 &nbsp;&nbsp; &nbsp; * &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;继续遍历root的左子树 &nbsp;&nbsp; &nbsp; * &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;如果栈s为空，break； &nbsp;&nbsp; &nbsp; * &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;如果栈s不为空，则 &nbsp;&nbsp; &nbsp; * &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;将栈顶元素弹出至root &nbsp;&nbsp; &nbsp; * &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;准备遍历root的右子树 &nbsp;&nbsp; &nbsp; */ &nbsp;&nbsp; &nbsp;public void pre(Node root){ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;//栈的初始化，建一个空栈 &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;Stack&lt;Node&gt; stack = new Stack&lt;Node&gt;(); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;//循环 &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;while(true){ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;//当root不为空时 &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;while(root!=null){ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;//输出根节点 &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;System.out.print(root.data+" "); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;//根节点进栈 &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;stack.push(root); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;//继续遍历左子树，迭代 &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;root = root.left; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;//当栈为空时 &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;if(stack.isEmpty()){ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;break; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;}else{//当栈不为空时 &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;root = stack.pop();//出栈，栈顶元素传给root &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;root = root.right; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp; &nbsp;&nbsp; &nbsp;/** &nbsp;&nbsp; &nbsp; * 中序遍历方法递归实现 &nbsp;&nbsp; &nbsp; */ &nbsp;&nbsp; &nbsp;private void midOrder(Node root) { &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;if(root == null){ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;return; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;}else{ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;midOrder(root.left); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;System.out.print(root.data+" "); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;midOrder(root.right); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp; &nbsp;&nbsp; &nbsp;/** &nbsp;&nbsp; &nbsp; * 中序遍历方法非递归实现 &nbsp;&nbsp; &nbsp; */ &nbsp;&nbsp; &nbsp;public void mid(Node root){ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;//栈的初始化，建一个空栈 &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;Stack&lt;Node&gt; stack = new Stack&lt;Node&gt;(); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;//循环 &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;while(true){ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;//当root不为空时 &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;while(root!=null){ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;//根节点进栈 &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;stack.push(root); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;//继续遍历左子树，迭代 &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;root = root.left; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;//当栈为空时 &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;if(stack.isEmpty()){ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;break; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;}else{//当栈不为空时 &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;root = stack.pop();//出栈，栈顶元素传给root &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;//输出根节点 &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;System.out.print(root.data+" "); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;root = root.right; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp; &nbsp;&nbsp; &nbsp;/** &nbsp;&nbsp; &nbsp; * 后序遍历方法递归实现 &nbsp;&nbsp; &nbsp; */ &nbsp;&nbsp; &nbsp;private void aftOrder(Node root) { &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;if(root == null){ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;return; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;}else{ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;aftOrder(root.left); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;aftOrder(root.right); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;System.out.print(root.data+" "); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp; &nbsp;&nbsp; &nbsp;/** &nbsp;&nbsp; &nbsp; * 后序遍历方法非递归实现 &nbsp;&nbsp; &nbsp; */ &nbsp;&nbsp; &nbsp;public void aft(Node root){ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;//栈的初始化，建一个空栈 &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;Stack&lt;Node&gt; stack = new Stack&lt;Node&gt;(); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;//循环 &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;while(true){ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;//当root不为空时 &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;while(root!=null){ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;//根节点进栈 &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;stack.push(root); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;//继续遍历左子树，迭代 &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;root = root.left; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;//当前结点的左右子节点都为空时，输出 &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;//当前结点的右子节点输出后，该节点可以随之输出 &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;while(!stack.isEmpty() &amp;&amp; stack.peek().right==root){ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;root = stack.pop(); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;System.out.print(root.data+" "); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;//当栈为空时 &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;if(stack.isEmpty()){ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;break; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;}else{//当栈不为空时 &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;root = stack.peek().right; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp; &nbsp;&nbsp; &nbsp; &nbsp;&nbsp; &nbsp;/** &nbsp;&nbsp; &nbsp; * 主函数 &nbsp;&nbsp; &nbsp; */ &nbsp;&nbsp; &nbsp;public static void main(String[] args) { &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;BinarySearchTree bst = new BinarySearchTree(); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;//构建二叉搜索树 &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;int[] arr = {4,5,1,2}; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;for(int i:arr){ &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;bst.addNode(i); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;} &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;System.out.println("中序遍历："); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;bst.midOrder(bst.root); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;System.out.println(); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;System.out.println("中序遍历："); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;bst.mid(bst.root); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;System.out.println(); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;System.out.println("前序遍历(递归)："); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;bst.preOrder(bst.root); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;System.out.println(); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;System.out.println("前序遍历(非递归)："); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;bst.pre(bst.root); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;System.out.println(); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;System.out.println("后序遍历(递归)："); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;bst.aftOrder(bst.root); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;System.out.println(); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;System.out.println("后序遍历(非递归)："); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;bst.aft(bst.root); &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;System.out.println(); &nbsp;&nbsp; &nbsp;} } </td> 
 </tr> 
 </tbody> 
</table>