Java 資料結構教程

向樹中插入鍵

向二叉樹中插入元素沒有特別的規則，你可以在任何需要的地方插入節點。

插入節點時唯一需要注意的是，在二叉樹中，每個節點最多隻能有兩個子節點。

因此，要將節點插入樹中，

逐層遍歷每個節點，檢查它是否有左子節點和右子節點。
如果任何節點同時擁有左子節點和右子節點，則無法再插入另一個節點，因為二叉樹中的節點最多隻能有兩個子節點，將這些值新增到佇列中並繼續。
如果任何節點沒有左子節點或右子節點，則建立一個新節點並將其新增到那裡。

簡而言之，將節點插入到沒有左子樹或右子樹或兩者都沒有的父節點。

示例

演示

import java.util.LinkedList;
import java.util.Queue;

class Node{
   int data;
   Node leftNode, rightNode;
   
   Node() {
      leftNode = null;
      rightNode = null;     
      this.data = data;
   }
   Node(int data) {
      leftNode = null;
      rightNode = null;     
      this.data = data;
   }   
   int getData() {
      return this.data;	   
   }
   Node getleftNode() {
      return this.leftNode;	   
   }	   
   Node getRightNode() {
      return this.leftNode;	   
   }
   void setData(int data) {
      this.data = data; 
   }		   
   void setleftNode(Node leftNode) {
      this.leftNode = leftNode;	   
   }
   void setRightNode(Node rightNode) {
      this.leftNode = rightNode;	      
   }
}
public class InsertingElements {
   public static int[] insertElement(int[] myArray, int pos, int data) {
      int j = myArray.length;      
      int lastElement = myArray[j-1];      
	      
      for(int i = (j-2); i >= (pos-1); i--) {
         myArray[i+1] = myArray[i];
      }     
      myArray[pos-1] = data;
      
      int[] resultArray = new int[j+1];      
      for(int i = 0; i < myArray.length; i++) {
         resultArray[i] = myArray[i]; 
      }   
      resultArray[resultArray.length-1] = lastElement;
      return resultArray;
	}
	public static void main(String args[]){
      int[] myArray = {10, 20, 30, 45, 96, 66};      
      int pos = 3;
      int data = 10005;
      int[] result = insertElement(myArray, pos, data);   
      
      for(int i = 0; i < result.length; i++){
         System.out.println(result[i]);
      }   
   }
}

輸出

列印頁面