二叉树

一、二叉树

二叉树是一种特殊的树，其特点如下：

二叉树每个节点最大只能有两个节点。
二叉树的子树也就是节点有左右之分，即左节点和右节点，次序不能乱。
二叉树即使只有一个子树，也有左右之分。

二、满二叉树

一种特殊的二叉树，其所有的分支节点都有两棵树，其所有的叶子节点都在同一层内。

所有的叶子节点都在同一层。
所有的非叶子节点都有两棵树，即节点度都是2.
同样深度的二叉树中，满二叉树的节点最多，2的h次方减1 $2^{h} - 1$

$2^{h} - 1$

若设二叉树的深度为

叶子节点可以出现在最后一层或倒数第二层。
最后一层的叶子节点一定集中在左部连续位置。
完全二叉树严格按层序编号。（可利用数组或列表进行实现，满二叉树同）

四、创建节点

class Node(object):

    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

五、根据列表创建二叉树

class Node(object):

    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right


class BinTreeNode(object):

    def __init__(self):
        self.root = None

    def create(self, li):
        for i in li:
            self.insert(i)

    def insert(self,num):
        if self.root == None:
            self.root = Node(num)
        else:
            p = self.root
            while 1:
                if num < p.data:
                    if p.left:
                        p = p.left  #递归创建
                    else:
                        p.left = Node(num)
                        break
                elif num > p.data:
                    if p.right:
                        p = p.right  # 递归创建
                    else:
                        p.right = Node(num)
                        break


if __name__ == "__main__":
    tree = BinTreeNode()
    li = [5, 1, 3, 8, 2, 9, 4, 6, 7]
    tree.create(li)

六、前序遍历

先访问根节点，再先序遍历左子树，然后再先序遍历右子树。总的来说是根、左、右。

def proNode(root):
    if root:
        print(root.data, end=' ')
        proNode(root.left)
        proNode(root.right)

七，中序遍历

先中序访问左子树，然后访问根，最后中序访问右子树。总的来说是左、根、右。

def proNode(root):
    if root:
        proNode(root.left)
        print(root.data, end=' ')
        proNode(root.right)

八、后续遍历

先后序访问左子树，然后后序访问右子树，最后访问根。总的来说是左、右、根。

def proNode(root):
    if root:
        proNode(root.left)
        proNode(root.right)
        print(root.data, end=' ')

九、宽度优先遍历——层次遍历

利用队列，依次将根，左子树，右子树存入队列，按照队列的先进先出规则来实现层次遍历。

def bfs(root):
    if root ==None:
        return
    queue = []
    queue.append(root)

    while queue:
        curNode = queue.pop(0)
        print(curNode.data, end=' ')
        if curNode.left:
            queue.append(curNode.left)

        if curNode.right:
            queue.append(curNode.right)

十、深度优先

利用栈，先将根入栈，再将根出栈，并将根的右子树，左子树存入栈，按照栈的先进后出规则来实现深度优先遍历。

前序、中序、后续遍历都属于深度优先遍历。

下面代码即是不用递归实现的前序遍历。

def dfs(root):
    if root == None:
        return

    infoqueue = []
    infoqueue.append(root)

    while infoqueue:
        curNode = infoqueue.pop()
        print(curNode.data, end=' ')
        if curNode.right:
            infoqueue.append(curNode.right)
        if curNode.left:
            infoqueue.append(curNode.left)

结束！