数据结构中树的类型

2025年3月17日 | 阅读 21 分钟

在理解数据结构中的树类型之前，让我们先了解什么是树作为数据结构。树可以定义为一种非线性数据结构，它以节点的形式存储数据，并且节点通过边相互连接。在所有节点中，有一个主节点称为根节点，所有其他节点都是这些节点的子节点。存在一些属性或规则，每个节点都应该遵循或满足。这些规则是：

每棵树都从一个主节点（称为根节点）开始。所有其他节点都是此根节点的子节点。根节点没有父节点。
树中的每个节点可以与父节点关联多个子节点，但每个子节点严格来说只能有一个父节点。
树中的每个父节点通过边与其子节点连接，该边用于在需要遍历树时进行遍历。在某些类型的树中，它们的边被赋予一个数字值，称为成本，用于确定遍历的总体成本，或者通过将连接到该特定节点与根节点的所有边相加来计算遍历该特定节点或遍历该节点的成本。

正如我们在上图中看到的，显示了一棵树，其根节点名为A，有三个子节点B、C和D。子节点B又有两个子节点E和F。同样，节点C有三个子节点G、H和I。节点D也有J和K作为子节点。如果我们想遍历到节点J，首先我们会从根节点A开始，然后去子节点D，最后到达节点J。

可用的树的各种类型

通用树
二叉树
二叉搜索树
AVL 树
红黑树
N叉树

现在让我们详细了解它们中的每一个，以便更好地理解它们。

通用树

通用树是树数据结构的基本形式之一。在通用树中，每个节点可以有零个或多于零个子节点。通用树的子树不保持有序属性。在通用树中，一个节点最多可以有 n（子节点数）个节点。如果不对树的层次结构施加任何限制，则该树称为通用树。在通用树中，每个节点都可以有无限数量的子节点。树是所有其他树的超集。

代码

// Java program to create and level order traverse a generic or general tree
 
// util package is imported to use classes like Queue and LinkedList
import java.util.*;
 
 
// a public class named GeneralTree is created
public class GeneralTree{
 
 
// A inner class named Node is created representing a single node of a generic tree
static class Node
{
 
// The class Node has two class variables named key and child of int type and Vector<Node> type respectively.
 
int key;
Vector<Node >child = new Vector<>();
};
 
 
// An Utility function named newNode is created to add a new child node to an already existing tree node
public static Node newNode(int key)
{
 
// a temporary node is created and then it is attached as a child to the existing parent node
Node temp = new Node();
temp.key = key;
return temp;
}
 
// a public static function named LevelOrderTraversal is created to print all the nodes in the tree level-wise starting from the root node which passed a parameter to the LevelOrderTraversal fucntion
 
public static void LevelOrderTraversal(Node root)
{
if (root == null)
return;
 
// Standard level order traversal code
// Queue is used to traverse the tree level-wise starting from the root node
Queue<Node > q = new LinkedList<>(); // Create a queue
q.add(root); // Enqueue root
while (!q.isEmpty()){
 
int n = q.size();
 
// If this node has children
while (n > 0)
{
// Dequeue an item from queue
// and print it
Node p = q.peek();
q.remove();
System.out.print(p.key + " ");
 
// Enqueue all children of
// the dequeued item
for (int i = 0; i < p.child.size(); i++)
q.add(p.child.get(i));
n--;
}
// One level is completed
// Now nodes in the next level is printed in the next line and same task is repeated each time the nodes in a level are exhausted
System.out.println();
}
}
 
// main function is created to call all the above created functions and create a general tree
public static void main(String[] args){
/* Now we will be creating this general tree using the Node class objects
*                      10
*     /   /     \      \
*   2   34   56    100
*   / \   |     /  |  \
*           77  88        1   7  8  9
*/
 
 
// creating a root node with value 10
Node root_node = newNode(10);
 
// adding four childs to the root node having values 2, 34, 56, adn 100 respectively
(root_node.child).add(newNode(2));
(root_node.child).add(newNode(34));
(root_node.child).add(newNode(56));
(root_node.child).add(newNode(100));
 
// adding two child nodes to the first child node of the root node having values 77, and 88 respectively
(root_node.child.get(0).child).add(newNode(77));
(root_node.child.get(0).child).add(newNode(88));
 
 
// adding one child nodes to the third child node of the root node having values 1
(root_node.child.get(2).child).add(newNode(1));
 
// adding three child nodes to the fourth child node of the root node having values 7, 8, and 9 respectively
(root_node.child.get(3).child).add(newNode(7));
(root_node.child.get(3).child).add(newNode(8));
(root_node.child.get(3).child).add(newNode(9));
 
System.out.println("Printing the nodes of tree level wise :");
System.out.println("Level order traversal : ");
 
LevelOrderTraversal(root_node);
}
 
}
//end of the public GeneralTree Class

