- A binary tree is a type of tree in which each node has at most two child branches.
- These child branches are labelled left and right.
Internal and External Nodes
- Internal nodes:
- An internal node is a node that has children.
- In the example below there are 4 internal nodes.
- The internal path length is the sum of the levels of all the internal nodes.
- In the example below the internal path length is: 1 + 1 + 2 = 4.
- External nodes:
- An external node is a node that does not have children.
- It is also called a leaf node.
- In the example below there are 4 external nodes.
- The external path length is the sum of hte levels of all the external nodes.
- In the example below the external path length is: 2 + 2 + 3 + 3 = 10.
- The internal nodes are colored red.
- The external nodes are colored blue.
Full Binary Tree
- A full binary tree is a type of binary tree in which each node has exactly 0 or 2 child branches.
- They are also called proper binary trees or plane binary trees.
Extended Binary Tree
- An extended binary tree is a type of full tree
- It is created by extending nodes of an existing tree:
- If the existing node has no children then two child nodes are added
- If the existing node has 1 child then a second child is added
- The existing nodes are drawn as blue circles
- The new, extended nodes are drawn as red rectangles
Complete Binary Tree
- A complete tree is a type of binary tree in which every node as two children apart from the bottom level, which is filled from left to right.
- Complete binary trees are useful because they offer the best ratio between the height and the number of nodes.
Perfect Binary Tree
- A binary tree is perfect if all of the external nodes are on the same level.
Skewed Binary Tree
- A skewed binary tree is a tree which is dominated by either left or right nodes.
# -*- coding: utf-8 -*- class Node: def __init__(self, data): self.data = data def addLeft(self, node): node = node if isinstance(node, Node) else Node(node) self.left = node node.parent = self return self # returns self so it can be chained def addRight(self, node): node = node if isinstance(node, Node) else Node(node) self.right = node node.parent = self return self def __str__(self, path = '', last = True): ret = path + ('' if not path else ('└─ ' if last else '├─ ')) + self.data + '\n' if hasattr(self, 'left'): ret += self.left.__str__(path + (' ' if last else '│ '), False) elif hasattr(self, 'right'): #we use a fake node for spacing ret += Node("").__str__(path + (' ' if last else '│ '), False) if hasattr(self, 'right'): ret += self.right.__str__(path + (' ' if last else '│ '), True) elif hasattr(self, 'left'): ret += Node("").__str__(path + (' ' if last else '│ '), True) return ret
tree = \ Node("Colors") \ .addLeft(Node("Blue") .addRight("Dark Blue")) \ .addRight(Node("Red") .addLeft("Light Red") .addRight("Dark Red")) \ print(tree)
Colors ├─ Blue │ ├─ │ └─ Dark Blue └─ Red ├─ Light Red └─ Dark Red