树的概念
树（英语：tree）是一种抽象数据类型（ADT）或是实作这种抽象数据类型的数据结构， 用来模拟具有树状结构性质的数据集合。它是由 n（n>=1）个有限节点组成一个具有层次关 系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
(1) 每个节点有零个或多个子节点；
(2) 没有父节点的节点称为根节点；
(3) 每一个非根节点有且只有一个父节点；
(4) 除了根节点外，每个子节点可以分为多个不相交的子树；
树的术语
(1) 节点的度：一个节点含有的子树的个数称为该节点的度；
(2) 树的度：一棵树中，最大的节点的度称为树的度；
(3) 叶节点或终端节点：度为零的节点；
(4) 父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
(5) 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
(6) 兄弟节点：具有相同父节点的节点互称为兄弟节点；
(7) 节点的层次：从根开始定义起，根为第 1 层，根的子节点为第 2 层，以此类推；
(8) 树的高度或深度：树中节点的最大层次；
(9) 堂兄弟节点：父节点在同一层的节点互为堂兄弟；
(10)节点的祖先：从根到该节点所经分支上的所有节点；
(11)子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
(12)森林：由 m（m>=0）棵互不相交的树的集合称为森林；
二叉树的基本概念
二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree） 和“右子树”（right
二叉树的性质
性质 1: 在二叉树的第 i 层上至多有 2^(i-1)个节点（i>0）
性质 2: 深度为 k 的二叉树至多有 2^k - 1 个节点（k>0）
性质 3: 对于任意一棵二叉树，如果其叶节点数为 N0，而度数为 2 的结点总数为 N2， 则 N0=N2+1;
性质 4:具有 n 个节点的完全二叉树的深度必为 log2(n+1)
性质 5:对完全二叉树，若从上至下、从左至右编号，则编号为 i 的结点，其左孩子编 号必为 2i，其右孩子编号必为 2i＋1；其双亲的编号必为 i/2（i＝1 时为根,除外）
代码
1.n个二叉树的节点
'''n个二叉树的节点'''
def count(n):
# root : 1
# left : k 0 <= k <= n-1
# right: n-1-k
s = count.cache.get(n,0)
if s:
return s
for k in range(n):
print('ok')
s += count(k) * count(n - 1 - k)
count.cache[n] = s
return s
count.cache = {0: 1}
print(count(5))
2.创建一个二叉树
'''构建一个二叉树'''
class TreeNode(object):
def __init__(self, data, left = None, right = None): # data为数据 left为左分支，不传参数默认为None right为右分支，不传参数默认为None
self.data = data
self.left = left
self.right = right
#两种创建一个简单的二叉树的方式 假设二叉树为ABC
#第一种
B = TreeNode('B')
C = TreeNode('C')
A = TreeNode('A')
root = A
#第二种
A.left = B
A.right = C
#创建一个复杂的二叉树
A,B,C,D,E,F,G,H,I = [TreeNode(x) for x in 'ABCDEFGHI']
A.left = B
A.right = C
B.right = D
C.left = E
C.right = F
E.left = G
F.left = H
F.right = I
print(C.left.data)
3.遍历二叉树（递归版）
先序遍历，根左右
中序遍历，左根右
后序遍历，左右根
'''
先序遍历，根左右
中序遍历，左根右
后序遍历，左右根
'''
import sys
sys.setrecursionlimit(100000) #例如这里设置为十万
class TreeNode(object):
def __init__(self,data, left = None, right = None): # data为数据 left为左分支，不传参数默认为None right为右分支，不传参数默认为None
self.data = data
self.left = left
self.right = right
def __repr__(self):
return str(self)
#创建一个复杂的二叉树
def creattreenode():
A,B,C,D,E,F,G,H,I = [TreeNode(x) for x in 'ABCDEFGHI']
A.left = B
A.right = C
B.right = D
C.left = E
C.right = F
E.left = G
F.left = H
F.right = I
return A #返回根节点
#递归版遍历二叉树(node)为访问二叉树的根节点
#先序遍历
def preorder(node):
if node is None:
return
print(node.data)
preorder(node.left)
preorder(node.right)
#中序遍历
def inorder(node):
if node is None:
return
preorder(node.left)
print(node.data)
preorder(node.right)
#后续遍历
def postorder(node):
if node is None:
return
preorder(node.left)
preorder(node.right)
print(node.data)
#迭代版本先序遍历（回溯法）
def preorderiter(node):
s = []
while True:
while node:
print(node)
s.append(node)
node = node.left
if not s:
break
node = s.pop().right
#层序遍历
from collections import deque
def levelorder(node):
q = deque([node])
while q:
node = q.popleft()
print(node)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
pn = creattreenode()
# preorder(pn)
levelorder(pn)4.二叉树的深度
#二叉树的深度(递归的方式)
def depth(node):
if node is None:
return 0
dl = depth(node.left)
dr = depth(node.right)
result = max(dl, dr) + 1
return result
# 二叉树的深度（非递归,层序遍历）
from collections import deque
def depth2(node):
q = deque([(node, 1)])
while q :
node, d = q.popleft()
if node.left:
q.append((node.left, d + 1))
if node.right:
q.append((node.right, d + 1))
return d5.拷贝二叉树
def copytree(node):
if node is None:
return None
lt = copytree(node.left)
rt = copytree(node.right)
root = TreeNode(node.data, lt , rt)
return root6.二叉树的操作（搜索，插入，删除）
class searchtree():
def __init__(self):
self.root = None
def search(self,k):
node, _ = self._search(k)
return node
def _search(self,k):
parent = None
node = self.root
while node and node.data != k:
parent = node
if k < node.data:
node = node.left
else:
node = node.right
return node, parent
def insert(self,k):
node, parent = self._search(k)
if node:
return
node = TreeNode(k)
if parent is None:
self.root = node
elif k< parent.data:
parent.left = node
else:
parent.right = node
def delete(self,k):
pass