邊分析邊走
首先節(jié)點類：

/** 節(jié)點* value 儲存的值* left 左節(jié)點 right 右節(jié)點*/ 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的左右節(jié)點，（root的左右結構指針）這個可能和C 有點像，我也差異很久為啥root自己不能該然而root.left能改，原來root.left相當于指針，只不過被封裝起來。這樣理解之和二叉樹的插入就很好理解了；
• 刪除節(jié)點：刪除的規(guī)則就是先找到這個點。這個點用這個點的子樹可以補上的點填充該點，然后在以這個點為頭刪除替代的子節(jié)點（調用遞歸）然后在添加到最后情況（只有一個分支，等等）。首先要找到移除的位置，然后移除的那個點分類討論，如果有兩個兒子，就選右邊兒子的最左側那個點替代，然后再子樹刪除替代的那個點。如果是一個節(jié)點，判斷是左空還是右空，將這個點指向不空的那個。不空的那個就替代了這個節(jié)點。入股左右都是空，那么他自己變空null就刪除了。
• 遍歷：前序中序，后序都是遞歸實現(xiàn)，用隊列實現(xiàn)遍歷的那種方法就是bfs的雛形。（個人認為）非遞歸便利要稍微麻煩一點。

import java.util.ArrayDeque; import java.util.Queue;/** ADT查找二叉樹* 規(guī)則：* 父節(jié)點的值要比左側大，要比右側小*/ 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&&current!=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;} //判斷 函數(shù)其實無法改變參數(shù)的值，但是可以調用其指針，改變。所以要直接用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)//左右節(jié)點均不空{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 " ");//當前節(jié)點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 " "); //訪問玩左右訪問當前節(jié)點 } }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 " ");//訪問完左節(jié)點訪問當前節(jié)點zhongxu(t.right);}}public void zhongxu2(node t)//先儲藏所有左側點，拋出一個點，訪問該點右節(jié)點，對右節(jié)點在儲存所有子左節(jié)點{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);}} }}

測試類和數(shù)據(jù)：

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

不知道還有啥錯誤的或者不準確的，請大神糾正

如果對后端、爬蟲等感性趣歡迎關注我的個人公眾號交流：bigsai

總結

以上是生活随笔為你收集整理的java实现简单的二叉树ADT的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。