遍历树数据结构，在一个循环中找到它的高度和计数元素

Question

我有一个树结构。

class Element {
    private List<Element> children;
}

Element treeStructure = produceSomeTreeStructure();
//How to get its height and number of elements.

直接的解决方案是制作两个循环。首先我可以找到节点数

A question on getting number of nodes in a Binary Tree （为非二叉树改变这个算法），

第二个循环获取树的高度 http://www.geeksforgeeks.org/iterative-method-to-find-height-of-binary-tree/

再次将此算法应用于非二叉树。

我的问题是，如何一步完成。将结果保存在全局变量中对我来说是可以接受的。

Answer 1

如果您想知道节点数，则需要探索整棵树。最简单的方法是使用深度优先搜索，即边走边计算节点数。

深度优先搜索算法还可以很容易地计算出当前正在探索的深度，以及总体上达到的最大深度。修改深度优先搜索算法以将这两个作为参数。

如果您以递归方式对其进行编码（最简单），则每次进行递归调用时只需将深度参数加一即可。如果这为您提供的数字大于您跟踪的最大值，则将最大值更新为当前深度。

Answer 2

是的，可以按照下面的代码所示完成。只需添加计数器 totalNodeCount 并在每次以 BFS 样式遍历节点时执行 +1。

// Iterative method to find height and node-count of Binary Tree
int treeHeightAndNumOfNodes(node *root)
{
    // Base Case
    if (root == NULL)
        return 0;

    // Create an empty queue for level order tarversal
    queue<node *> q;

    // Enqueue Root and initialize height
    q.push(root);
    int height = 0;
    int totalNodeCount = 0; // <-- Use this counter to store total number of node traversed.

    while (1)
    {
        // nodeCount (queue size) indicates number of nodes
        // at current lelvel.
        int nodeCount = q.size();
        if (nodeCount == 0)
            return height;

        height++;

        // Dequeue all nodes of current level and Enqueue all
        // nodes of next level
        while (nodeCount > 0)
        {
            node *node = q.front();
            q.pop();
            if (node->left != NULL)
                q.push(node->left);
            if (node->right != NULL)
                q.push(node->right);
            nodeCount--;
            totalNodeCount++;    // <--  Update this counter
        }
    }
}

Again, adapt this algorithm to non-binary tree.

为此，将下面给出的代码行替换为遍历每个子节点并将 NON-NULL 子节点推入队列的循环。

if (node->left != NULL)
    q.push(node->left);
if (node->right != NULL)
    q.push(node->right);

Answer 3

你要找的有点像 BFS。你只需要像下面这样走你的树：

int getHeight(Element e) {
    int max_height = 0;
    for (Element child : e.children) {
        max_height = max(max_height, getHeight(child));
    }
    return max_height + 1;
}

同样，获取元素总数也很容易：无需获取节点子节点中的最大值，只需将它们相加即可。

int getTotalCount(Element e) {
    int total_count = 0;
    for (Element child : e.children) {
        total_count += getTotalCount(el);
    }
    return total_count + 1;
}

如果您必须 return 使用相同函数的两个数字，只需将它们打包在一个公共 class 中以便仅遍历您的树一次。

Answer 4

感谢大家的回答。

这就是我编写的代码。

public static TreeData countElementsAndFindHeight(Element root) {
    TreeData treePair = new TreeData();
    if (root == null) {
        return treePair;
    }

    treePair.nElements = 1;
    treePair.height = 1;

    //Nodes queue will contain all the elements of the trees, so its size is the number of elements.
    List<Element> nodesQueue = new LinkedList<Element>();

    treePair.walkedNodes = nodesQueue;

    List<Element> children = root.getChildren();
    if (CommonUtils.isCollectionEmpty(children)) {
        return treePair;
    }

    treePair.height = countElementsAndFindHeight(root, nodesQueue);
    nodesQueue.add(root);
    treePair.nElements = nodesQueue.size();

    return treePair;
}


private static int countElementsAndFindHeight(Element root, List<Element> nodesQueue) {
    int maxHeight = 1;
    List<Element> children = root.getChildren();
    if (CommonUtils.isCollectionEmpty(children)) {
        return maxHeight;
    }

    for (Element childElement : children) {
        int childHeight = countElementsAndFindHeight(childElement, nodesQueue);
        if (childHeight > maxHeight) {
            maxHeight = childHeight;
        }
        nodesQueue.add(childElement);
    }

    return maxHeight + 1;
}

public static class TreeData {

    protected int height = 0;
    protected int nElements = 0;
}

遍历树数据结构，在一个循环中找到它的高度和计数元素

Walk tree data structure to find its height and count elements in one loop

java

algorithm

tree