What is the definition for the height of a tree?_问答_开发者

I can't seem to find a definitive answer for this, I'm trying to do some elementary proofs on heaps but here's wha开发者_C百科t's throwing me off a little bit:

Is an empty tree valid? If so, what is its height?

I would think this would be 0.

What is the height of a tree with a single node?

I would think this would be 1 but I have seen definitions where it is 0 (and if this is the case then I don't know how to account for an empty tree).

Height of a tree is the length of the path from root of that tree to its farthest node (i.e. leaf node farthest from the root).

A tree with only root node has height 0 and a tree with zero nodes would be considered as empty. An empty tree has height of -1. Please check this.

I hope this helps.

I think you should take a look at the Dictionary of Algorithms and Data Structures at the NIST website. There definition for height says a single node is height 0.

The definition of a valid tree does include an empty structure. The site doesn't mention the height of such a tree, but based on the definition of the height, it should also be 0.

I have seen it used in both ways (counting a single node as 0 or 1), but the majority of sources would define a root-only tree as a tree of height 0, and would not consider a 0-node tree valid.

If your tree is a recursively defined data structure which may be either empty or a node with a left and right subtree (for example search trees, or your heap), then the natural definition is to assign 0 to the empty tree and 1 + the height of the highest subtree to a nonempty tree.

If your tree is a graph then the natural definition is the longest path from the root to a leaf, so a root-only tree has depth 0. You normally wouldn't even consider empty trees in this case.

The height of a tree is the length of the longest path to a terminal node in either of its children.

Wikipedia says the height of an empty tree is -1. I disagree. An empty tree is literally just a tree containing one terminal node (a null or special value which represents an empty tree). Since the node has no children, the length of its longest path must be the empty sum = 0, not -1.

Likewise, a non-empty tree has two children, so by definition there is at least a path >= 1 to a terminal node.

We might define our tree as follows:

type 'a tree =
    | Node of 'a tree * 'a * 'a tree
    | Nil

let rec height = function
    | Node(left, x, right) -> 1 + max (height left) (height right)
    | Nil -> 0

According to Wikipedia, the height of a (sub-)tree with one single node is 0. The height of a tree with no nodes would be -1. But I think it's up to you, how you define the height and your proofs should work with either definition.

The definition of the height of a rooted tree is the length of the longest path from the root to a leaf, expressed in the number of edges. This definition does not cover the case of an empty tree, as there is no path at all.

However, for practical reasons, it is convenient to define the height of an empty tree as −1. Here are some of those reasons:

For non-empty trees we have this rule: the height of the tree is equal to the number of levels in that tree, minus 1. If we extrapolate this rule to an empty tree, then we have 0 levels, and thus a height of −1.
A tree with height ℎ has at least ℎ+1 nodes. If the tree is binary, then it has at most 2^ℎ+1−1 nodes. If we substitute −1 for ℎ we get 0 for both expressions, and indeed an empty tree has zero nodes.
The height of a tree is one more than the maximum among the heights of the root's subtrees. If the root happens to have no children, we could say it only has "empty" subtrees. And if we consider the height of those empty subtrees to be −1, then we come to the (correct) conclusion that this tree's height is 0.

It would be impractical to define the height of an empty tree as 0, as you would need to define exceptions to the points raised above.

actully a perfect defn for height of tree is d level of leaf of d longest path from root plus 1..accordin 2 this defn f a tree s empty,it wont b havin any level n v cant consider it had zero,coz level of a root s zero ..so empty tree level is -1,than accordin 2 defn its -1+1=0..so ZERO s d height of empty tree...bt n many book they hav given -1 bt no explanation s given