如何在 C 中不使用递归求二叉树的高度？

Question

能否不用递归的情况下用C语言得到二叉树最大深度的逻辑。

Answer 1

要在不使用递归的情况下获取树的高度，就是对树进行 BFS（非递归）。并跟踪您所达到的级别。最后一层的数字应该是你的树的深度。

上述方法的伪代码应该是这样的：

Q: Queue like data structure
root: root of your tree
couter = 0 // variable which will denote depth.
1. Q -> add ( root)
2. while ( Q is not empty) 
2.1 size = Q-> size ();
  2.2 while( size -- > 0)
  2.2.1 Process your tree
  2.2.2 Increment: Counter 
  End of While (2.2)
End of While (2)

Answer 2

这是获取树高度的非递归方法

int heightOfBinaryTree(struct BinaryTree *root) {
if (!root) {
    return 0;
}
int level = 0;

// queue to traverse the tree
struct Queue *q = createQueue();

// end of first level
enqueue(q, NULL);

while (!isEmpty(q)) {
    root = dequeue(q);
    // completion of first level.

    if (root == NULL) {
        // put another mark for next level
        if (!isEmpty(q)) {
            enqueue(q, NULL);
            level++;
        }
        else {
            if (root -> left) {
                enqueue(q, root -> left);
            }
            if (root -> right) {
                enqueue(q, root -> right);
            }
        }
    }
}

return level;

}