二叉樹的構成
二叉樹由節點(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;
}
}
}
}
}
}