我也不會二叉樹，今天就學學

二叉樹的構成

二叉樹由節點（node）和邊組成。節點分為根節點、父節點、子節點。 

紅色是根節點（root）。藍色是子節點也是父節點，綠色的是子節點。

其餘的線是邊。節點和鏈表中的節點一樣都可以存放數據信息。

* 通常來說樹是頂部小，底部大，且樹呈分層結構。

* root節點時第0層，以此類推。二叉樹最多有兩個節點。
*
* 二叉樹一個節點左子節點的關鍵字小於這個節點，

* 右子節點關鍵字大於或等於這個父節點。


創建一個樹節點包含左節點引用和右節點引用

public class Node {

 public int iData;

 public double dDate;

 public Node leftNode;//左節點

 public Node rightNode;//右節點

 private Node root;//根節點


//最大值和最小值查找，
 

//應為是從root開始查找，那麼最小值肯定是在root的左面，最大值肯定是在root的右面

//最小值存在於一棵樹的最下的左node，最大值存在於一棵樹的最大的有node

public Node[] mVal(){
 Node minNode = null;
 Node maxNode = null;

 //創建一個數組用來保存最大和最小值
 Node[] minmaxnode = new Node[2];

 //從根節點開始,把根節點賦值給current
 Node current = root;

 //死循環，只要當前node不為null,就把它左面的node賦值給current，一直到最後一個，就是最小的了

 while (current != null){

 //假設這個值是最小node
 minNode = current;

 //再把這個node左面的node賦值給crrrent，知道為null，循環就退出了
 current = current.leftNode;
 }

 minmaxnode[0] = minNode;

 //找最大的
 current = root;

 while(current != null){
 maxNode = current;
 current = current.rightNode;
 }
 

 minmaxnode[1]= maxNode;
 return minmaxnode;
}


//查找數據
public Node find(int key){

 //從根節點開始
 Node current = root;

 //如果傳入的值和根節點的值不一致，繼續，否則返回根節點
 //死循環，下一個current就是下面賦值給的左面或者是右面的節點，直到滿足條件，找到需要的值

 while (current.iData != key){

 //如果節點的值比key大，那麼就把左面的節點賦值給當前
 if(current.iData > key){

 current = root.leftNode;
 }else{
 current = root.rightNode;
 }

 //到這裡就直接全部遍歷完了都沒有找到
 if(current == null){
 return null;
 }
 }
 return current;
}



//往二叉樹中插入數據，插入的過程中會比較大小，所以查找的時間也是比較快
 

public void insert(int iData ,double dDate){

 //創建node節點
 Node newNode = new Node();
 newNode.iData = iData;
 newNode.dDate = dDate;

 //如果根節點沒有值，那麼剛創建的節點就是根節點
 if(root == null){
 root = newNode;
 }else{

 //把根節點賦值給current節點
 Node current = root;

 //創建一個parent節點保存根節點
 Node parent;

 while (true){
 //最終根據節點遍歷到左節點或者右節點為null
 //然後把新創建的節點賦值給當前current節點的左右節點
 //保存current變為null之前的父節點

 parent =current;

 //如果插入的數據比根節點的左面的數據小
 if(iData < current.iData){

 //那就遍歷左面的節點，每次都把左面的節點賦值給current
 current = current.leftNode;

 //如果current，也就左面的這個節點為null,那麼就把新節點放到左面
 if(current == null){
 parent.leftNode = newNode;
 return; 

 }
 }else {
 current = current.rightNode;
 if(current == null){
 parent.rightNode = newNode;
 return;
 }
 }
 }
 }
}


}