输出

Printing the nodes of tree level wise :
Level order traversal :
(level 0) 10
(level 1) 2 34 56 100
(level 2) 77 88 1 7 8 9

在上面编写的代码中，我们创建了一个名为 GenralTree 的类，其中有一个名为 Node 的静态内部类，它将表示树的实际节点。我们还有一个公共静态函数 newNode，用于将新节点添加到树中，并将新添加节点的值作为参数传递给此 newNode 函数。

在 main 函数中，我们首先创建了一个名为 Node 的内部静态类的对象作为根节点，其值为 10。然后，我们向根节点添加了四个子节点，其值为 2、34、56 和 100。新添加的四个子节点将位于第 1 层，根节点将位于第 0 层。现在，我们向第 1 层中的第一个节点（即值为 2 的节点）添加了两个子节点，其值分别为 77 和 88。此外，我们向第 1 层中的第二个节点（即值为 34 的节点）添加了一个子节点，其值为 1。最后，我们向第 1 层中的最后一个节点（即值为 100 的节点）添加了三个子节点，其值分别为 7、8 和 9。

成功创建树后，我们按层级打印了树，这意味着会打印一层中的节点，然后打印下一层中的节点，直到耗尽树中的所有节点。

为了按层级打印树，我们创建了一个名为 LevelOrderTraversal 的函数，它将按层级打印树。在成功创建树之后，我们将根节点作为参数传递给 LevelOrderTraversal 函数来调用它。

二叉树

二叉树可以定义为一种树，其中每个父节点最多可以添加两个子节点。子节点称为左子节点和右子节点。二叉树是最流行的树之一。当我们对二叉树应用各种约束和特性时，会形成各种其他树，例如 AVL 树、BST（二叉搜索树）、RBT 树等。我们将在后续讨论中详细解释这些类型的树。

换句话说，我们可以说，一个元素最多有两个子节点的通用树称为二叉树。由于二叉树中的每个元素最多只有 2 个子节点，我们通常称它们为左子节点和右子节点。

二叉树节点包含以下部分：

数据
指向左子节点的指针
指向右子节点的指针

代码

// Java program to create and level order traverse a binary tree
 
 
// util package is imported to use classes like Queue and LinkedList
import java.util.*;
 
 
 
// A class named Node is created representing a single node of a binary tree
class Node{
 
 
  // The class Node has three class variables named key and left and right of int type and Node type respectively.
 
 
  // the key variable holds the actual value that is assigned to that node of the binary tree
  int key;
 
  // left and right variables that are of Node type will be used to store the left and right child nodes of the parent of the binary tree
  Node left, right;
 
// a parameterized constructor is created to create and add data to the node at the same time.
  public Node(int item)
  {
    key = item;
    left = right = null;
  }
 
 }
// end of node class definition
 
// A public class named BinaryTree is created having two constructors and methods to print the binary tree level-wise.
 
class BinaryTree{
 
  // A static variable named root_node is created that will represent the node of the binary tree
  static Node root_node;
 
 
 
 
  // A parametrized constructor of the BinaryTree class is written having the key as a parameter
  BinaryTree(int key)
  {
 
// here we are constructing a new node and assigning it to the root node
    root_node = new Node(key);
  }
 
  BinaryTree()
  {
    root_node = null;
  }
 
 
 
// a public static function named printLevelOrder is created to print all the nodes in the tree level-wise starting from the root node
 
