0

给定完整二叉树的前序遍历，其中每个节点都标记为叶节点或内部节点，是否有一个好的算法来找到树的高度？例如，如果 N 代表一个内部节点，L 代表一个叶子，那么给定前序遍历 NLNNLLL，高度将为 3。

4

1 回答 1

1

好吧，我不禁为我们将 marti 留在评论中而感到难过。我认为他真的不知道从哪里开始，并且至少表明他已经考虑过这个问题。

我们对完全二叉树了解多少？每个节点要么是叶子，要么有两个孩子。

前序遍历递归地访问根，左子树，然后右子树。

想一想这个问题：在（完整二叉树的）前序遍历中的什么时候，我们知道我们已经用尽了一个子树？我们将访问它的根，然后访问两片叶子（如果是叶子，则只访问根）。

让我们制作一个特殊结构的堆栈：

struct StackNode{
   size_t count; //initialize to 0
   char nodeType; //'N' or 'L'
};

这个“StackNode”对象将使用“nodeType”变量跟踪我们在前序遍历中访问的节点类型，这应该很清楚。我们还有一个特殊的计数器“计数”，我们将其初始化为 0。

解决方案背后的想法是这样的：

  • 每次遇到“N”时，创建一个 StackNode，并将其压入堆栈。
  • 每次遇到“L”时，创建一个 StackNode，并将其压入堆栈
  • 如果您压入堆栈的最后一个节点是“L”，则弹出最后一个节点，然后将 stack.top() 的计数加 1
  • 如果 stack.top() 的计数为 2，则从堆栈中弹出顶部，然后将 stack.top() 的计数增加 1（重复直到堆栈为空或您已停止从堆栈中弹出）

每次将节点压入堆栈时，都可以检查树的当前高度。它是您的 stack-1 中的项目数（说明底部的项目是根）。

只要您跟踪到目前为止遇到的最大高度，您就会找到树的高度。

让我们来看看你的例子：NLNNLLL

堆栈最初是空的。

int maxHeight = -1;

处理第一个字符：N

将一个节点压入堆栈：

堆栈：类型计数

  • N, 0

    最大高度 = 0；

处理下一个字符：L

将一个节点压入堆栈：

  • L, 0

  • N, 0

    最大高度 = 1；//（增加1）

最后处理的字符是叶子，所以弹出并递增：

堆：

  • N, 1

    最大高度 = 1；

处理下一个字符：N

将一个节点压入堆栈：

  • N, 0

  • N, 1

    最大高度 = 1；//不变

处理下一个字符：N

将一个节点压入堆栈：

  • N, 0
  • N, 0

  • N, 1

    最大高度 = 2；//（增加1）

处理下一个字符：L

将一个节点压入堆栈：

  • L, 0
  • N, 0
  • N, 0

  • N, 1

    最大高度 = 3；//递增1

最后一个节点是叶子，所以pop和increment

堆：

  • N, 1
  • N, 0

  • N, 1

    最大高度 = 3；//不变

处理下一个字符：L

将一个节点压入堆栈：

  • L, 0
  • N, 1
  • N, 0

  • N, 1

    最大高度 = 3；//不变

最后一个节点是叶子，所以弹出并递增：

  • N, 2
  • N, 0
  • N, 1

顶部节点的计数为 2，因此弹出并递增：

  • N, 1
  • N, 1

处理下一个节点：L

将一个节点压入堆栈：

  • L, 0
  • N, 1

  • N, 1

    最大高度 = 3；//不变

最后一个节点是叶子，所以弹出并递增：

  • N, 2
  • N, 1

顶部节点的计数为 2，因此弹出并递增：

  • N, 2

顶部节点的计数为 2，因此弹出并递增：

(empty stack), finished

maxHeight = 3; //the maximum height discovered during a preorder of a full binary tree
于 2013-02-01T05:41:21.133 回答