（3）常見樹應(yīng)用
??xml默垄、html；路由協(xié)議甚纲、mysql數(shù)據(jù)庫索引口锭、文件系統(tǒng)、決策樹等等介杆。

2. 二叉樹

（1）二叉樹的性質(zhì)
性質(zhì)1：第i層至多有2^(i-1)個(gè)節(jié)點(diǎn)
性質(zhì)2：深度為k的二叉樹至多有2^k -1個(gè)節(jié)點(diǎn)
性質(zhì)3：任意一棵二叉樹鹃操，如果葉節(jié)點(diǎn)樹為m，度為2的節(jié)點(diǎn)總數(shù)為n春哨，則m = n + 1
性質(zhì)4：具有n個(gè)節(jié)點(diǎn)的完全二叉樹的深度必為log2(n+1)荆隘，向下取整
性質(zhì)5：對完全二叉樹，若從上至下赴背，從左至右編號椰拒，則編號為i的節(jié)點(diǎn)晶渠，其左孩子的編號必為2i、右孩子編號必為2i+1燃观，其雙親編號必為i/2
（2）二叉樹的遍歷

（3）二叉樹實(shí)現(xiàn)
實(shí)現(xiàn)樹結(jié)構(gòu)、末尾添加節(jié)點(diǎn)缚陷、廣度優(yōu)先遍歷适篙、先序遍歷、中序遍歷箫爷、后序遍歷

#! usr/bin/env python
# coding:utf-8
#=====================================================
# Copyright (C) 2020 * Ltd. All rights reserved.
#
# Author      : Chen_Sheng19
# Editor      : VIM
# Create time : 2020-05-12
# File name   : 
# Description : 
#
#=====================================================
class Node(object):
    def __init__(self,item):
        self.item = item
        self.lchild = None
        self.rchild = None

class Binary_tree(object):
    def __init__(self):
        self.root = None
        self.travel_result = []

    def add(self,item):
        node = Node(item)
        if self.root is None:
            self.root = node
            return

        queue = []
        queue.append(self.root)
        while queue:
            cur_node = queue.pop(0)
            if cur_node.lchild is None:
                cur_node.lchild = node
                return
            else:
                queue.append(cur_node.lchild)

            if cur_node.rchild is None:
                cur_node.rchild = node
                return
            else:
                queue.append(cur_node.rchild)

    def breadth_travel(self):
        if self.root is None:
            return None
        else:
            his = []
            result = []
            
            his.append(self.root)
            result.append(self.root.item)
            while his:
                cur = his.pop(0)
                if cur.lchild is None:
                    return result
                else:
                    his.append(cur.lchild)
                    result.append(cur.lchild.item)
                if cur.rchild is None:
                    return result
                else:
                    his.append(cur.rchild)
                    result.append(cur.rchild.item)

    def pre_order_travel_op(self,node):
        if node is None:
            return
        self.travel_result.append(node.item)

        self.pre_order_travel_op(node.lchild)
        self.pre_order_travel_op(node.rchild)


    def pre_order_travel(self,node):
        self.pre_order_travel_op(node)
        print(self.travel_result)
        self.travel_result = []

    def mid_order_travel_op(self,node):
        if node is None:
            return

        self.mid_order_travel_op(node.lchild)
        self.travel_result.append(node.item)
        self.mid_order_travel_op(node.rchild)

    def mid_order_travel(self,node):
        self.mid_order_travel_op(node)
        print(self.travel_result)
        self.travel_result = []
    
    def post_order_travel_op(self,node):
        if node is None:
            return
        self.post_order_travel_op(node.lchild)
        self.post_order_travel_op(node.rchild)
        self.travel_result.append(node.item)
    def post_order_travel(self,node):
        self.post_order_travel_op(node)
        print(self.travel_result)
        self.travel_result = []

if __name__ == "__main__":
    tree = Binary_tree()
    tree.add(0)
    tree.add(1)
    tree.add(2)
    tree.add(3)
    tree.add(4)
    tree.add(5)
    tree.add(6)
    tree.add(7)
    tree.add(8)
    tree.add(9)
    print(tree.breadth_travel())
    tree.pre_order_travel(tree.root)
    tree.mid_order_travel(tree.root)
    tree.post_order_travel(tree.root)