 public static void printLevelOrder()
    {
        int h = height(root_node);
        int i;
        for (i=1; i<=h; i++){
            printCurrentLevel(root_node, i);
            System.out.println();
          }
    }
 
// a public static function named height is created to fund the height of the binary tree starting from the root node to the farthest leaf node that is present in the binary tree
 
// the root node of the binary tree is passed as a parameter to the public static function named height
 
    public static int height(Node root){
 
        if (root == null)
           return 0;
        else
        {
            /* compute  height of each subtree */
            int lheight = height(root.left);
            int rheight = height(root.right);
             
            /* use the larger one */
            if (lheight > rheight)
                return(lheight+1);
            else return(rheight+1);
        }
    }
 
 
// a Public static function named printCurrrntLevel is created to print al the nodes that are present in that level
 
// this function is called repeatedly for the each level of the binary tree
 
   public static void printCurrentLevel (Node root ,int level)
    {
        if (root == null)
            return;
        if (level == 1)
            System.out.print(root.key + " ");
        else if (level > 1)
        {
            printCurrentLevel(root.left, level-1);
            printCurrentLevel(root.right, level-1);
        }
    }
 
 
//the main function is created to create an object of the BinaryTree class and call the printLevelOrder method to level-wise print the nodes of the binary tree
 
  public static void main(String[] args){
 
    
 
 
    // first of all we have created an Object of the BinaryTree class that will represent the binary tree
    BinaryTree tree = new BinaryTree();
 
 
    // now a new node with the value as 150 is added as the root node to the Binary Tree
    tree.root_node = new Node(150);
 
    // now a new node with the value 250 is added as a left child to the root node
    tree.root_node.left = new Node(250);
 
    // now a new node with the value 270 is added as a right child to the root node
    tree.root_node.right = new Node(270);
 
 
    // now a new node with the value 320 is added as a left child to the left node of the previous level node
    tree.root_node.left.left = new Node(320);
 
 
    // now a new node with the value 350 is added as a right child to the right node of the previous level node
    tree.root_node.left.right = new Node(350);
 
    /*
               150
         /          \
       250         270
        /     \       /      \
      320 350  null  null
 
*/
 
 
 
    System.out.println("Printing the nodes of tree level wise :");
    System.out.println("Level order traversal : ");
    tree.printLevelOrder();
 
  }
}
// end of the BinaryTree class

输出

Printing the nodes of tree level wise :
Level order traversal :
(level 0) 150
(level 1) 250 270
(level 2) 320 350

在上面编写的代码中，我们创建了一个名为 BinaryTree 的类，其中有一个名为 Node 的另一个类，它将表示树的实际节点。

在 main 函数中，我们首先创建了一个名为 Node 的类的对象作为根节点，其值为 150。然后，我们向根节点添加了两个子节点，其值分别为 250 和 270。新添加的两个子节点将位于第 1 层，根节点将位于第 0 层。现在，我们向第 1 层中的第一个节点（即值为 250 的节点）添加了两个子节点，其值分别为 320 和 350。

成功创建树后，我们按层级打印了树，这意味着会打印一层中的节点，然后打印下一层中的节点，直到耗尽树中的所有节点。

为了按层级打印树，我们创建了一个名为 printLevelOrder 的函数，它将按层级打印树。在成功创建树之后，我们调用了 printLevelOrder 函数。

二叉搜索树

二叉搜索树（也称为 BST）是具有各种限制的二叉树的扩展。

二叉搜索树中的主要约束是，节点左子节点的值应小于或等于父节点的值，并且右子节点的值应大于或等于父节点的值。

顾名思义，二叉搜索树最适合搜索操作，因为在每个节点，我们都可以确定移动到哪里，也就是说，如果我们处于某个节点，并且我们的搜索键的值小于该节点的值，那么我们需要向左移动，反之亦然，如果搜索键的值更大。

代码

