什么是二叉树？

一棵树** **是一种非线性的数据结构，数据对象一般是按照层次关系组织的。这种结构是非线性的，因为与数组、关联列表、堆栈和队列不同，树中的数据不是线性组织的。**二叉树是一种递归的树形数据结构，每个节点最多可以有2个孩子。 **

二叉树在完美时有几个有趣的特性。

特性1：每个 "层次 "上的总节点数随着你在树上的移动而翻倍。
特性2：T**，最后一层的节点数等于所有其他层的节点数之和，再加1**。

存储在树形结构中的每个数据元素称为*节点。*一个树形节点包含以下部分。

1. 数据*
   *2. 指向左边子节点的指针
2. 指向右边子节点的指针

在Java中，我们可以用类来表示一个树节点。下面是一个带有整数数据的树节点的例子。

static class Node {    
	int value; 
        Node left, right; 
         
        Node(int value){ 
            this.value = value; 
            left = null; 
            right = null; 
        }

现在你知道什么是二叉树了，让我们来看看不同类型的二叉树。

二叉树的类型

全二进制树

全二叉树是一棵二叉树，每个节点正好有0或2个孩子。全二进制树的例子是。

完美二叉树

如果所有的内部节点都有两个孩子，而且所有的叶子都在同一级别，那么这棵二叉树就是完美二叉树。完美二叉树的例子是。

完整的二叉树

完全二叉树是指除了可能的最后一级之外，每一级都被完全填满的二叉树，而且所有的节点都尽可能的靠左。一个完整二叉树的例子是。

现在你已经了解了不同类型的二叉树，让我们来看看如何创建一棵二叉树。

二叉树的实现

对于实现来说，有一个辅助的Node类，它将存储int值，并保持对每个孩子的引用。第一步是找到我们要添加新节点的地方，以便保持树的排序。我们将遵循这些规则，从根节点开始。

• 如果新节点的值比当前节点的值低，就去找左边的子节点。
• 如果新节点的值大于当前节点的值，则转到右边的子节点
• 当当前节点为*空时，*我们已经到达了一个叶子节点，我们在该位置插入新节点。

现在让我们借助一个例子来看看我们如何实现这个逻辑。

package MyPackage;
 
public class Tree { 
	static class Node {    
	int value; 
        Node left, right; 
         
        Node(int value){ 
            this.value = value; 
            left = null; 
            right = null; 
        } 
    } 
      
    public void insert(Node node, int value) {
        if (value < node.value) { if (node.left != null) { insert(node.left, value); } else { System.out.println(" Inserted " + value + " to left of " + node.value); node.left = new Node(value); } } else if (value > node.value) {
          if (node.right != null) {
            insert(node.right, value);
          } else {
            System.out.println("  Inserted " + value + " to right of "
                + node.value);
            node.right = new Node(value);
          }
        }
      }
     public void traverseInOrder(Node node) {
        if (node != null) {
            traverseInOrder(node.left);
            System.out.print(" " + node.value);
            traverseInOrder(node.right);
        }
     }
    
     public static void main(String args[]) 
    { 
    Tree tree = new Tree();
    		    Node root = new Node(5);
    		    System.out.println("Binary Tree Example");
    		    System.out.println("Building tree with root value " + root.value);
    		    tree.insert(root, 2);
    		    tree.insert(root, 4);
    		    tree.insert(root, 8);
    		    tree.insert(root, 6);
    		    tree.insert(root, 7);
    		    tree.insert(root, 3);
    		    tree.insert(root, 9);
    		    System.out.println("Traversing tree in order");
    		    tree.traverseLevelOrder();
    		   
    		  }
}

输出：

Binary Tree Example
Building tree with root value 5
  Inserted 2 to left of 5
  Inserted 4 to right of 2
  Inserted 8 to right of 5
  Inserted 6 to left of 8
  Inserted 7 to right of 6
  Inserted 3 to left of 4
  Inserted 9 to right of 8
Traversing tree in order
 2 3 4 5 6 7 8 9

在这个例子中，我们使用了内序遍历法来遍历树。内序遍历包括首先访问左边的子树，然后是根节点，最后是右边的子树。还有更多的方法来遍历一棵树。让我们来看看它们。

树的遍历*

树可以用多种方式进行遍历。让我们用之前用过的同一个树的例子来说明每种情况。 

深度第一搜索

深度优先搜索是一种遍历方式，你在一条路径上尽可能地深入，然后再退回来尝试另一条路径。有几种方法来执行深度优先搜索。顺序内、顺序前和顺序后。 

我们已经检查过了in-order遍历。现在让我们来看看前顺序和后顺序。

前序遍历

在前序遍历中，你首先访问根节点，然后是左子树，最后是右子树。下面是代码。

public void traversePreOrder(Node node) {
    if (node != null) {
        System.out.print(" " + node.value);
        traversePreOrder(node.left);
        traversePreOrder(node.right);
    }
}

输出：

5 2 4 3 8 6 7 9

后序遍历

在后序遍历中，你首先访问左子树，然后是右子树，最后是根节点。下面是代码。

public void traversePostOrder(Node node) {
    if (node != null) {
        traversePostOrder(node.left);
        traversePostOrder(node.right);
        System.out.print(" " + node.value);
    }
}

输出：

3 4 2 7 6 9 8 5

宽度优先搜索

这种类型的遍历在进入下一层次之前会访问一个层次的所有节点。这就像在一个池塘的中心投下一块石头。你探索的节点会从起点 "荡漾开来"。广度优先搜索也被称为层序搜索，从根部开始，从左到右访问树的所有层次。

二叉树的应用

二叉树的应用包括。

• 在许多搜索应用中使用，其中数据不断进入/离开
• 作为一种工作流程，用于合成数字图像的视觉效果
• 在几乎所有的高带宽路由器中使用，用于存储路由器表
• 还用于无线网络和内存分配
• 在压缩算法中使用，还有更多
  这就是这篇 "Java中的树 "文章的结尾。