Python Forum
Binary expression trees
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Binary expression trees
#1
Hi,

I am trying to build a decision tree from the prefix. The prefix is given in a string, I am reading it by identifying operators and operands from it. No issues here.
My trouble is with actually building the tree, but not using a stack.
Here is my code for adding nodes to the tree:

    def add(self, value):        
        if self.root is None:
            self.root = BinaryTreeNode(value)
        else:
            ptr = self.root
        while True:
            if ptr.value in ["+", "-", "*", "/", "%", "//", "**"]:
                if ptr.left is None:
                    ptr.left = BinaryTreeNode(value)
                    break
                else:
                    ptr = ptr.left
            else:
                if ptr.right is None:
                    ptr.right = BinaryTreeNode(value)
                    break
                else:
                    ptr = ptr.right
The problem is it is not moving on the right branch of the tree. Example: "+ * 2 3 - 20 / 15 3"
The code above is actually building 3 as a the right side of the 2 node, instead of both being the left & right of the "*" node.
So smth like this:
Output:
+ * 2 3
instead of:
Output:
+ * 2 3
So the error is that the code doesn't move back up on the branch of the tree.
Any idea how to solve this?

Many thanks!
Cristina
Larz60+ write Oct-21-2020, 11:01 AM:
Please post code within code tags, I added them for you this time.
Reply
#2
Look at your logic as you walk down the tree:

Am I on an operator?
If so, is the left side empty? (If it is, set the value on the left)
If left side is not empty, make left side the new pointer

At the moment, nothing in the "it is an operator" conditional will examine or redirect to the right. That only happens in the non-operator block.

I'm not sure what logic you're using to create the tree, but you probably need another conditional in there to see if you want to add on the right.
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  Using ID3 Estimator for Decision Trees student6306 2 1,338 Jun-15-2023, 04:11 PM
Last Post: student6306

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020