// Java program to create and level order traverse a binary search tree
 
 
 public class BinarySearchTree {
 
// A class named Node is created representing a single node of a binary search tree
class Node{
 
// The class Node has three class variables named key and left and right of int type and Node type respectively.
 
 
   // the key variable holds the actual value that is assigned to that node of the binary tree
int key;
 
// left and right variables that are of Node type will be used to store the left and right child nodes of the parent of the binary tree
Node left, right;
 
 
// a parameterized constructor is created to create and add data to the node at the same time.
public Node(int item){
 
key = item;
left = right = null;
}
}
 
 
 
// A static variable named root_node is created that will represent the node of the binary search tree
static Node root_node;
 
// A parametrized constructor of the BinaryTree class is written having the key as a parameter
BinarySearchTree()
{
root_node = null;
}
 
void insert(int key)
{
root_node = insertRec(root_node, key);
}
 
Node insertRec(Node root, int key)
{
 
//If the tree is empty, return a new node
 
if (root == null)
{
root = new Node(key);
return root;
}
 
// Otherwise, recur down the tree
if (key < root.key)
root.left = insertRec(root.left, key);
else if (key > root.key)
root.right = insertRec(root.right, key);
 
// return the (unchanged) node pointer
return root;
}
 
 
 
// a public static function named printLevelOrder is created to print all the nodes in the tree level-wise starting from the root node
 
public static void printLevelOrder()
    {
        int h = height(root_node);
        int i;
        for (i=1; i<=h; i++){
            printCurrentLevel(root_node, i);
            System.out.println();
          }
    }
 
// a public static function named height is created to fund the height of the binary tree starting from the root node to the farthest leaf node that is present in the tree
 
// the root node of the binary tree is passed as a parameter to the public static function named height
 
    public static int height(Node root){
 
        if (root == null)
           return 0;
        else
        {
            /* compute  height of each subtree */
            int lheight = height(root.left);
            int rheight = height(root.right);
             
            /* use the larger one */
            if (lheight > rheight)
                return(lheight+1);
            else return(rheight+1);
        }
    }
 
 
// a Public static function named printCurrrntLevel is created to print all the nodes that are present in that level
 
// this function is called repeatedly for each level of the tree
 
   public static void printCurrentLevel (Node root ,int level)
    {
        if (root == null)
            return;
        if (level == 1)
            System.out.print(root.key + " ");
        else if (level > 1)
        {
            printCurrentLevel(root.left, level-1);
            printCurrentLevel(root.right, level-1);
        }
    }
 
 
 
 
 
 
//the main function is created to create an object of the BinaryTree class and call the printLevelOrder method to level-wise print the nodes of the tree
public static void main(String[] args){
 
 
// first of all we have created an Object of the BinarySearchTree class that will represent the binary search tree
BinarySearchTree tree = new BinarySearchTree();
 
/* Let us create following BST
     50
/  \
            30          70
           /   \  /   \
        20   40      60  80
*/
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);
 
 
System.out.println("Printing the nodes of tree level wise :");
     System.out.println("Level order traversal : ");
tree.printLevelOrder();
 
}
}
// end of BinarySearchTree class

输出

Printing the nodes of tree level wise :
Level order traversal :
(level 0) 50
(level 1) 30 70
(level 2) 20 40 60 80

在上面编写的代码中，创建了一个以值为 50 的根节点为根的二叉搜索树，然后分别向其添加了一个值为 30 的左子节点和值为 70 的右子节点。然后，我们向第 1 层中的左子节点（值为 20 和 40）添加了一个左子节点和右子节点；之后，我们向根节点的第 1 层中的右子节点（值为 60 和 80）添加了一个左子节点和右子节点。

成功创建树后，我们按层级打印了树，这意味着会打印一层中的节点，然后打印下一层中的节点，直到耗尽树中的所有节点。

为了按层级打印树，我们创建了一个名为 printLevelOrder 的函数，它将按层级打印树。在成功创建树之后，我们调用了 printLevelOrder 函数。

AVL 树

AVL 树可以定义为一种自平衡二叉搜索树。AVL 这个名字是以发明者 Adelson-Velshi 和 Landis 的名字命名的。AVL 树具有动态平衡树节点的属性。添加了一个名为平衡因子的附加指标，用于确定 AVL 树中每个节点是否需要平衡树或子树。节点的高度最多为 1。在 AVL 树中，正确的平衡因子是 1、0 和 -1。如果树有新节点，它将被旋转以确保其平衡。

AVL 树中的查看、插入和删除等各种操作需要 O(log n) 的时间。它主要应用于查找操作。

