Tree

Definition

at most two children node

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

• 工业界的应用
  • Social networks analysis
  • Information indexing
  • Information compression

基本概念

• Balanced Binary Tree: is commonly defined as a binary tree in which the depth of the left and right subtrees of every node differ by 1 or less
• Complete Binary Tree: is a banary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
  • 除了最后一行，其他行完整
  • 最后一样as far as left as possible
• Binary Search Tree: for every sigle node in the tree, the values in its left subtree are all smaller than its value, and the values in its right subtree are all larger than its value.