以非递归方式获取二叉树节点的深度 [英] Retrieving a Binary-Tree node's depth non-recursively

问题描述

任何人都可以指出一种无需使用递归即可获取二叉树(非平衡树或BST)中二叉树深度的方法吗?理想地使用Java/C/C#

Can anyone point out a way of getting the depth of a Node in a Binary Tree (not a balanced one, or BST) without using recursion? Ideally in Java/C/C#

该节点表示为:

class Node
{
  Node Left;
  Node Right;
  string Value;
  int Depth;
}

将等级顺序与FIFO列表结合使用是我的第一个想法，但是我很困惑地检测到等级何时发生变化，尤其是对于不平衡的树木.

Using Level Order with a FIFO list was my first thought, but I was stumped at detecting when the level changes, particular for unbalanced trees.

推荐答案

您可以使用堆栈实现任何递归方法，无论如何，这都是递归的工作方式.想象一下您的递归函数看起来像

You can implement any resursive method with a stack, which is how resursion works anyways. Imagine your resursive function looks like

function int getDepth (Node head, string val)
{
    if (head == NULL)
        return -1;

    if (val == head.Value)
        return head.Depth;

    return MAX(getDepth(head.Left, val), getDepth(head.Right, val);
}

非递归函数看起来像

function int getDepth (Node head, string val)
{
    Stack s = new Stack();

    s.push(head);

    while(s.count > 0)
    {
        Node temp = s.pop();

        if (temp != NULL)
        {
            if (s.Value == val)
                return s.Depth;
            else
            {
                s.push(temp.Left);
                s.push(temp.Right);
            }
        }

    }


    return -1;
}

此功能设置每个节点的深度

This function sets the depth for each node

function void setDepth (Node head)
{
    Stack s = new Stack();

    head.Depth = 0;
    s.push(head);

    while(s.count > 0)
    {
        Node temp = s.pop();

        if (temp != NULL)
        {
            if (temp.Left != NULL)
            {
                temp.Left.Depth = temp.Depth + 1;
                s.push(temp.Left);
            }

            if (temp.Right != NULL)
            {
                temp.Right.Depth = temp.Depth + 1;
                s.push(temp.Right);
            }
        }

    }

}

这篇关于以非递归方式获取二叉树节点的深度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！