代码

// Java program to create and level order traverse a AVL tree
 
 
 
// A class named Node is created representing a single node of a tree
class Node {
 
// The class Node has three class variables named key and left and right of int type and Node type respectively.
 
   // the key variable holds the actual value that is assigned to that node of the tree
int key, height;
Node left, right;
 
Node(int d) {
key = d;
height = 1;
}
}// end of Node class
 
 
 
public class AVLTree {
 
// A static variable named root_node is created that will represent the node of the tree
static Node root_node;
 
// A function named height is written to get the height of the tree
int height(Node N) {
if (N == null)
return 0;
 
return N.height;
}
 
// A utility function to get maximum of two integers
int max(int a, int b) {
return (a > b) ? a : b;
}
 
Node rightRotate(Node y) {
Node x = y.left;
Node T2 = x.right;
 
x.right = y;
y.left = T2;
 
y.height = max(height(y.left), height(y.right)) + 1;
x.height = max(height(x.left), height(x.right)) + 1;
 
// Return new root
return x;
}
 
 
// A utility function to left rotate subtree rooted with x
Node leftRotate(Node x) {
Node y = x.right;
Node T2 = y.left;
 
// Perform rotation
y.left = x;
x.right = T2;
 
// Update heights
x.height = max(height(x.left), height(x.right)) + 1;
y.height = max(height(y.left), height(y.right)) + 1;
 
// Return new root
return y;
}
 
 
// Get Balance factor of node N
int getBalance(Node N) {
if (N == null)
return 0;
 
return height(N.left) - height(N.right);
}
 
 
// insert fucntion to add node(s) to the AVL
Node insert(Node node, int key) {
 
// Perform the normal BST insertion
if (node == null)
return (new Node(key));
 
if (key < node.key)
node.left = insert(node.left, key);
else if (key > node.key)
node.right = insert(node.right, key);
else // Duplicate keys not allowed
return node;
 
// Update height of this ancestor node
node.height = 1 + max(height(node.left),
height(node.right));
 
// Get the balance factor of this ancestor node to check whether this node became unbalanced
int balance = getBalance(node);
 
// If this node becomes unbalanced, then there are 4 cases Left Left Case
if (balance > 1 && key < node.left.key)
return rightRotate(node);
 
// Right Right Case
if (balance < -1 && key > node.right.key)
return leftRotate(node);
 
// Left Right Case
if (balance > 1 && key > node.left.key) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
 
// Right Left Case
if (balance < -1 && key < node.right.key) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
 
return node;
}
 
 
 
 
// a public static function named printLevelOrder is created to print all the nodes in the tree level-wise starting from the root node
public static void printLevelOrder()
     {
        int h = height_tree(root_node);
        int i;
        for (i=1; i<=h; i++){
            printCurrentLevel(root_node, i);
            System.out.println();
          }
    }
 
// a public static function named height is created to fund the height of the binary tree starting from the root node to the farthest leaf node that is present in the tree
// the root node of the binary tree is passed as a parameter to the public static function named height
    public static int height_tree(Node root){
 
        if (root == null)
           return 0;
        else
        {
            /* compute  height of each subtree */
            int lheight = height_tree(root.left);
            int rheight = height_tree(root.right);
             
            /* use the larger one */
            if (lheight > rheight)
                return(lheight+1);
            else return(rheight+1);
        }
    }
 
 
// a Public static function named printCurrrntLevel is created to print all the nodes that are present in that level
// this function is called repeatedly for each level of the binary tree
    public static void printCurrentLevel (Node root ,int level)
    {
        if (root == null)
            return;
        if (level == 1)
            System.out.print(root.key + " ");
        else if (level > 1)
        {
            printCurrentLevel(root.left, level-1);
            printCurrentLevel(root.right, level-1);
        }
    }
 
 
 
