二叉树是一种重要的数据结构，在计算机科学中有着广泛的应用。它是由节点（Node）和分支边（Branch）构成的树状结构，每个节点最多只有两个分支，分别称为左子节点和右子节点。在Java编程中，实现简单二叉树可以利用节点操作来完成。

首先，我们需要创建一个节点类Node，定义以下属性：

public class Node {
  int key;
  String value;
  Node leftChild;
  Node rightChild;
  
  // 构造方法
  public Node(int key, String value)
    this.key = key;
    this.value = value;
  
}

可以看到，节点类中包含了key和value属性，用来存储键值对。leftChild和rightChild分别表示左子节点和右子节点，如果节点没有子节点，则为null。

接着，我们创建一个简单二叉树类BinaryTree，定义以下操作：

public class BinaryTree {
  Node root;
  
  // 添加节点
  public void put(int key, String value) {
    Node newNode = new Node(key, value);
    if (root == null)
      root = newNode;
     else {
      Node current = root;
      Node parent;
      while (true) {
        parent = current;
        if (key < current.key) {
          current = current.leftChild;
          if (current == null)
            parent.leftChild = newNode;
            return;
          
        } else {
          current = current.rightChild;
          if (current == null)
            parent.rightChild = newNode;
            return;
          
        }
      }
    }
  }
  
  // 查找节点
  public Node get(int key) {
    Node current = root;
    while (current != null) {
      if (current.key == key)
        return current;
       else if (key < current.key)
        current = current.leftChild;
       else
        current = current.rightChild;
      
    }
    return null;
  }
  
  // 删除节点
  public boolean delete(int key) {
    Node current = root;
    Node parent = root;
    boolean isLeftChild = true;
    while (current.key != key) {
      parent = current;
      if (key < current.key)
        isLeftChild = true;
        current = current.leftChild;
       else
        isLeftChild = false;
        current = current.rightChild;
      
      if (current == null)
        return false;
      
    }
    if (current.leftChild == null && current.rightChild == null) {
      if (current == root)
        root = null;
       else if (isLeftChild)
        parent.leftChild = null;
       else
        parent.rightChild = null;
      
    } else if (current.rightChild == null) {
      if (current == root)
        root = current.leftChild;
       else if (isLeftChild)
        parent.leftChild = current.leftChild;
       else
        parent.rightChild = current.leftChild;
      
    } else if (current.leftChild == null) {
      if (current == root)
        root = current.rightChild;
       else if (isLeftChild)
        parent.leftChild = current.rightChild;
       else
        parent.rightChild = current.rightChild;
      
    } else {
      Node successor = getSuccessor(current);
      if (current == root)
        root = successor;
       else if (isLeftChild)
        parent.leftChild = successor;
       else
        parent.rightChild = successor;
      
      successor.leftChild = current.leftChild;
    }
    return true;
  }
  
  // 获取后继节点
  public Node getSuccessor(Node delNode) {
    Node successor = delNode;
    Node successorParent = delNode;
    Node current = delNode.rightChild;
    while (current != null)
      successorParent = successor;
      successor = current;
      current = current.leftChild;
    
    if (successor != delNode.rightChild)
      successorParent.leftChild = successor.rightChild;
      successor.rightChild = delNode.rightChild;
    
    return successor;
  }
}

添加节点操作put()用来向二叉树中添加节点，查找节点操作get()用来查找指定键值的节点，删除节点操作delete()用来删除指定键值的节点。其中，删除节点时需要通过getSuccessor()方法获取当前节点的后继节点来替换，这里不再赘述。

最后，我们来测试一下我们实现的简单二叉树：

public class TestBinaryTree {
  public static void main(String[] args) {
    BinaryTree binaryTree = new BinaryTree();
    binaryTree.put(5, "E");
    binaryTree.put(3, "C");
    binaryTree.put(7, "G");
    binaryTree.put(1, "A");
    binaryTree.put(4, "D");
    binaryTree.put(6, "F");
    binaryTree.put(8, "H");
    Node node = binaryTree.get(3);
    System.out.println(node.value); //输出：C
    binaryTree.delete(5);
    node = binaryTree.get(5);
    System.out.println(node); //输出：null
  }
}

可以看到，我们成功地实现了简单二叉树，并且对其进行了一系列操作，完成了节点的添加、查找和删除。通过这个例子，我们可以更好地理解二叉树的应用及其实现方法。

相似文章

友情链接
• 网站定制开发
• 帮你发
• 小蓄群站获客
• 雅圣洁家政