What is the definition of the height of a tree?

Asked 2 years ago, Updated 2 years ago, 98 views

I am currently studying binary tree through a book called Data Structure written easily in C language.

At first, I didn't think deeply about the simple concept

Gradually, the concepts started to get confused, so I googled about the height of the tree.

However, the definition of the binary tree concept obtained through the book and googling is different, so I ask you a question.

The book says: (I brought the same picture as the book)

The level in the tree is numbered for each layer of the tree, and by definition, the level of the root becomes 1 and increases by 1 as it goes down one step by step. The height of the tree refers to the maximum level that the tree has. The height of the tree above is 3.

The following are the definitions obtained through googling.

The height of a node is the length of the longest downward path to a leaf from that node. The height of the root is the height of the tree. The depth of a node is the length of the path to its root (i.e., its root path). This is commonly needed in the manipulation of the various self-balancing trees, AVL Trees in particular. The root node has depth zero, leaf nodes have height zero, and a tree with only a single node (hence both a root and leaf) has depth and height zero. Conventionally, an empty tree (tree with no nodes, if such are allowed) has height −1.

https://en.wikipedia.org/wiki/Tree_(data_structure)

Height of node – The height of a node is the number of edges on the longest downward path between that node and a leaf.

http://typeocaml.com/2014/11/26/height-depth-and-level-of-a-tree/

Of course, while studying, the posts posted by overseas users

I see it as more accurate, but

It's very confusing because I've never seen a book with a different definition.

Which definition do you think is correct?

(At first, I was looking back on whether it was up to each person's definition, but eventually I posted a question like this.)

binary-tree data-structure c

2022-09-20 16:20

1 Answers

Justice is not right or wrong. This is what this book defines.

So, you have to understand that one of the conclusions is not right or wrong, but the book defines it like that and proceeds with the story.

A typical tree definition is that the root node is level 0, and the plot in the question shows that the root node is level 1.

And the height of a typical tree is also, I think, represented by the number of edges from the root node to the farthest node, but it's not common to define it like the picture in the question, but it's sometimes seen.

When I studied trees before, why do I get the tree level different from book to book?I've searched for it.

https://stackoverflow.com/questions/59151282/what-is-level-of-root-node-in-a-tree


2022-09-20 16:20

If you have any answers or tips


© 2024 OneMinuteCode. All rights reserved.