概述

在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^{{i-1}个结点；深度为k的二叉树至多有2}k-1个结点；对任何一棵二叉树T，如果其终端结点数为n_0，度为2的结点数为n_2，则n_0=n_2+1。

含义

一棵深度为k，且有2^k-1个节点称之为满二叉树；深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应时，称之为完全二叉树。

二叉树分类：

1、满二叉树

2、完全二叉树

3、平衡二叉树

二叉排序树

二叉排序树（Binary Sort Tree）BST又称二叉查找树（Binary Search Tree）BST

二叉排序树有以下性质：

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

（4）没有键值相等的节点。

二叉树的实现原理

#定义二叉树的节点
 2 class Node(object):
 3     def __init__(self,elem):
 4         """
 5         param: self.elem 是节点的数据域
 6                 self.lchild 是节点的左孩子
 7                 self.rchild 是节点的右孩子
 8         """
 9         self.elem = elem
10         self.lchild = None
11         self.rchild = None
12 
13 class Tree(object):
14     def __init__(self):
15         self.root = None
16     #添加节点
17     def add(self,elem):
18         """
19         param: elem 是传进来的数据，我们要实例化一个节点接收它，
20                 queue: 创建一个队列来接收和弹出节点       
21         """
22         #创建节点
23         node = Node(elem)    
24         if self.root == None:
25             """如果根节点是None,则表示一颗空树，直接把该节点赋给root节点"""
26             self.root = node
27             return
28         queue = []
29         queue.append(self.root)
30         while queue:
31             """队列的弹出要加0，与栈相仿"""
32             curNode = queue.pop(0)
33             if curNode.lchild == None:
34                 curNode.lchild = node
35                 return
36             else:
37                 queue.append(curNode.lchild)
38             if curNode.rchild == None:
39                 curNode.rchild = node
40                 return
41             else: 
42                 queue.append(curNode.rchild)
43 
44     #广度优先遍历
45     def travel(self):
46         queue = []
47         #判断根节点是否存在
48         if self.root is None:
49             return
50         else:
51             queue.append(self.root)
52         while queue:
53             curNode = queue.pop(0)
54             print(curNode.elem,end='\t')
55             if curNode.lchild is not None:
56                 queue.append(curNode.lchild)
57             if curNode.rchild is not None:
58                 queue.append(curNode.rchild)
59             
60 if __name__ == '__main__':
61     tree = Tree()
62     tree.add('A')
63     tree.add('B')
64     tree.add('C')
65     tree.add('D')
66     tree.add('E')
67     print('广度优先遍历')
68     tree.travel()