1、树的特性
1）一棵树中的任意两个结点有且仅有唯一的一条路径连通；
2）一棵树如果有n个结点，则它一定有n−1条边；
3）在一棵树中加一条边将会构成一个回路。
2、二叉树
1）二叉树是一种特殊的树，二叉树的特点是每个结点最多有两个儿子。
2）二叉树使用范围最广，一颗多叉树也可以转化为二叉树。
3、满二叉树
1）二叉树中每个内部节点都有两个儿子，满二叉树所有的叶节点都有相同的深度。
2）满二叉树是一棵深度为h且有2h−1个结点的二叉树。
4、完全二叉树
1）若设二叉树的高度为h，除了第h层外，其他层的结点数都达到最大个数，第h层从右向左连续 缺若干个结点，则为完全二叉树。
5、树的特点
- 如果一棵完全二叉树的父节点编号为K,则其左儿子的编号是2K,右儿子的结点编号为2K+1
- 已知完全二叉树的总节点数为n求叶子节点个数：
- 已知完全二叉树的总节点数为n求父节点个数：为：n/2
- 已知完全二叉树的总节点数为n求叶子节点为2的父节点个数：
当n为奇数时：n/2
当n为偶数时 : n/2-1
5.如果一棵完全二叉树有N个结点，那么这棵二叉树的深度为【log2（N+1）log2（N+1）】（向上取整）
参考博客：https://www.cnblogs.com/freeman818/p/7252041.html
1、生成树结构
- 前序遍历： DBACEGF（根节点排最先，然后同级先左后右）
- 中序遍历： ABCDEFG (先左后根最后右）
- 后序遍历： ACBFGED （先左后右最后根）
class Node:
def __init__(self,value=None,left=None,right=None):
self.value=value
self.left=left #左子树
self.right=right #右子树
if __name__=='__main__':
root=Node('D',Node('B',Node('A'),Node('C')),Node('E',right=Node('G',Node('F'))))
class Node:
def __init__(self,value=None,left=None,right=None):
self.value=value
self.left=left #左子树
self.right=right #右子树
def preTraverse(root):
'''
前序遍历
'''
if root==None:
return
print(root.value)
preTraverse(root.left)
preTraverse(root.right)
if __name__=='__main__':
root=Node('D',Node('B',Node('A'),Node('C')),Node('E',right=Node('G',Node('F'))))
print('前序遍历：')
preTraverse(root) # DBACEGF
class Node:
def __init__(self,value=None,left=None,right=None):
self.value=value
self.left=left #左子树
self.right=right #右子树
def midTraverse(root):
'''
中序遍历
'''
if root == None:
return
midTraverse(root.left)
print(root.value)
midTraverse(root.right)
if __name__=='__main__':
root=Node('D',Node('B',Node('A'),Node('C')),Node('E',right=Node('G',Node('F'))))
print('中序遍历：')
midTraverse(root) # ACBFGED
class Node:
def __init__(self,value=None,left=None,right=None):
self.value=value
self.left=left #左子树
self.right=right #右子树
def afterTraverse(root):
'''
后序遍历
'''
if root == None:
return
afterTraverse(root.left)
afterTraverse(root.right)
print(root.value)
if __name__=='__main__':
root=Node('D',Node('B',Node('A'),Node('C')),Node('E',right=Node('G',Node('F'))))
print('后序遍历：')
afterTraverse(root) # ACBFGED
前序排列原理：
#####此时执行preTraverse(root.left) 函数
'''
1、第一步 root=Node(D) print D，D入栈[D]
2、第二步 root=Node(D).left=Node(B) print B, B入栈[D,B]
3、第三步 root=Node(B).left=Node(A) print A, A入栈[D,B,A]
4、第四步 root=Node(A).left=None,没有进入递归，顺序执行preTraverse(root.right)
5、第五步 Node(A).right==None，也没有进入递归，此时preTraverse(A) 函数才会正真返回，A出栈[D,B]
6、第六步 A的上级调用函数为：preTraverse(B.left),所以接着会顺序执行preTraverse(B.right),B的左右节点访问后B出栈[D]
7、第七步 Node(B).right==Node(C) print C,C入栈[D,C]
8、第八步 Node(C).left==None, Node(C).right==None,访问完C的左右节点后函数返回C出栈，返回上级调用[D]
9、第九步 此时返回上级调用执行preTraverse(D.right)=Node(E) print E,D出栈，E入栈[E]
'''
'''此时输出结果：DBACE'''
class Node:
def __init__(self,value=None,left=None,right=None):
self.value=value
self.left=left #左子树
self.right=right #右子树
def layered_print( root):
if not root:
return []
curLayer = [root] # 当前层的所有节点
while curLayer:
layerValue = [] # 当前层的值
nextLayer = [] # 下一层的所有节点
for node in curLayer: # 循环当前层所有节点并并获取所有value值
layerValue.append(node.value)
if node.left:
nextLayer.append(node.left) # 将当前层的左节点加入列表
if node.right:
nextLayer.append(node.right) # 将当前层的右节点加入列表
print layerValue # 打印当前层的值
curLayer = nextLayer # 将循环下移一层
'''
['D']
['B', 'E']
['A', 'C', 'G']
['F']
'''
if __name__=='__main__':
root=Node('D',Node('B',Node('A'),Node('C')),Node('E',right=Node('G',Node('F'))))
layered_print(root)
1、hash树描述（就是散列树）
- 散列树选择从2开始的连续质数来建立一个十层的哈希树。
- 第一层结点为根结点，根结点下有2个结点；
- 第二层的每个结点下有3个结点；
- 依此类推，即每层结点的子节点数目为连续的质数。
2、hash树特点
注：关系型数据库中，索引大多采用B/B+树来作为存储结构，而全文搜索引擎的索引则主要采用hash的存储结构，这两种数据结构有什么区别？
- 如果是等值查询，那么哈希索引明显有绝对优势，因为只需要经过一次算法即可找到相应的键值；
- 当然了，这个前提是，键值都是唯一的，如果键值不是唯一的，就需要先找到该键所在位置，然后再根据链表往后扫描，直到找到相应的数据；
- 如果是范围查询检索，这时候哈希索引就毫无用武之地了，因为原先是有序的键值，经过哈希算法后，有可能变成不连续的了，就没办法再利用索引完成范围查询检索；
- 同理，哈希索引也没办法利用索引完成排序，以及like ‘xxx%’ 这样的部分模糊查询（这种部分模糊查询，其实本质上也是范围查询）；
3、建立hash树
- 选择从2开始的连续质数来建立一个十层的哈希树。
- 第一层结点为根结点，根结点下有2个结点；第二层的每个结点下有3个结点；
- 依此类推，即每层结点的子节点数目为连续的质数。到第十层，每个结点下有29个结点。
- 同一结点中的子结点，从左到右代表不同的余数结果。
例如：第二层结点下有三个子节点。那么从左到右分别代表：除3余0，除3余1，除3余2.对质数进行取余操作得到的余数决定了处理的路径。- 以随机的10个数的插入为例，来图解HashTree的插入过程。
- 其实也可以把所有的键-值节点放在哈希树的第10层叶节点处，这第10层的满节点数就包含了所有的整数个数，
但是如果这样处理的话，所有的非叶子节点作为键-值节点的索引，这样使树结构庞大，浪费空间。
4、查找编辑
- 哈希树的节点查找过程和节点插入过程类似，就是对关键字用质数序列取余，根据余数确定下一节点的分叉路径，直到找到目标节点。
- 如上图，最小”哈希树(HashTree)在从4G个对象中找出所匹配的对象，比较次数不超过10次，也就是说：最多属于O(10)。
- 在实际应用中，调整了质数的范围，使得比较次数一般不超过5次。
- 也就是说：最多属于O(5)，因此可以根据自身需要在时间和空间上寻求一个平衡点。
5、删除编辑
- 哈希树的节点删除过程也很简单，哈希树在删除的时候，并不做任何结构调整。
- 只是先查到到要删除的节点，然后把此节点的“占位标记”置为false即可（即表示此节点为空节点，但并不进行物理删除）。
6、hash树优点
- 从哈希树的结构来说，非常的简单，每层节点的子节点个数为连续的质数。
- 子节点可以随时创建，因此哈希树的结构是动态的，也不像某些哈希算法那样需要长时间的初始化过程。
- 哈希树也没有必要为不存在的关键字提前分配空间。
- 从算法过程我们可以看出，对于整数，哈希树层级最多能增加到10。
- 因此最多只需要十次取余和比较操作，就可以知道这个对象是否存在，这个在算法逻辑上决定了哈希树的优越性。
- 从删除算法中可以看出，哈希树在删除的时候，并不做任何结构调整。
- 常规树结构在增加元素和删除元素的时候都要做一定的结构调整，否则他们将可能退化为链表结构，而导致查找效率的降低。
- 哈希树采取的是一种“见缝插针”的算法，从来不用担心退化的问题，也不必为优化结构而采取额外的操作，因此大大节约了操作时间。
7、缺点编辑
- 哈希树不支持排序，没有顺序特性。
- 如果在此基础上不做任何改进的话并试图通过遍历来实现排序，那么操作效率将远远低于其他类型的数据结构。
8、hash索引使用范围
总结：哈希适用在小范围的精确查找，在列数据很大，又不需要排序，不需要模糊查询，范围查询时有用
1、hash索引仅满足“=”、“IN”和“<=>”查询，不能使用范围查询
因为hash索引比较的是经常hash运算之后的hash值，因此只能进行等值的过滤，不能基于范围的查找，
因为经过hash算法处理后的hash值的大小关系，并不能保证与处理前的hash大小关系对应。
2、hash索引无法被用来进行数据的排序操作
由于hash索引中存放的都是经过hash计算之后的值，而hash值的大小关系不一定与hash计算之前的值一样，
所以数据库无法利用hash索引中的值进行排序操作。
3、对于组合索引，Hash 索引在计算 Hash 值的时候是组合索引键合并后再一起计算 Hash 值，
而不是单独计算 Hash 值，所以通过组合索引的前面一个或几个索引键进行查询的时候，Hash 索引也无法被利用。
4、Hash 索引遇到大量Hash值相等的情况后性能并不一定就会比B-Tree索引高。
对于选择性比较低的索引键，如果创建 Hash 索引，那么将会存在大量记录指针信息存于同一个 Hash 值相关联。
这样要定位某一条记录时就会非常麻烦，会浪费多次表数据的访问，而造成整体性能低下。