Empty binary trees

[Vinodh]

Started reading about Binary Trees and got the following questions in
mind. Please help.

Definition of a Binary Tree from "Data Structures using C and C++ by
Tanenbaum" goes like this,
"A binary tree is a finite set of elements that is either empty or is
partitioned into three disjoint subsets. The first subset contains a
single element called the 'Root' of the tree. The other two subsets
are themselves binary trees, called the 'Left' and 'Right' subtrees of
the original tree."

My Questions:
1) Why they talk about a binary tree that is totally empty? I mean a
binary tree with Zero elements?

2) A binary tree is partioned into three disjoint subsets. That means
all the elements in a binary tree should be unique? Duplicate elements
are allowed within a subtree? Any significance of this?

Thanks,
Vinodh

 

[Kai-Uwe Bux]

Started reading about Binary Trees and got the following questions in
mind. Please help.

Definition of a Binary Tree from "Data Structures using C and C++ by
Tanenbaum" goes like this,
"A binary tree is a finite set of elements that is either empty or is
partitioned into three disjoint subsets. The first subset contains a
single element called the 'Root' of the tree. The other two subsets
are themselves binary trees, called the 'Left' and 'Right' subtrees of
the original tree."

My Questions:
1) Why they talk about a binary tree that is totally empty? I mean a
binary tree with Zero elements?

It's needed in the recursive definition. If you do not allow subtrees to be
empty, then your trees cannot have leaves and will be infinite.

2) A binary tree is partioned into three disjoint subsets. That means
all the elements in a binary tree should be unique?
Yes.

Duplicate elements are allowed within a subtree?
No.

Any significance of this?

Yes: trees do not have cycles.



BTW: your question is basically unrelated to C++ and would be better suited
for comp.programming.



Best

Kai-Uwe Bux

 

[Juha Nieminen]

No.

That would be incorrect. You are confusing binary trees with binary
search trees.

A binary tree doesn't impose any limitations whatsoever on the
contents of the nodes. It only defines the structure of the tree (each
node can have one parent node and two subtrees).

What you are thinking about is a binary search tree, which has the
additional limitation that all the nodes in the left subtree must be
smaller than the node itself, and the ones on the right subtree larger.

 

[Kai-Uwe Bux]

That would be incorrect. You are confusing binary trees with binary
search trees.

I don't think that I am confusing anything here.

A binary tree doesn't impose any limitations whatsoever on the
contents of the nodes.

We have to distinguish the dublication of labels from the dublication of
nodes. In a tree, subtrees will not share nodes. However, different nodes
might share labels.

The definition that the OP refers to is clearly not talking about labels but
about nodes.

It only defines the structure of the tree (each
node can have one parent node and two subtrees).

And those subtrees do not share nodes.

What you are thinking about is a binary search tree,
which has the
additional limitation that all the nodes in the left subtree must be
smaller than the node itself, and the ones on the right subtree larger.

You are blurring the distinction of nodes and labels. That is not a good
idea when talking about trees. The comparison applies to labels. The
requirement that nodes be distinct is just a consequence of the absence of
cycles in trees.


Best

Kai-Uwe Bux

 

[Vinodh]

I don't think that I am confusing anything here.


We have to distinguish the dublication of labels from the dublication of
nodes. In a tree, subtrees will not share nodes. However, different nodes
might share labels.

The definition that the OP refers to is clearly not talking about labels but
about nodes.


And those subtrees do not share nodes.

Right.I was talking about nodes only. And I was not asking about
"Binary Search Tree" which seems to be a specialization of a Binary
Tree. The statement that subtrees do not share nodes in a binary tree
is in synch with the definition of "the subtrees are disjoint". Thanks
for validating my understanding.

You are blurring the distinction of nodes and labels. That is not a good
idea when talking about trees. The comparison applies to labels. The
requirement that nodes be distinct is just a consequence of the absence of
cycles in trees.

No.

Right.
Recursively if we check I find that, since root and subtrees can not
have anything common, between root, left and right nothing is going to
be common in a binary tree. Hence now I am able to understand every
node value in a binary tree is Unique. Thanks

Thouh I don't know the significance of this Uniqueness.

 

[Vinodh]

Right.I was talking about nodes only. And I was not asking about
"Binary Search Tree" which seems to be a specialization of a Binary
Tree. The statement that subtrees do not share nodes in a binary tree
is in synch with the definition of "the subtrees are disjoint". Thanks
for validating my understanding.



Right.
Recursively if we check I find that, since root and subtrees can not
have anything common, between root, left and right nothing is going to
be common in a binary tree. Hence now I am able to understand every
node value in a binary tree is Unique. Thanks

Thouh I don't know the significance of this Uniqueness.





- Show quoted text -- Hide quoted text -

- Show quoted text -

Okay....Okay....Now I got it. It is that nodes or lables are distinct.
But the data storage I mean the values we store may be anything which
means that we may have redundant data in a tree.Interesting....

 

[Juha Nieminen]

We have to distinguish the dublication of labels from the dublication of
nodes. In a tree, subtrees will not share nodes. However, different nodes
might share labels.

I understood "no duplicate elements" to mean that the same value
cannot be stored in the tree twice. I apologize for the misunderstanding.

 

[James Kanze]

Vinodh wrote:

[...]

No.

I'm not sure I like the wording here. "Duplicate" can (and
usually does, I think) mean a copy, and you can definitely have
elements with identical values (copies of one another) in a
tree. Each element, however, must be "unique", in the sense
that it has a distinct identity from all other elements.

Yes: trees do not have cycles.

There's more too it than that, I think. A tree is a directed
graph, but you can have acyclic directed graphs which aren't
trees. The important significance here is that each element
(except the root) has exactly one parent, no more (and the root
has zero). (In fact, the definition that I've usually heard for
a tree is a directed acyclic graph in which exactly one element
has zero elements pointing into it, and all other elements have
one element pointing into them. Although the recursive
definition proposed in the original posting works as well, and
results in the same thing.)