Welcome, guest | Sign In | My Account | Store | Cart

A simple example demonstrating the construction of binary trees.

Python, 120 lines
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
# A binary ordered tree example

class CNode:
    left , right, data = None, None, 0
    
    def __init__(self, data):
        # initializes the data members
        self.left = None
        self.right = None
        self.data = data

class CBOrdTree:
    def __init__(self):
        # initializes the root member
        self.root = None
    
    def addNode(self, data):
        # creates a new node and returns it
        return CNode(data)

    def insert(self, root, data):
        # inserts a new data
        if root == None:
            # it there isn't any data
            # adds it and returns
            return self.addNode(data)
        else:
            # enters into the tree
            if data <= root.data:
                # if the data is less than the stored one
                # goes into the left-sub-tree
                root.left = self.insert(root.left, data)
            else:
                # processes the right-sub-tree
                root.right = self.insert(root.right, data)
            return root
        
    def lookup(self, root, target):
        # looks for a value into the tree
        if root == None:
            return 0
        else:
            # if it has found it...
            if target == root.data:
                return 1
            else:
                if target < root.data:
                    # left side
                    return self.lookup(root.left, target)
                else:
                    # right side
                    return self.lookup(root.right, target)
        
    def minValue(self, root):
        # goes down into the left
        # arm and returns the last value
        while(root.left != None):
            root = root.left
        return root.data

    def maxDepth(self, root):
        if root == None:
            return 0
        else:
            # computes the two depths
            ldepth = self.maxDepth(root.left)
            rdepth = self.maxDepth(root.right)
            # returns the appropriate depth
            return max(ldepth, rdepth) + 1
            
    def size(self, root):
        if root == None:
            return 0
        else:
            return self.size(root.left) + 1 + self.size(root.right)

    def printTree(self, root):
        # prints the tree path
        if root == None:
            pass
        else:
            self.printTree(root.left)
            print root.data,
            self.printTree(root.right)

    def printRevTree(self, root):
        # prints the tree path in reverse
        # order
        if root == None:
            pass
        else:
            self.printRevTree(root.right)
            print root.data,
            self.printRevTree(root.left)

if __name__ == "__main__":
    # create the binary tree
    BTree = CBOrdTree()
    # add the root node
    root = BTree.addNode(0)
    # ask the user to insert values
    for i in range(0, 5):
        data = int(raw_input("insert the node value nr %d: " % i))
        # insert values
        BTree.insert(root, data)
    print
    
    BTree.printTree(root)
    print
    BTree.printRevTree(root)
    print
    data = int(raw_input("insert a value to find: "))
    if BTree.lookup(root, data):
        print "found"
    else:
        print "not found"
        
    print BTree.minValue(root)
    print BTree.maxDepth(root)
    print BTree.size(root)

It's a toy example written years ago to implement a binary tree in Python. Useful for newbies or for a base for something else

4 comments

Rodrigo Senra 19 years, 8 months ago  # | flag

Small suggestion. Nice example. IMHO you should just change the B-Tree comment to binary tree, although this code can hold multiple info per node, it does not implement a B-Tree structure neither has its properties (like being balanced, having a maximum number of buckets per node and short in height).

Foo Bear (author) 19 years, 8 months ago  # | flag

Fixed. thanks :)

Vicente Soler 14 years, 3 months ago  # | flag

I can see, by running the example, that zero (0) is always a node. Can we get rid of it? How could it be done?

Why cannt feed letters (or texts) into the binary tree?

Thank you

Grant Jenks 9 years, 6 months ago  # | flag

If you're looking for an API similar to that provided by a binary search tree, check out the sortedcontainers module. It implements sorted list, sorted dict, and sorted set data types in pure-Python and is fast-as-C implementations (even faster!). Learn more about sortedcontainers, available on PyPI and github.

Created by Foo Bear on Tue, 13 Jul 2004 (PSF)
Python recipes (4591)
Foo Bear's recipes (3)

Required Modules

  • (none specified)

Other Information and Tasks