joowani / binarytree Goto Github PK
View Code? Open in Web Editor NEWPython Library for Studying Binary Trees
Home Page: http://binarytree.readthedocs.io
License: MIT License
Python Library for Studying Binary Trees
Home Page: http://binarytree.readthedocs.io
License: MIT License
I met a problem when implementing the morris traversal algorithm using this package, the simplified code is as follows:
from binarytree import build
# morris traversal algorithm will cause circular references
# but it will be solved while traveling again
def cycle(root):
condition = True
while root:
if condition:
root.right = root
condition = False
else:
root.right = None
if __name__ == '__main__':
node = build([1,2,3,4,5])
cycle(node)
the while
statement will call the root.__len__()
, which will get size by level traversal. But if there is a circular references like above, level traversal will get into infinite loop without any message about it. Changing the while statement to while root is not None
can solve this, but I think it would be better to raise some message if this happened.
Suggestions:
len(node)
can get correct size of node even though there is circular references.
you can use set
to record the visited node while counting size of node using level traversal. Besides, while node, if node
looks more graceful than while node is not None, if node is not None
.
if the first proposal is rejected, please raise some error message or warning while get into len(node)
infinite loop.
Hi, I'm the package maintainer for binarytree
on the AUR.
With release 6.5.0, I noticed that the graphviz imports changed to fetch ExecutableNotFound
from graphviz.exceptions
, but to my knowledge, ExecutableNotFound
still exists under graphviz
.
Was this a mistake? I tested this against graphviz
0.19.
First of all nice package, thanks for that! I just wanted to visualize a binary tree with Graphviz thats why I adapted this utility function from the treelib package, maybe it fits somewhere in your library. As I wanted to have string values for nodes and that doesn't work with your package I supplied an optional id2name
dictionary, which stores the mapping.
import binarytree as bt
def binarytree_to_dot(root: bt.Node, filename: str, id2name: Optional[Dict[int, str]] = None,
shape: str = 'ellipse', graph: str = 'digraph') -> None:
"""Exports the tree in dot format of the graphviz software.
Left childs are denoted by a full stroke arrow, right childs by a dashed arrow."""
if not isinstance(root, bt.Node):
raise ValueError("Root must be a binarytree.")
if id2name is None:
id2name = {node.value: str(node.value) for node in root}
nodes, connections = [], []
for node in root.levelorder:
nid = node.value
state = '"' + str(nid) + '"' + ' [label="' + str(id2name[nid]) + '", shape=' + shape + ']'
nodes.append(state)
if node.left is not None:
cid = node.left.value
connections.append('"' + str(nid) + '":sw' + ' -> ' + '"' + str(cid) + '"')
if node.right is not None:
cid = node.right.value
connections.append('"' + str(nid) + '":se' + ' -> ' + '"' + str(cid) + '" [style=dashed]')
# write nodes and connections to dot format
with open(filename, 'wt') as f:
f.write(graph + ' tree {\n')
for n in nodes:
f.write('\t' + n + '\n')
f.write('\n')
for c in connections:
f.write('\t' + c + '\n')
f.write('}')
Use it like this
root = bt.tree(height=6)
binarytree_to_dot(root, filename="test_tree.dot")
After installing graphviz, you can plot the tree with the following command:
dot -T png -o test_tree.png test_tree.dot
I'm not sure if the current way of calculating the is_bst
property is correct. I thought for a bst, ALL nodes in left subtree should be less than parent, and ALL nodes in right subtree should be greater than (and possibly equal to if you want to allow duplicate keys) parent.
Seems like the current method only compares immediate left and right nodes to parent, so an example like this tree fails with current method:
__ 2
/ \
1 4
\
3
from binarytree import tree, convert, inspect
nodeList = [2, 1, 4, None, 3]
tree = convert(nodeList)
tree_props = inspect(tree)
assert(tree_props['is_bst'] == False)
Hi,
I'm new to github but I just found your project, which really interests me and should make my work easier.
I've read through the documentation, and I didn't find a way to associate strings to a Node. I actually need it to process the Huffman algorithm, and therefore need to create a tree with each letters of my message and their probability. I've spotted the value of the node could be a float, which fits for the probability, but have you thought about a way to implement strings ?
I could maybe use ASCII to put integers in place of letters in the tree, but that would require me to attach the weight (probability) to such a node and I did not find out if that was possible either.
Could you help me better understanding your library ?
Thank you very much !
The license states that it should be packaged in all distributions of the package, but it is not packaged in the pypi release. I only realized this because I am in the process of packaging bonarytree for conda forge.
Tree:
5
/ \
2 3
/ \
2 4
/ \
3 1
Code:
from binarytree import build
li = [5, 2, 3, None, None, 2, 4, 3, 1]
build(li)
Error:
File "C:\Program Files\Python37\lib\site-packages\binarytree\__init__.py", line 1811, in build
'parent node missing at index {}'.format(parent_index))
FYI:
def build(values):
...
nodes = [None if x is None else Node(x) for x in data]
non_null_nodes = [x for x in nodes if x is not None]
for i in range(1, len(nodes)):
if nodes[i] is not None:
parent_index = (i - 1) // 2
parent = non_null_nodes[parent_index]
...
def levelorder(self):
...
current_level = [self]
res = []
while current_level:
next_level = []
for node in current_level:
if node:
res.append(node.val)
next_level.append(node.left)
next_level.append(node.right)
else:
res.append(None)
current_level = next_level
while res:
if res[-1] is None:
res.pop()
else:
break
return res
Hi, I find this project superb cool. I read through the code in the first time. All code are concise and good. But I am having a hard time trying to understand the algorithm to pretty-print(pprint) the tree.
Can you add more comments to explain how it works? It seems the code is building up the node value and formatting ascii strings level by level. But I am very curious about the idea behind, like what does l_len, l_vale_from, l_anhor works? what l_anchor is marked as ceiling and r_anchor as floor?
def _build_str(node):
"""Helper function used for pretty-printing."""
if node == _null:
return 0, 0, 0, []
line1 = []
line2 = []
val_len = gap_len = len(str(_value_of(node)))
l_len, l_val_from, l_val_to, l_lines = _build_str(_left_of(node))
r_len, r_val_from, r_val_to, r_lines = _build_str(_right_of(node))
if l_len > 0:
l_anchor = -int(-(l_val_from + l_val_to) / 2) + 1 # ceiling
line1.append(' ' * (l_anchor + 1))
line1.append('_' * (l_len - l_anchor))
line2.append(' ' * l_anchor + '/')
line2.append(' ' * (l_len - l_anchor))
val_from = l_len + 1
gap_len += 1
else:
val_from = 0
line1.append(str(_value_of(node)))
line2.append(' ' * val_len)
if r_len > 0:
r_anchor = int((r_val_from + r_val_to) / 2) # floor
line1.append('_' * r_anchor)
line1.append(' ' * (r_len - r_anchor + 1))
line2.append(' ' * r_anchor + '\\')
line2.append(' ' * (r_len - r_anchor))
gap_len += 1
val_to = val_from + val_len - 1
gap = ' ' * gap_len
lines = [''.join(line1), ''.join(line2)]
for i in range(max(len(l_lines), len(r_lines))):
l_line = l_lines[i] if i < len(l_lines) else ' ' * l_len
r_line = r_lines[i] if i < len(r_lines) else ' ' * r_len
lines.append(l_line + gap + r_line)
return len(lines[0]), val_from, val_to, lines
Hi,
I was looking at documentation for building a tree from list. Below is from the documentation,
>>> from binarytree import build
>>>
>>> # Build a tree from list representation
>>> root = build([7, 3, 2, 6, 9, None, 1, 5, 8])
>>> print(root)
#
# __7
# / \
# __3 2
# / \ \
# 6 9 1
# / \
# 5 8
#
Then I tried
>>> root = build([7, 3, 2, 6, 9, None, 1, 5, 8, 1, 2])
>>> print(root)
______7
/ \
__3__ 2
/ \ \
6 9 1
/ \ / \
5 8 1 2
But when I tried to add one more leaf to the node, I get an error.
>>> root = build([7, 3, 2, 6, 9, None, 1, 5, 8, 1, 2, 3])
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "/binarytree/__init__.py", line 1651, in build
.format(parent_index)
binarytree.exceptions.NodeNotFoundError: Parent node missing at index 5
It seems I cannot add the 3 to tree because theres a None node at index 5. I think the 3 should instead be added to the left child node of 1 (index 6)
Hello, i think that a short reference for the properties of binary trees will be useful for the purpose of the project.
Something like :
what_is_full()
Is a tree in which every node in the tree has either 0 or 2 children.
An Example
Hi there,
I did not get the reason why the value of Node class in binarytree must be integer in the new version (3.0.1.), whereas it worked perfectly for floating point value in the old version (1.1.1).
Can you fix that?
Thanks
MC
Documentation is missing explanation if this data structure keeps the data balanced (red-black, AVL) or not.
If it's NOT, better to explicitly say in the very first few lines of the readme.
Here's a brief list of functionality that I think would be really awesome to include in this library. Any feedback would be greatly appreciated. I'll get to these eventually if @joowani likes them and if no one gets to them first!
The function _is_balanced
always returns 1 + height
. What gives?
import binarytree
ttree = binarytree.tree(height=3, is_perfect=True)
print(ttree)
assert ttree.height == binarytree._is_balanced(ttree), \
f'Tree property height: {ttree.height} is not equal to \
_is_balanced function return value: {binarytree._is_balanced(ttree)}'
You can also visit https://repl.it/@ashokb/binarytreeBalanced to run it
Hi! Could we add a requirements.txt file for making it easy for new contributors to contribute?
Hi, and first thanks for this handy package. I'm using it with my students, and even if I really like the print method, I would like to have better outputs as I am using it on notebooks.
I've implemented a regular tree display in svg format. It allows outputs like this:
Are you interested in this feature, it do not change anything except in notebooks, where the traditionnal print method will still work.
For reference here is the doc for _repr_svg_
:
https://ipython.readthedocs.io/en/stable/config/integrating.html?highlight=repr_svg#rich-display
Hello,
A quick question if that is the place to ask, is it possible to access the index of an individual node ?
I can't seem to find an easy way to do that.
Thanks !
hello i am new in github and though i have already installed the package by using "pip install binarytree", I still wonder why I downloaded the zip and ran "pip setup.py install" but went wrong with the error "setuptools-scm was unable to detect version for C:\Users\Desktop\binarytree-6.5.1." while I have installed setuptools-scm package in version of 8.0.4. Thanks a lot!
When importing I get the error:
No module named 'graphviz.exceptions'
I did the pip install with both graphviz and binarytree and I have the last version of both. Python version: 3.7
Hey Joowani :),
I just created a build script of this package for archlinux (PKGBUILD). Maybe you can check if all is ok. If all is good, we can put this build option in README, that would be great for arch users :).
Cheers,
Joaquin
I am a new user of binarytree
and it's saving me some time in an algorithms class, so thank you!
Originally, I was scrolling up and down in the README.md
a bunch, before I noticed the binarytree.readthedocs.io link on the right. The API Specification page was exactly what I was looking for.
Take a look at README
of popular repos:
They all clearly have the docs hosting linked at the top of the README
, which makes it very easy to discover the docs. I think isort
does the best job of this.
I think it would be helpful for binarytree
to do the same. Thank you for your consideration!
while trying to repr tree as image following the example provided on readme, got following error:
AttributeError: 'Digraph' object has no attribute '_repr_svg_'
looks like it's because Digraph._repr_svg_()
is deprecated:
binarytree/binarytree/__init__.py
Line 512 in 397e65f
and is solved by replacing the line with:
return self.graphviz()._repr_image_svg_xml()
(_repr_image_svg_xml()
returns str
)
text:
from binarytree import tree
t = tree()
t
---------------------------------------------------------------------------
AttributeError Traceback (most recent call last)
File ~/.asdf/installs/python/3.10.1/lib/python3.10/site-packages/IPython/core/formatters.py:343, in BaseFormatter.__call__(self, obj)
[341](file:///home/scarf/.asdf/installs/python/3.10.1/lib/python3.10/site-packages/IPython/core/formatters.py?line=340) method = get_real_method(obj, self.print_method)
[342](file:///home/scarf/.asdf/installs/python/3.10.1/lib/python3.10/site-packages/IPython/core/formatters.py?line=341) if method is not None:
--> [343](file:///home/scarf/.asdf/installs/python/3.10.1/lib/python3.10/site-packages/IPython/core/formatters.py?line=342) return method()
[344](file:///home/scarf/.asdf/installs/python/3.10.1/lib/python3.10/site-packages/IPython/core/formatters.py?line=343) return None
[345](file:///home/scarf/.asdf/installs/python/3.10.1/lib/python3.10/site-packages/IPython/core/formatters.py?line=344) else:
File ~/.asdf/installs/python/3.10.1/lib/python3.10/site-packages/binarytree/__init__.py:512, in Node._repr_svg_(self)
[506](file:///home/scarf/.asdf/installs/python/3.10.1/lib/python3.10/site-packages/binarytree/__init__.py?line=505) """Display the binary tree using Graphviz (used for `Jupyter notebooks`_).
[507](file:///home/scarf/.asdf/installs/python/3.10.1/lib/python3.10/site-packages/binarytree/__init__.py?line=506)
[508](file:///home/scarf/.asdf/installs/python/3.10.1/lib/python3.10/site-packages/binarytree/__init__.py?line=507) .. _Jupyter notebooks: https://jupyter.org
[509](file:///home/scarf/.asdf/installs/python/3.10.1/lib/python3.10/site-packages/binarytree/__init__.py?line=508) """
[510](file:///home/scarf/.asdf/installs/python/3.10.1/lib/python3.10/site-packages/binarytree/__init__.py?line=509) try:
[511](file:///home/scarf/.asdf/installs/python/3.10.1/lib/python3.10/site-packages/binarytree/__init__.py?line=510) # noinspection PyProtectedMember
--> [512](file:///home/scarf/.asdf/installs/python/3.10.1/lib/python3.10/site-packages/binarytree/__init__.py?line=511) return str(self.graphviz()._repr_svg_())
[514](file:///home/scarf/.asdf/installs/python/3.10.1/lib/python3.10/site-packages/binarytree/__init__.py?line=513) except (SubprocessError, ExecutableNotFound, FileNotFoundError):
[515](file:///home/scarf/.asdf/installs/python/3.10.1/lib/python3.10/site-packages/binarytree/__init__.py?line=514) return self.svg()
AttributeError: 'Digraph' object has no attribute '_repr_svg_'
Node(3)
ubuntu 21.10
python 3.10.1
ipython 8.1.1
binarytree 6.5.1
graphviz 0.20
It would be nice to have a way to set the seed (or random state) for creating random trees. For instance, something like bst(4, random_state=42)
would return always the same random tree.
Thanks!
[1, 2, 3, None, None, 5, 6, 7, 8, 9, None, None, None, 10, None, 11]
should produce:
[2, 5, None, 3, None, 1, 4]
should produce:
but both fail.
if parent is None:
> raise NodeNotFoundError(
"parent node missing at index {}".format(parent_index)
)
E binarytree.exceptions.NodeNotFoundError: parent node missing at index 3
/Users/me/.pyenv/versions/3.9.2/lib/python3.9/site-packages/binarytree/__init__.py:2008: NodeNotFoundError
Whereas the following code builds the trees as expected:
def from_list(nums: Sequence[Optional[int]]) -> Optional[TreeNode]:
"""Build a binary tree in level order.
The idea is to take two numbers and associate with the first non-null parent that hasn't been looked at.
Keyword arguments:
nums -- node values
"""
queue: collections.deque[TreeNode] = collections.deque()
root = None
if nums:
root = TreeNode(nums[0])
queue.append(root)
i = 1
while i < len(nums):
node = queue.popleft()
if nums[i] is not None:
node.left = TreeNode(nums[i])
queue.append(node.left)
i += 1
if i < len(nums) and nums[i] is not None:
node.right = TreeNode(nums[i])
queue.append(node.right)
i += 1
queue.clear()
return root
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.