Can a Node Have Multiple Parents in Trees?

[mohamed el teir]

i know that a node cannot have more than one parent given that these parents have common ancestor (because this is undirected cycle and a tree must have no cycles).
but can a node have more than one parent given that these parents don't have common ancestor (which will produce an unrooted tree i think) ??

 

[newjerseyrunner]

What circumstances would you use such a data structure? Sounds like a relational database.

 

[mohamed el teir]

What circumstances would you use such a data structure? Sounds like a relational database.

i am not planning now to use this but as a concept i want to know is this right or wrong

 

[Dominik Tugend]

[...]
but can a node have more than one parent given that these parents don't have common ancestor (which will produce an unrooted tree i think) ??

That would imply multiple roots and is not allowed (see definition section):
https://en.wikipedia.org/w/index.php?title=Tree_(data_structure)&oldid=712433755#Definition

In a tree a node has at most a single parent, which is also mentioned in the article linked above.

You can have multiple (read a collection of) trees though, but those aren't interconnected then and don't count as a (single) tree (see 5th graphic in definition section).

 

[mohamed el teir]

That would imply multiple roots and is not allowed (see definition section):
https://en.wikipedia.org/w/index.php?title=Tree_(data_structure)&oldid=712433755#Definition

In a tree a node has at most a single parent, which is also mentioned in the article linked above.

You can have multiple (read a collection of) trees though, but those aren't interconnected then and don't count as a (single) tree (see 5th graphic in definition section).

so what does an unrooted tree exactly mean ?

 

[Dominik Tugend]

Ah I thought you were asking about the data structure tree, but it seems you are asking about graph theory actually.

I think the terms "parent" and "child" don't exist for un-rooted trees:

An example for a binary un-rooted tree can be found on this page, there is also a good definition of it:
https://en.wikipedia.org/w/index.php?title=Unrooted_binary_tree&oldid=617279144#Definitions

 

[Filip Larsen]

In graph terminology, any graph without cycles is a tree. As a data structure, the navigability between nodes, like parent and child relations, usually express some kind of hierarchy between nodes which comes "on top" of the tree graph in order to serve some purpose, like for instance expressing a search tree. In principle you could have tree data structures with many or no roots depending on what the relationship means.

 

[newjerseyrunner]

Usually the point of a tree is to know where you came from, which implies a single parent. If you're just wanting to conserve space, you could wrap all of your nodes in a reference counter.

 

[Pepper Mint]

Supposing your current concern is about computational molecular biology, particularly algorithmic approaches available to building phylogenetic trees.

i know that a node cannot have more than one parent given that these parents have common ancestor (because this is undirected cycle and a tree must have no cycles).

Yes, that is partly true about the inadequacy of using phylogenetic trees alone to represent the histories of species in question. As a matter of fact, two daughter branches may have only one parent in a binary tree.

but can a node have more than one parent given that these parents don't have common ancestor (which will produce an unrooted tree i think) ??

There are actually several types of trees used to model species relationships in phylogenetic study. The most commonly mentioned ones are rooted and unrooted trees, either of which can't be used to fully model outcomes of such events of the so-called reticulate evolution as gene transfer, hybridization, recombination, reassortment etc. These are what your concern is exactly about that whether or not a child can have two parents at the same time. We therefore have to opt to choose a better modeling tool called a phylogenetic network instead, which is also a graph being again as either rooted (e.g split, median, quasi-median, etc.) or unrooted (e.g haplotype, reticulograms) one. You can google on these terms to learn more about their applications in practice.

 

[harborsparrow]

I seem to recall that C++ allows multiple inheritance, which may be an example of what you are referring to. For example, a given object O can inherit properties from two different ancestors. It can also be the parent of multiple descendants. For a designer point of view, this turned out to be a prescription for disaster, which is why most OO languages do NOT support multiple inheritance. So we're not talking trees, per se, but once you start doing that, you no longer have a tree, as was pointed out above. You just have a graph. And you can try to avoid cycles in it, but it's not what is called a "tree" any longer in strict comp. sci. terminology.