树的基本术语

节点的度：节点拥有的子树数
树的度：树内各结点的度的最大值
深度：树中结点的最大层次
其他术语：叶子（终端）结点、分支（非终端）结点、孩子、双亲、祖先、子孙、兄弟、堂兄弟

结点的层次从根开始定义起，根为第一层，根的孩子为第二层。

二叉树

定义：每个结点至多只有两颗子树，且子树有左右之分，其次序不能任意颠倒。
二叉树具有五种形态：

参考：https://blog.csdn.net/xiaoquantouer/article/details/65631708

二叉树的性质：

性质1：二叉树第i层上的结点数目最多为2^(i-1)(i>=1)
性质2：深度为k的二叉树至多有2^k-1个结点（k>=1）
性质3：在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1

满二叉树：高度为k，并且由2^k-1个结点组成的二叉树
完全二叉树：深度为k，有n个结点的二叉树，当且仅当每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应。
下面两个性质是完全二叉树的两个特性：

性质4：具有n个结点的完全二叉树的深度为int(log₂n)+1。其中int(x)表示不超过x的最大整数
性质5:对一棵完全二叉树按层序编号，每层从左到右，则对任意结点i
(1) 如果i=1，则i是二叉树的根，没有双亲。如果i>1,则双亲PARENT(i)是结点int(i/2)
(2) 如果2i>n,则结点无左孩子，否则其左孩子LCHILD(i)是结点2i
(3) 如果2i+1>n,则结点无右孩子，否则其右孩子RCHILD(i)是结点2i+1

二叉树的存储结构

顺序存储结构：用一组地址连续的存储单元依次自上而下、自左而右的存储完全二叉树上的结点元素。一般二叉树的每个结点应该和完全二叉树的结点一一对应
这种存储结构只适用于完全二叉树
链式存储结构
二叉链表：数据域、左右指针域
三叉链表:数据域、左右指针域、指向双亲结点的指针域

二叉树的遍历

按访问根节点的优先顺序，分为先（根）序遍历、先（根）序遍历、后（根）序遍历
例子：

先序遍历的递归算法

中序遍历的非递归算法

遍历二叉树的时间复杂度是O(n),空间复杂度为O(n)

线索二叉树

当以二叉链表作为存储结构的时候，只能找到结点的左右孩子信息，而不能直接得到结点在任一序列中前驱和后继信息，这种信息只有在遍历的动态过程中才能得到。适用条件：需要经常遍历或知道序列的前驱和后继

线索二叉树的标识域：
lchild、LTag、data、RTag、rchild
其中：LTag=0：lchild指示结点的左孩子。LTag=1：lchild指示结点的前驱
同理：RTag=0：rchild指示结点的左孩子。RTag=1：rchild指示结点的前驱

中序线索化链表

树和森林

树的存储结构：

双亲表示法

孩子表示法
使用多重链表：每个结点有多个指针，每个指针指向一棵树的根节点
另一种办法：n个结点有n个孩子链表，而n个头指针又组成一个线性表。
兄弟表示法
又称二叉树表示法，lchild指向该结点的第一个孩子，lchild指向该结点的下一个兄弟结点

森林和二叉树的转换

给定一棵树，可以找到唯一的一棵二叉树与之对应

赫夫曼树和赫夫曼编码

参考：https://www.cnblogs.com/ciyeer/p/9045897.html

字符 a 在哈夫曼编码是 0 ，字符 b 编码为 10 ，字符 c 的编码为 110 ，字符 d 的编码为 111

适用场景：最佳判定算法，某些不均匀的查找或插入操作

回溯树

回溯法不是根据某种确定的计算法则，而是利用试探和回溯的搜索技术求解。是设计递归过程的一种重要方法，其实质是一个先序遍历一棵“状态树”的过程，只是这棵树不是遍历前预先建立的，而是隐含在遍历的过程中。

下面是一个利用回溯法求集合幂集的例子

"""
求幂集的过程可以看成是先序遍历一棵二叉树的过程
实际上并不需要构建一棵树
问：为什么我用yield就是不行呢？？？为什么呢为什么呢？？？
"""
# 求幂集的过程
def getpowerset(i, dataset, powerset):
    if (i >= len((dataset))):
        # yield powerset
        print(powerset)
    else:
        k = len(powerset)
        powerset.append(dataset[i])
        getpowerset(i + 1, dataset, powerset)
        powerset.pop(-1)
        getpowerset(i + 1, dataset, powerset)


def test():
    dset = [2, 5, 6]
    pset = []
    i = 0
    # for item in getpowerset(i, dset, pset):
    #     print(item)
    getpowerset(i, dset, pset)


test()

输出：

在网上查了一下，有一个用二进制来求的，感觉很受益，自己对照着也实现了一下

"""
求幂集的非递归办法
在[0,2^(n-1)]的整数区间上任取一个值x，x的二进制表示可以用来表示s的一个子集：对于x的第i位，如果为1，则此子集包含s的第i个元素，否则不包含
因此，只要遍历 [0,2^(n-1)]的整数区间，就能列举出s的所有子集，这些子集的集合就是s的幂集。
"""
def power_set(s):
    n = len(s)
    test_marks = [1 << i for i in range(0, n)]   # 1的二进制表示：0000 00001
    for k in range(0, 2 ** n):
        l = []
        for idx, item in enumerate(test_marks):  # enumerate可同时返回位序和数值
            if k & item:
                l.append(s[idx])
        yield set(l)    # yield可以看成是返回


def __test__():
    s = [1, 2, 3, 4]
    for e in power_set(s):
        print(e)


__test__()

算法学习笔记——二叉树