1
$\begingroup$

I run a algorithm to solve a problem that return a set of information relative to a binary tree associated with these problem. For illustrate the results obtained I try to plot the binary tree. I make the plot of the right in image below. But I like to plot the tree of the left.

The question is: How plot the binary tree of right in figure below?

enter image description here

The input data for this is two lists. The first contain the "path" of solution (for the tree in the left/right below: paths = {{0, 0, 0, 0, 0}, {0, 1, 1, 1}}) the second list contain the number of nodes in each level (for the tree in the right below: nodes_leves = {1, 2, 4, 4}).

I tried search for the functions associated with graph, trees, etc. but don't encountered a solution for plot this specific tree.

Thanks in advance


Explanation of "paths":

First, denote the "path" {0, 0, 0, 0} for {a = 0, b = 0, c = 0, d = 0}. For the level 1 we have one possibility. Then the a = 0 is the node root. The partial path in the binary tree so far is {left} (see the picture below). enter image description here

After this we have two possibilities for b. But the solution is b=0. That is, in the path we have chosen the left. So far the path in the binary tree is {left, left} (see the picture below).

enter image description here

Note that in second level is possible to have {left, rigth}, i.e., {a = 0, b = 1}. But for the "path solution" the path chosen is {left, left} = {0, 0} = {a = 0, b = 0}.

For the third level we have the possibilities {left, left, 'left/right'}. But the solution is {left, left, left}, i.e., {a = 0, b = 0, c = 0} or {0, 0, 0}. The picture below illustrate this.

enter image description here

And follow this construction we have the two paths solutions in the binary tree: {0, 0, 0, 0} = {left, left, left, left} and {1, 1, 1, 1} = {right, right, right, right}.

The node root maybe be green. But its not fundamental. The problem is receive from input: any path, for e.g. {0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1}, where "0 is choose node son of left" and "1 is choose node son of right" in a certain level, and the number of nodes in each level, for e.g. {1, 2, 4, 2, 8, 5, 4, 3, 2, 4, 4, 4} and plot the respective binary tree with the "paths" and the nodes deleted.

We are going down in this binary tree. In level 1, we have 1 node. In level n we have $2^n$ nodes (in the worst case).

$\endgroup$
5
  • $\begingroup$ Welcome to Mathematica.SE! I suggest the following: 1) As you receive help, try to give it too, by answering questions in your area of expertise. 2) Take the tour and check the faqs! 3) When you see good questions and answers, vote them up by clicking the gray triangles, because the credibility of the system is based on the reputation gained by users sharing their knowledge. Also, please remember to accept the answer, if any, that solves your problem, by clicking the checkmark sign! $\endgroup$
    – Dunlop
    Sep 13, 2019 at 19:10
  • $\begingroup$ can you explain how paths = {{0, 0, 0, 0, 0}, {0, 1, 1, 1}} is related to the two trees? $\endgroup$
    – kglr
    Sep 13, 2019 at 22:10
  • $\begingroup$ Thanks, @kglr! Your answer below, don't includes the paths in the tree. For e.g. for the path $\{0,0,0,0,0\}$ in each choice in the binary tree, the vertice of left is choosen. '0' indicate left and '1' indicate the rigth (son) in this binary tree. Is it possible include this in the code for the plot? $\endgroup$
    – Student
    Sep 16, 2019 at 11:22
  • $\begingroup$ user78008, still don't understand how {0,0,0,0,0} (a list with 5 elements) relates to the verbal description "in each choice in the binary tree, the vertice of left is choosen" (there are 7 such choices in the left tree). I added new pieces in my answer for highlighting selected edges. $\endgroup$
    – kglr
    Sep 16, 2019 at 15:22
  • $\begingroup$ I edited the question for explain whats means the "path" in the binary tree. The correct is {0, 0, 0, 0}, a list with $\underline{4}$ elements (were a typo). $\endgroup$
    – Student
    Sep 17, 2019 at 2:20

1 Answer 1

1
$\begingroup$

You can use CompleteKaryTree to construct the left tree and process it to remove unwanted nodes to get the right tree:

leftg = CompleteKaryTree[4,2,
  ImageSize -> 300, 
  VertexStyle -> {_ -> Blue,  Alternatives[2,4,8,3,7,15]-> Green}];

rightg = VertexDelete[leftg, Range[10, 13]];

Row[{leftg, rightg}, Spacer[10]]

enter image description here

Highlighting edges:

In each choice in the binary tree, the vertex on left is chosen

HighlightGraph[leftg, First /@ GatherBy[EdgeList[leftg], First]]

enter image description here

In each choice in the binary tree, the vertex on right is chosen

HighlightGraph[leftg, Last /@ GatherBy[EdgeList[leftg], First]]

enter image description here

In the first node the left branch is chosen and in other nodes right branch is selected

HighlightGraph[leftg, {#[[1, 1]], #[[2 ;;, -1]]} & @ GatherBy[EdgeList[leftg], First]]

enter image description here

Alternatively, instead of deleting you can hide unwanted vertices and the edges leading to them using the options VertexShapeFunction and EdgeShapeFunction

SetProperty[leftg, 
 {VertexShapeFunction -> {Alternatives @@ Range[10, 13] -> None}, 
  EdgeShapeFunction -> {Alternatives @@ IncidenceList[leftg, Range[10, 13]] -> None}}]

enter image description here

or using the options VertexStyle and EdgeStyle:

SetProperty[leftg, 
  {VertexStyle -> {Alternatives @@ Range[10, 13] -> Directive[EdgeForm[], White]}, 
  EdgeStyle -> {Alternatives @@ IncidenceList[leftg, Range[10, 13]] -> White}}]

same picture

$\endgroup$
1
  • $\begingroup$ Thanks for help, but this not answer my question. $\endgroup$
    – Student
    Sep 18, 2019 at 14:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.