边分析边走
首先节点类：
/* * 节点 * value 储存的值 * left 左节点 right 右节点 */ public class node {//结点 public int value; public node left; public node right; public node() { } public node(int value) { this.value=value; this.left=null; this.right=null; } public node(int value,node l,node r) { this.value=value; this.left=l; this.right=r; } }
树类：在这个问题中查找较好理解，最左侧的最小，最右侧的最大
插入：要注意t虽然是root的引用，但是t无法直接改变root的value值，只能改变root的左右节点，（root的左右结构指针）这个可能和C 有点像，我也差异很久为啥root自己不能该然而root.left能改，原来root.left相当于指针，只不过被封装起来。这样理解之和二叉树的插入就很好理解了；
删除节点：删除的规则就是先找到这个点。这个点用这个点的子树可以补上的点填充该点，然后在以这个点为头删除替代的子节点（调用递归）然后在添加到最后情况（只有一个分支，等等）。首先要找到移除的位置，然后移除的那个点分类讨论，如果有两个儿子，就选右边儿子的最左侧那个点替代，然后再子树删除替代的那个点。如果是一个节点，判断是左空还是右空，将这个点指向不空的那个。不空的那个就替代了这个节点。入股左右都是空，那么他自己变空null就删除了。
遍历：前序中序，后序都是递归实现，用队列实现遍历的那种方法就是bfs的雏形。（个人认为）非递归便利要稍微麻烦一点。
import java.util.ArrayDeque; import java.util.Queue; /* * ADT查找二叉树 * 规则： * 父节点的值要比左侧大，要比右侧小 */ public class tree { public node root;//根 public tree() {root=null;} public void makeempty()//变空 {root=null;;} public boolean isempty()//查看是否为空 {return root==null;} public node findmin(node t)//查找最小返回值是node，调用查看结果时需要.value { if(t==null) {return null;} else if(t.left==null) {return t;} else return(findmin(t.left)); } public node findmax(node t)//查找最大 { if(t==null) {return null;} else if(t.right==null) {return t;} else return(findmax(t.right)); } public boolean iscontains(int x)//是否存在 { node current=root; if(root==null) {return false;} while(current.value!=x&¤t!=null) { if(xcurrent.value) {current=current.right;} if(current==null) {return false;}//在里面判断如果超直接返回 } //如果在这个位置判断是否为空会导致current.value不存在报错 if(current.value==x) {return true;} return false; } public node insert(int x,node t)//插入 t是root的引用 { node a1=new node(x); if(root==null) {root=a1;return root;} //判断 函数其实无法改变参数的值，但是可以调用其指针，改变。所以要直接用root（个人理解） if(t==null) {t=a1;return t;} else if(t!=null) { if(x=t.value) {t.right= insert(x,t.right);} } return t; } public node remove(int x,node t) { if(t==null) {return null;} if(xt.value) {t.right=remove(x,t.right);} else if(t.left!=null&&t.right!=null)//左右节点均不空 { t.value=findmin(t.right).value;//找到右侧最小值替代 t.right=remove(t.value,t.right); } else //左右单空或者左右都空 { if(t.left==null&&t.right==null) {t=null;} else if(t.right!=null) { t=t.right; } else if(t.left!=null) { t=t.left; } return t; } return t; } public void duilie(node t) { Queue q1 = new ArrayDeque(); if(t==null)return; if(t!=null) { q1.add(t);} while(!q1.isEmpty()) { node t1= q1.poll(); if(t1.left !=null)q1.add(t1.left); if(t1.right!=null)q1.add(t1.right); System.out.print(t1.value " "); } System.out.println(); } public void qianxu(node t)//前序递归 前序遍历：根结点 ---> 左子树 ---> 右子树 { if(t!=null) { System.out.print(t.value " ");//当前节点 qianxu(t.left ); qianxu(t.right);} } public void qianxu2(node t)//非递归前序 栈 先左后右 { Stack q1=new Stack(); if(t==null)return; if(t!=null) {q1.push(t);} while(!q1.empty()) { node t1=q1.pop(); if(t1.right!=null) {q1.push(t1.right);} if(t1.left!=null) {q1.push(t1.left);} System.out.print(t1.value " "); } } public void houxu(node t)//后序遍历 后序遍历：左子树 ---> 右子树 ---> 根结点 { if(t!=null) { houxu(t.left ); houxu(t.right); System.out.print(t.value " "); //访问玩左右访问当前节点 } } public void houxu2(node t)//q1和q2 q1要先右后左，先遍历右侧，q1先装右侧就把右侧放到前面，左侧放在上面（栈顶） { Stack q1=new Stack(); Stackq2=new Stack(); if(t==null)return; if(t!=null) {q1.push(t); } while(!q1.isEmpty()) { node t1=q1.pop(); q2.push(t1); if(t1.left!=null) {q1.push(t1.left);} if(t1.right!=null) {q1.push(t1.right);} } while(!q2.isEmpty()) { node t1=q2.pop(); System.out.print(t1.value " "); } } public void zhongxu(node t)//中序遍历 中序遍历：左子树---> 根结点 ---> 右子树 { if(t!=null) { zhongxu(t.left); System.out.print(t.value " ");//访问完左节点访问当前节点 zhongxu(t.right); } } public void zhongxu2(node t)//先储藏所有左侧点，抛出一个点，访问该点右节点，对右节点在储存所有子左节点 { Stack q1=new Stack(); if(t==null)return; if(t!=null) {q1.push(t);} node t1=q1.peek();//不能抛出，要先存最左侧 while(t1.left!=null) { t1=t1.left; q1.push(t1); } while(!q1.isEmpty()) { node t2=q1.pop(); System.out.print(t2.value " "); if(t2.right!=null) { t2=t2.right;q1.push(t2); while(t2.left!=null) {t2=t2.left; q1.push(t2);} } } }
测试类和数据：
public class exam2 { public static void main(String [] args) { tree a=new tree(); a.insert(5, a.root); a.insert(9, a.root); a.insert(8, a.root); a.insert(4, a.root); a.insert(2, a.root); a.insert(6, a.root); a.insert(7, a.root); a.insert(1, a.root); System.out.print("队列遍历"); a.duilie(a.root); System.out.print("前序遍历"); a.qianxu(a.root); System.out.print("非递归前序："); a.qianxu2(a.root); System.out.println(); System.out.print("后序遍历"); a.houxu(a.root); System.out.print("非递归后序："); a.houxu2(a.root); System.out.println(); System.out.print("中序遍历"); a.zhongxu(a.root); System.out.print("非递归中序："); a.zhongxu2(a.root); System.out.println(); System.out.println(a.iscontains(12)); System.out.println(a.iscontains(7)); System.out.println("min: " a.findmin(a.root).value); System.out.println("max: " a.findmax(a.root).value); a.remove(9, a.root); a.remove(8, a.root); System.out.print("前序遍历"); a.qianxu(a.root); System.out.println(); System.out.print("后序遍历"); a.houxu(a.root); System.out.println(); System.out.print("中序遍历"); a.zhongxu(a.root); } }
结果：
队列遍历5 4 9 2 8 1 6 7
前序遍历5 4 2 1 9 8 6 7 非递归前序：5 4 2 1 9 8 6 7
后序遍历1 2 4 7 6 8 9 5 非递归后序：1 2 4 7 6 8 9 5
中序遍历1 2 4 5 6 7 8 9 非递归中序：1 2 4 5 6 7 8 9
false
true
min: 1
max: 9
前序遍历5 4 2 1 6 7
后序遍历1 2 4 7 6 5
中序遍历1 2 4 5 6 7
不知道还有啥错误的或者不准确的，请大神纠正
