Insert children of a specified node in a binary tree and retrieve all leaves of a binary tree.

asked 2017-05-04 21:22:32 +0200

KittyL gravatar image

I am trying to use a binary tree to store data. When different cases happens at some step, I will need to create two children from the current node.

I also need to collect all information on the leaves (nodes with no children). I use the following definition of binary trees:

from sage.misc.binary_tree import BinaryTree
T = BinaryTree();

I can insert node the following way:

t.insert(0,[1,2,4]);
t.insert(1,[4,5]);
t.insert(2,[5,0]);

But I couldn't find a way to visualize the tree. Also I don't know how to add two children of one certain node. For example, if 0 is the root (it seems so), 1 is its left child and 2 is its right child (which I am not sure), how do I make sure I add two children for the node 2?

I also looked at this page: (http://doc.sagemath.org/html/en/refer...). I couldn't see how to insert a node with values in it, or how to retrieve information of leaves.

Do I have to define my own tree structure?

Thank you for your help!

edit retag flag offensive close merge delete

Comments

The first line

from sage.misc.binary_tree import BinaryTree

points to an other BinaryTree then the above linked one. (Which has no method insert.) After some good minutes with the cython (!?) code for it on my machine at

/usr/share/sage/source/sage/misc/binary_tree.pyx

which is mirrored in html at

http://doc.sagemath.org/html/en/reference/data_structures/sage/misc/binary_tree.html

i could not realize how such a BinaryTree "tree" differs from and a python dictionary where we remove most of the functionality, except the basic one. (And make the constructors very tricky and with unwanted side effects. If in a dictionary the last value declaration for a key wins, for a "BinaryTree"... The nodes seem to be the keys. But i am still missing the father-child functionality and ...)

dan_fulea gravatar imagedan_fulea ( 2017-05-05 22:28:32 +0200 )edit

After further searching for lines of code using the same import, i had to resign while founding that the "tree" should be not a kind of a dictionary, but a kind of a spartan map:

https://groups.google.com/forum/#!msg/sage-support...

dan_fulea gravatar imagedan_fulea ( 2017-05-05 22:32:42 +0200 )edit

Yes, you are right. I didn't link the one with "insert" since it does not provide me the functionality I was looking for. So I found another one, which does not have "insert", and still cannot do anything since it does not provide a value for each node. Now I decide I should just make a "recursive list" to achieve my goal. It seems Sage does not have a good Binary Tree implementation, at least for my purpose. Thank you for your time!

KittyL gravatar imageKittyL ( 2017-05-06 12:09:57 +0200 )edit