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]);
      }   
   }
}

输出

打印页面