Last active
December 4, 2023 21:20
-
-
Save fsoppelsa/025ae6e7dd1de7c4ffc45ca91d4724f9 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| from anytree import Node, RenderTree | |
| from anytree.exporter import UniqueDotExporter | |
| def Inorder(root): | |
| """ | |
| Perform an inorder traversal of a tree and print the nodes values | |
| Ignores the ~ (not) symbol | |
| Args: | |
| root (TreeNode): The root node of the tree. | |
| Returns: | |
| None | |
| """ | |
| if root.is_leaf: | |
| # If the current node is a leaf node, print its name | |
| print(root.name, end="") | |
| if root.children: | |
| # If the current node has children, recursively traverse them | |
| left = root.children[0] | |
| right = root.children[1] | |
| print("(", end="") | |
| Inorder(left) | |
| print(root.name, end="") | |
| Inorder(right) | |
| print(")", end="") | |
| def Inorder1(root): | |
| """ | |
| Inorder, polish notation(?) | |
| Args: | |
| root (TreeNode): The root node of the tree. | |
| Returns: | |
| None | |
| """ | |
| if root is None: | |
| return | |
| if (root.children): | |
| left = root.children[0] | |
| right = root.children[1] | |
| print("(", end="") | |
| Inorder1(left) | |
| Inorder1(right) | |
| print(")", end="") | |
| print(root.name, end="") | |
| def Inorder2(root): | |
| """ | |
| Regular inorder traversal of a tree. | |
| Args: | |
| root (TreeNode): The root node of the tree. | |
| Returns: | |
| None | |
| """ | |
| if root.is_leaf: | |
| print(root.name, end="") | |
| if root.name == "~" and root.children: | |
| child = root.children[0] | |
| print("~", end="") | |
| Inorder2(child) | |
| elif (root.children): | |
| left = root.children[0] | |
| right = root.children[1] | |
| print("(", end="") | |
| Inorder2(left) | |
| print(root.name, end="") | |
| Inorder2(right) | |
| print(")", end="") | |
| # Tree without not | |
| sroot = Node("<->") | |
| sl0 = Node("->", parent=sroot) | |
| sr0 = Node("->", parent=sroot) | |
| sl0l = Node("p", parent=sl0) | |
| sl0r = Node("q", parent=sl0) | |
| sr0le = Node("~p", parent=sr0) | |
| sr0re = Node("~q", parent=sr0) | |
| Inorder(sroot) | |
| print() | |
| Inorder1(sroot) | |
| print() | |
| # Tree with not | |
| # ((p->q)<->(~p)->(~q)) | |
| root = Node("<->") | |
| l0 = Node("->", parent=root) | |
| r0 = Node("->", parent=root) | |
| l0l = Node("p", parent=l0) | |
| l0r = Node("q", parent=l0) | |
| r0l = Node("~", parent=r0) | |
| r0le = Node("p", parent=r0l) | |
| r0r = Node("~", parent=r0) | |
| r0re = Node("q", parent=r0r) | |
| UniqueDotExporter(root).to_picture("tree.png") | |
| Inorder2(root) | |
| print() | |
| # Another tree with not from book, page 9 | |
| # p->(q<->~(p->~q)) | |
| zroot = Node("->") | |
| zl = Node("p", parent=zroot) | |
| zr = Node("<->", parent=zroot) | |
| zrl = Node("q", parent=zr) | |
| zrr = Node("~", parent=zr) | |
| zrrb = Node("->", parent=zrr) | |
| zrrl = Node("p", parent=zrrb) | |
| zrrr = Node("~", parent=zrrb) | |
| zrrrb = Node("q", parent=zrrr) | |
| UniqueDotExporter(zroot).to_picture("tree1.png") | |
| Inorder2(zroot) | |
| print() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment