1.树结构术语
2.二叉树
1. 树结构术语
树的特点：① 每个节点有0个或多个子节点；②没有父节点的称为根节点；③每一个非根节点有且只有一个父节点；④除根节点外，每个子节点可以分为多个不相交的子树。
节点的度：一个节点含有的子树个数
树的度：一棵树中，最大的节点的度
叶节点：度为0的节点
父节点：若一个节点含有子节点，该节点称为该子节点的父节点
子节点：一个节点含有的子树的根节点
兄弟节点：具有相同父节点的节点
节点的层次：根节点定义为第1层，往后类推
树的深度：节点的最大层次
堂兄弟节点：其父节点在同一层次的节点
节点的祖先：从根节点到该节点所经过的所有节点
子孙：以某节点为根节点的子树中任一节点
森林：m(>=0)棵互不相交的树的集合
（1）树的种类
无序树：任意节点的子节点之间没有顺序关系
有序树：任意节点的子节点之间有顺序关系：
二叉树：每个节点最多含2个子节点：
完全二叉树：对于一颗二叉树，假设其深度为d(>1)，除了第d层外，其他各层的节点数目均已达到最大值，且第d层所有节点从左向右连续紧密排列。（满二叉树：所有叶节点都在最底层的完全二叉树）
平衡二叉树：当且仅当任何节点的两棵子树的高度差不大于1的二叉树
排序二叉树：二叉查找树（二分查找？）
霍夫曼树：带权路径的二叉树
B树
（2）树的存储
顺序存储：
链式存储
（3）常见树应用
xml、html；路由协议、mysql数据库索引、文件系统、决策树等等。
2. 二叉树
（1）二叉树的性质
性质1：第i层至多有2(i-1)个节点
性质2：深度为k的二叉树至多有2k -1个节点
性质3：任意一棵二叉树，如果叶节点树为m，度为2的节点总数为n，则m = n + 1
性质4：具有n个节点的完全二叉树的深度必为log2(n+1)，向下取整
性质5：对完全二叉树，若从上至下，从左至右编号，则编号为i的节点，其左孩子的编号必为2i、右孩子编号必为2i+1，其双亲编号必为i/2
（2）二叉树的遍历
广度优先遍历（层次遍历）：从左向右，从上至下先序遍历：先根，后左，再右中序遍历：先左，后根，再右后序遍历：先左，后右，再根
（3）二叉树实现
实现树结构、末尾添加节点、广度优先遍历、先序遍历、中序遍历、后序遍历
#! 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)
