N元树数据结构

约定不等于承诺〃 2023-10-04 09:03 25阅读 0赞

## 一元树数据结构 ##

N元树是一棵树，它使我们可以拥有`n`一个特定节点的子节点数目，因此命名为**N-ary**，这使其**比非常常见的二叉树（**使我们最多具有两个特定子节点的**树）更为复杂。**节点。

N元树的图形表示如下所示：

在上面显示的N元树中，我们可以注意到总共有**11个节点**，**有些节点有3个子节点**，有些只有一个。在二叉树的情况下，存储这些子节点更为容易，因为我们可以将两个节点（即左右）分配给一个特定的节点以标记其子节点，但这并不是那么简单。为了存储任何树节点的子节点，我们使用了另一种数据结构，主要是C ++中的vector和Java中的LinkedList。

### N元树的实现 ###

处理非线性数据结构时，我们要做的第一件事就是为它们创建自己的结构（Java中的构造函数）。就像在二叉树的情况下一样，我们使用一个类，`TreeNode`并且在该类内部，我们创建了构造函数并具有了类级变量。

考虑下面的代码片段：

public static class TreeNode{
            int val;
            List<TreeNode> children = new LinkedList<>();
    
            TreeNode(int data){
                val = data;
            }
    
            TreeNode(int data,List<TreeNode> child){
                val = data;
                children = child;
            }
    }

在上面的代码片段中，我们有一个名为的类，该类`TreeNode`又包含两个具有相同名称的构造函数，但实际上它们是重载的（相同的方法名称，但参数不同）。我们还有两个标识符，其中之一是val，用于存储任何特定节点的值，然后，我们具有一个List，用于存储树的任何节点的子节点。

上面的代码段包含了我们树的基本结构，现在只剩下一个树了，随后我们将看到如何使用级别顺序遍历来打印树。为了构建一棵树，我们将利用我们在上面的类中定义的构造函数。

考虑下面的代码片段：

public static void main(String[] args) {
            // creating an exact replica of the above pictorial N-ary Tree
            TreeNode root = new TreeNode(1);
            root.children.add(new TreeNode(2));
            root.children.add(new TreeNode(3));
            root.children.add(new TreeNode(4));
            root.children.get(0).children.add(new TreeNode(5));
            root.children.get(0).children.add(new TreeNode(6));
            root.children.get(0).children.add(new TreeNode(7));
            root.children.get(1).children.add(new TreeNode(8));
            root.children.get(2).children.add(new TreeNode(9));
            root.children.get(2).children.add(new TreeNode(10));
            root.children.get(2).children.add(new TreeNode(11));
            printNAryTree(root);
    }

首先，我们创建**了N元树**的**根节点**，然后必须为该根节点分配一些子节点，方法是使用dot（`.`）运算符并访问该根节点的children属性，然后然后使用`List`接口提供的add方法将不同的子级添加到根节点。一旦添加了根节点的所有子节点，就该添加每个新级别节点的子节点了，我们首先通过使用list接口提供的get方法访问该节点，然后添加相应的子节点来进行此操作节点到该节点。

最后，我们打印此N元树，我们通过调用`printNAryTree`方法来做到这一点。

现在，由于打印一棵树并不像遍历一组项目那样简单，因此我们可以使用不同的技术（精确地计算算法）。这些主要是：

*  **有序遍历**
 *  **预购遍历**
 *  **后订单遍历**
 *  **级别顺序遍历**

在本教程中，我们将使用“级别顺序遍历”方法，因为它很容易理解，前提是您之前已经了解了它如何在二叉树上工作。

#### 级别顺序遍历（打印N元树） ####

对任何树的“级别顺序”遍历都考虑到这样一个事实，我们要先在根级别上打印节点，然后再转到下一个级别，并继续重复此过程，直到我们到达最后一个级别为止。我们利用队列数据结构来存储特定级别的节点。

考虑下面显示的简单N元树：

以上树的“级别顺序遍历”如下所示：

1
    2 3 4 5

考虑下面的代码片段：

private static void printNAryTree(TreeNode root){
            if(root == null) return;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while(!queue.isEmpty()) {
                int len = queue.size();
                for(int i=0;i<len;i++) { // so that we can reach each level
                    TreeNode node = queue.poll();
                    System.out.print(node.val + " ");
                    for (TreeNode item : node.children) { // for-Each loop to iterate over all childrens
                        queue.offer(item);
                    }
                }
                System.out.println();
            }
    }

整个代码如下所示：

import java.util.LinkedList;
    import java.util.List;
    import java.util.Queue;
    
    public class NAryTree {
        public static class TreeNode{
            int val;
            List<TreeNode> children = new LinkedList<>();
    
            TreeNode(int data){
                val = data;
            }
    
            TreeNode(int data,List<TreeNode> child){
                val = data;
                children = child;
            }
        }
    
        private static void printNAryTree(TreeNode root){
            if(root == null) return;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while(!queue.isEmpty()) {
                int len = queue.size();
                for(int i=0;i<len;i++) {
                    TreeNode node = queue.poll();
                    assert node != null;
                    System.out.print(node.val + " ");
                    for (TreeNode item : node.children) {
                        queue.offer(item);
                    }
                }
                System.out.println();
            }
        }
    
        public static void main(String[] args) {
            TreeNode root = new TreeNode(1);
            root.children.add(new TreeNode(2));
            root.children.add(new TreeNode(3));
            root.children.add(new TreeNode(4));
            root.children.get(0).children.add(new TreeNode(5));
            root.children.get(0).children.add(new TreeNode(6));
            root.children.get(0).children.add(new TreeNode(7));
            root.children.get(1).children.add(new TreeNode(8));
            root.children.get(2).children.add(new TreeNode(9));
            root.children.get(2).children.add(new TreeNode(10));
            root.children.get(2).children.add(new TreeNode(11));
            printNAryTree(root);
        }
    }

上面代码的输出是：

1 2 3 4 5 6 7 8 9 10 11

我们可以将此输出与开始时使用的N元树的图形表示形式进行比较，每个级别节点包含相同的值。

### 一元树的类型 ###

以下是N元树的类型：

#### 1.完整的N元树 ####

完整N元树是一个N元树，它允许每个节点具有0个或N个子节点。

考虑以下所示的完整N元树的图形表示形式：

请注意，以上N元的所有节点都具有4个子节点或0个子节点，因此满足该属性。

#### 2.完整的N元树 ####

完整的N元树是一棵N元树，其中除最后一级节点外，该树的每一级上的节点都应完整（应该有**N个子**节点），如果最后一级节点不完整，则这些节点必须“尽可能左”。

考虑以下所示的完整N元树的图形表示形式：