查找树的高度赋予preorder [英] Find tree height given preorder

问题描述

由于满二叉树，其中每个节点被标记或者是叶节点或内部节点的preorder遍历，是有一个好的算法来寻找树的高度？例如，如果N重新presents内部节点和L重新presents一片叶子，然后给予preorder traverseal NLNNLLL，该高度将是3

Given a preorder traversal of a full binary tree, where each node is labeled either a leaf node or an internal node, is there a good algorithm to find the height of the tree? For example, if N represents an internal node and L represents a leaf, then given the preorder traverseal NLNNLLL, the height would be three.

推荐答案

好吧，我不禁心疼，我们要离开马蒂挂在评论。我想，他真的不知道从哪里开始，并至少表明，他想到了问题。

Alright, I can't help but feel bad that we're leaving marti hanging in the comments. I think he truly doesn't know where to start, and has at least demonstrated that he's thought about the problem.

我们所知道的满二叉树做？每个节点可以是叶或有两个孩子。

What do we know about a full binary tree? Each node is either a leaf or has two children.

一个preorder递归遍历访问根，左子树，然后右子树。

A preorder traversal recursively visits the root, left subtree, then right subtree.

想想这个问题：在什么时候在preorder遍历（满二叉树的），我们知道我们已经筋疲力尽子树？我们参观了它的根目录，然后两片叶子（或只是如果它是一个叶根）。

Think about this question: at what point in the preorder traversal (of a full binary tree) do we know we've exhausted a subtree? We will have visited its root, and then two leaves (or just the root if it's a leaf).

让我们一摞一个特殊的结构：

Let's make a stack of a special structure:

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

这StackNode对象追踪，我们参观了我们的preorder遍历什么类型的节点使用节点类型变量，这应该是清楚的。我们也有一个专柜计数我们初始化为0。

This 'StackNode' object will track what type of node we visited in our preorder traversal using the 'nodeType' variable, which should be clear. We also have a special counter 'count' which we initialize to 0.

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

The idea behind a solution would be this:

• 在每次遇到一个'N'，创造一个StackNode，并将其推入堆栈的时间。
• 在每次遇到一个L，创建一个StackNode，并将其推入堆栈时间
• 如果你压入堆栈中的最后一个节点是'L'，然后通过1
弹出的最后一个节点关闭，然后递增stack.top（）的数
• 如果stack.top（）的次数为2，然后弹出顶出栈，然后递增stack.top（）'由1秒计数（重复，直到堆栈为空或者你已经停止突然离开叠加）

• each time you encounter a 'N', create a StackNode, and push it onto the stack.
• each time you encounter a 'L', create a StackNode, and push it onto the stack
• if the last node you pushed onto the stack was 'L', then pop the last node off, and then increment stack.top()'s count by 1
• if stack.top()'s count is 2, then pop the top off the stack, and then increment stack.top()'s count by 1 (repeat until stack is empty or you've stopped popping off the stack)

你推一个节点到堆栈每一次，你可以检查你的树的当前高度。它是在你的栈-1项的数量（占在底部为根的项）。

Every time you push a node onto the stack, you can check the current height of your tree. It is the number of items in your stack-1 (accounting for the item on the bottom being the root).

只要你跟踪你所遇到迄今的最大高度，你会发现你的树的高度。

As long as your track the maximum height you've encountered thus far, you will find the height of your tree.

让我们携手通过你的例如： NLNNLLL

Let's work through your example: NLNNLLL

堆栈最初是空的。

int maxHeight = -1;

---

过程的第一个字符： N

推一个节点到堆栈：

堆栈：类型数量

• N，0

• N, 0

=了maxHeight 0;

maxHeight = 0;

工艺下一个字符：→

推一个节点到堆栈：

• L，0

• N，0

• L, 0

• N, 0

了maxHeight = 1; //（加1）

maxHeight = 1; //(incremented by 1)

处理的最后一个字符是一片叶子，所以流行和增量：

The last character processed was a leaf, so pop and increment:

堆栈：

• N，1

• N, 1

=了maxHeight 1;

maxHeight = 1;

工艺下一个字符： N

推一个节点到堆栈：

• N，0

• N，1

• N, 0

• N, 1

了maxHeight = 1; //不变

maxHeight = 1; //unchanged

工艺下一个字符： N

推一个节点到堆栈：

• N，0
• N，0

• N，1

• N, 0
• N, 0

• N, 1

了maxHeight = 2; //（加1）

maxHeight = 2; //(incremented by 1)

工艺下一个字符：→

推一个节点到堆栈：

• L，0
• N，0
• N，0

• N，1

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

• N, 1

=了maxHeight 3; //加1

maxHeight = 3; //incremented by 1

最后一个节点是一个叶子，所以流行和增量

last node was a leaf, so pop and increment

堆栈：

• N，1
• N，0

• N，1

• N, 1
• N, 0

• N, 1

=了maxHeight 3; //不变

maxHeight = 3; //unchanged

工艺下一个字符：→

推一个节点到堆栈：

• L，0
• N，1
• N，0

• N，1

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

• N, 1

=了maxHeight 3; //不变

maxHeight = 3; //unchanged

最后一个节点是一个叶子，所以流行和增量：

last node was a leaf, so pop and increment:

• N，2
• N，0
• N，1

顶级节点具有计数2，所以流行和增量：

top node has count 2, so pop and increment:

• N，1
• N，1

工艺下一个节点：→

推一个节点到堆栈：

• L，0
• N，1

• N，1

• L, 0
• N, 1

• N, 1

=了maxHeight 3; //不变

maxHeight = 3; //unchanged

最后一个节点是一个叶子，所以流行和增量：

last node was a leaf, so pop and increment:

• N，2
• N，1

顶级节点具有计数2，所以流行和增量：

top node has count 2, so pop and increment:

• N，2

顶级节点具有计数2，所以流行和增量：

top node has count 2, so pop and increment:

(empty stack), finished

maxHeight = 3; //the maximum height discovered during a preorder of a full binary tree

这篇关于查找树的高度赋予preorder的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！