    //the main function is created to create an object of the BinaryTree class and call the printLevelOrder method to level-wise print the nodes of the binary tree
public static void main(String[] args) {
AVLTree tree = new AVLTree();
 
tree.root_node = tree.insert(tree.root_node, 24);
tree.root_node = tree.insert(tree.root_node, 87);
tree.root_node = tree.insert(tree.root_node, 45);
tree.root_node = tree.insert(tree.root_node, 12);
tree.root_node = tree.insert(tree.root_node, 33);
tree.root_node = tree.insert(tree.root_node, 94);
 
/* The resultant AVL Tree is
45
/  \
        24   87
        /  \     \
     12  33  94
*/
 
System.out.println("Printing the nodes of tree level wise :");
     System.out.println("Level order traversal : ");
 
tree.printLevelOrder();
}
}

输出

Printing the nodes of tree-level wise :
Level order traversal :
45
24 87
12 33 94

红黑树

与 AVL 树一样，红黑树也是一种自动平衡树。之所以称为红黑树，是因为每个节点根据某些条件具有红色或黑色的特定颜色。由于它是一种自平衡树，它会维护树的整体平衡。在 AVL 树上，搜索操作只需 O(log n) 时间。在红黑树中添加新节点会导致现有节点旋转，以维护红黑树的属性。

代码

// Java program to create and level order traverse a Reb-black tree
 
import static java.lang.Integer.max;
 
// A public class named RBTree is created
public class RBTree {
TreeNode Root = null;
 
 
// Function named HeightT is created to get the Height of the tree
int HeightT(TreeNode Root){
int lefth, righth;
 
if (Root == null
|| (Root.children == null
&& Root.children[1] == null)) {
return 0;
}
lefth = HeightT(Root.children[0]);
righth = HeightT(Root.children[1]);
 
return (max(lefth, righth) + 1);
}
 
// Function named check is written to check whether dir is empty or not
int check(int dir){
 
return dir == 0 ? 1 : 0;
}
 
// Function named isRed is written to check whether color of the node is red or not
boolean isRed(TreeNode Node){
 
return Node != null
&& Node.color.equals("R");
}
 
// Function named SingleRotate is written to do single rotation
TreeNode SingleRotate(TreeNode Node,int dir){
 
TreeNode temp
= Node.children[check(dir)];
Node.children[check(dir)]
= temp.children[dir];
temp.children[dir] = Node;
Root.color = "R";
temp.color = "B";
 
return temp;
}
 
// Function named DoubleRotate is written to do Double rotation
TreeNode DoubleRotate(TreeNode Node,int dir){
 
Node.children[check(dir)]= SingleRotate(Node.children[check(dir)],check(dir));
return SingleRotate(Node, dir);
}
 
// To add a new node to the tree a fucntion named Insert is written
TreeNode Insert(RBTree tree,String data){
 
if (tree.Root == null) {
tree.Root= new TreeNode(data);
if (tree.Root == null)
return null;
}
else {
 
// A temporary root
TreeNode temp = new TreeNode("");
 
// Grandparent and Parent
TreeNode g, t;
TreeNode p, q;
 
int dir = 0, last = 0;
 
t = temp;
 
g = p = null;
 
t.children[1] = tree.Root;
 
q = t.children[1];
while (true) {
 
if (q == null) {
 
// Inserting root node
q = new TreeNode(data);
p.children[dir] = q;
}
 
// Sibling is red
else if (isRed(q.children[0])
&& isRed(q.children[1])) {
 
// Recoloring if both
// children are red
q.color = "R";
q.children[0].color = "B";
q.children[1].color = "B";
}
 
if (isRed(q) && isRed(p)) {
 
// Resolving red-red
// violation
int dir2;
if (t.children[1] == g) {
dir2 = 1;
}
else {
dir2 = 0;
}
 
// If children and parent
// are left-left or
// right-right of grand-parent
if (q == p.children[last]) {
t.children[dir2]= SingleRotate(g,last == 0? 1: 0);
}
 
// If they are opposite
// childs i.e left-right
// or right-left
else {
t.children[dir2]= DoubleRotate(g,last == 0? 1: 0);
}
}
 
// Checking for correct
// position of node
if (q.data.equals(data)) {
break;
}
last = dir;
 
// Finding the path to
// traverse [Either left
// or right ]
dir = q.data.compareTo(data) < 0? 1: 0;
 
if (g != null) {
t = g;
}
 
// Rearranging pointers
g = p;
p = q;
q = q.children[dir];
}
 
tree.Root = temp.children[1];
}
 
// Black color is assigned to the root node
tree.Root.color = "B";
 
return tree.Root;
}
 
 
/////////////PRINTING A TREE/////////////////////
 
 
 
// a public function named printLevelOrder is created to print all the nodes in the tree level-wise starting from the root node
public void PrintLevel(TreeNode root, int i){
 
if (root == null) {
return;
}
 
if (i == 1) {
System.out.print("| "+ root.data+ " | "+ root.color+ " |");
 
if (root.children[0] != null) {
System.out.print(" "+ root.children[0].data+ " |");
}
else {
System.out.print(" "+ "NULL"+ " |");
}
 
 
if (root.children[1] != null) {
System.out.print(" "+ root.children[1].data+ " |");
}
else {
System.out.print(" "+ "NULL"+ " |");
}
 
System.out.print(" ");
 
return;
}
 
PrintLevel(root.children[0],
i - 1);
PrintLevel(root.children[1],
i - 1);
}
 
 
 
// A utility fucntion named LevelOrder is written to print the tree
void LevelOrder(TreeNode root){
 
int i;
 
for (i = 1;i < HeightT(root) + 1;i++){
 
PrintLevel(root, i);
System.out.print("\n\n");
}
}
}
 
 
// A class named TreeNode is created representing a single node of a tree
class TreeNode {
 
// Class variables
String data, color;
TreeNode children[];
 
public TreeNode(String data){
 
// Color R- Red
// and B - Black
this.data = data;
this.color = "R";
children
= new TreeNode[2];
children[0] = null;
children[1] = null;
}
} // end of the TreeNode class
 
