将随机二叉树表示为数组? [英] Represent a Random Binary Tree as Array?

问题描述

我正在阅读有关

我喜欢这是多么简单，但是在我的特定情况下，我需要存储一个随机的二叉树，其结构不一致.像这样的情况，在任何给定深度的节点数量都是不可预测的:

有没有一种简单的方法可以用数组实现类似的东西?

注意:答案中的语言没有偏爱.

解决方案

一个简单的解决方案可以简单地创建一个数组，就好像该树是完整的二叉树，然后填充丢失的节点带有空"单元格.

空值可以用特殊值(取决于域)来表示，例如:null，负整数等.

如果没有特殊值可用，则可以创建另一个相同大小的布尔数组，该数组将保存单元格是否为空?"的答案.

顺便说一句，这样的一棵树(每个节点最多具有2个孩子)被简单地称为二叉树(不需要单词 random ).您称为二叉树的树，其中每个节点都没有子节点或恰好有2个子节点，被称为完整二叉树.

I'm reading about Eytzinger's method for storing binary trees as an array.

I like how straight forward this is, but in my specific case I need to store a random binary tree, that isn't consistent in structure. Something like this where the amount of nodes at any given depth is not predictable:

Is there a simple method for implementing something like this with arrays?

Note: No preference on language in answers.

解决方案

A simple solution can be simply to create an array as if the tree was a full binary tree, and just fill the missing nodes with "empty" cells.

Empty can be indicated with special values (depending on the domain) for example: null, negative integer etc.

If no special values are available, you can create another same-sized Boolean array that will hold the answer to "is cell empty?".

By the way, such a tree, where each node has at most 2 children, is simply called a Binary Tree (no need for the word random). The tree that you call a Binary Tree, where every node has either no children or exactly 2 children, is called a Complete Binary Tree.

这篇关于将随机二叉树表示为数组?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！