Java 使用链表实现二叉树的程序

在此程序中，我们需要通过插入节点和按中序方式显示节点来创建二叉树。一个典型的二叉树可以表示如下

在二叉树中，每个节点最多可以有两个子节点。每个节点可以有零个、一个或两个子节点。二叉树中的每个节点包含以下信息

Data 表示节点中存储的值。

Left 表示指向左子节点的指针。

Right 表示指向右子节点的指针。

算法

定义 Node 类，该类包含三个属性：data、left 和 right。这里，left 表示节点的左子节点，right 表示节点的右子节点。

• 创建节点时，数据将传递到节点的 data 属性，left 和 right 都将设置为 null。
• 定义另一个类，该类有一个 root 属性。
  • Root 表示树的根节点，并将其初始化为 null。

a. insert() 将向树添加一个新节点

• 它检查 root 是否为 null，这意味着树是空的。它将新节点添加为 root。
• 否则，它将 root 添加到队列中。
• 变量 node 表示当前节点。
• 首先，它检查节点是否有左子节点和右子节点。如果有，它将两个节点都添加到队列中。
• 如果左子节点不存在，它将新节点添加为左子节点。
• 如果左子节点存在，则它将新节点添加为右子节点。

a. Inorder() 将按中序方式显示树的节点。

• 它遍历整个树，然后打印左子节点，然后是根节点，然后是右子节点。

程序

输出

Binary tree after insertion
1 
Binary tree after insertion
2 1 3 
Binary tree after insertion
4 2 5 1 3 
Binary tree after insertion
4 2 5 1 6 3 7