// Main Class
class Main{
 
 
 
//the main function is created to create an object of the RBTree class and call the printLevelOrder method to level-wise print the nodes of the tree
public static void main(String ... nk)
{
// Representation of a Node is like:
// -------------------------------------------
// DATA | COLOR | LEFT CHILD | RIGHT CHILD |
// -------------------------------------------
 
RBTree Tree = new RBTree();
String Sentence, Word;
Sentence = "ONE TWO THREE FOUR";
String arr[] = Sentence.split(" ");
 
for (int i = 0;i < arr.length;i++) {
Tree.Root = Tree.Insert(Tree, arr[i]);
}
 
System.out.println("Printing the nodes of tree level wise :");
     System.out.println("Level order traversal : ");
System.out.println("");
Tree.LevelOrder(Tree.Root);
}
 
}// end of the Main class

输出

Printing the nodes of tree level wise :
Level order traversal :
 
| THREE | B | ONE | TWO |
 
| ONE | B | FOUR | NULL | | TWO | B | NULL | NULL |
 
| FOUR | R | NULL | NULL |

因此，在上面的代码中，我们成功地实现了具有插入和遍历操作的红黑树。输出中打印的数据顺序是：

节点中的数据
该节点的颜色
该特定节点的左子节点
该特定节点的右子节点

如果树的右子节点或左子节点为 NULL，则表示该特定节点分别没有右子节点或左子节点。

N叉树

在 N 叉树中，与前面的父节点关联的最大子节点数是 N。N 叉树与通用树或泛型树非常相似，后者也可以在树中包含任意数量的节点。

在 Java 编程语言中，N 叉树的实现与通用树完全相同。

因此，在本文中，我们清楚地了解了不同类型的树，并简要地回顾了它们中的每一种，以便更好地理解。我们还为通用树、二叉树、二叉搜索树、AVL 树、红黑树和 N 叉树等所有这些类型的树实现了示例 Java 代码。

下一主题数据结构中的抽象数据类型

数据结构中树的类型

通用树

二叉树

二叉搜索树

AVL 树

红黑树

N叉树

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

数据结构中树的类型

通用树

二叉树

二叉搜索树

AVL 树

红黑树

N叉树

相关帖子

股票收益问题

将二叉搜索树中的所有大于值的节点加上

后缀树导论

二叉树的垂直遍历

构建线性类型后缀

Kasai 算法从后缀数组构建 LCP 数组

螺旋形式打印给定矩阵

整数流的（运行）中位数

找出最后一个拿到票的人（队列中的问题）

数据结构中的 LIFO 方法

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器