二叉树

'''
二叉树


附录:
    使用遍历序列还原二叉树:
        1. 使用先序序列或后序序列, 加上中序序列就可以还原二叉树.
           先序序列的第一个元素是根节点, 后序序列的最后一个元素是根节点, 这样根节点确定了.
           中序序列的根节点是在中间, 在左子二叉树和右子二叉树之间, 根据上一步获得到的根节点, 在中序序列中找到根节点并左右分开, 即得到了左右两个子二叉树
           根据先序序列或后序序列的特点, 进行一一还原.
        2. 若是真二叉树, 可以不需要中序序列, 使用先序序列和后序序列也可以还原.
           先序序列的第一个元素是根节点, 然后是以左子二叉树的根节点为首的左子二叉树, 然后是以右子二叉树的根节点为首的右子二叉树.
           后序序列的最后一个元素是根节点, 之前是以右子二叉树的根节点为末尾的右子二叉树, 再之前是以左子二叉树的根节点为末尾的左子二叉树.
           这样根节点可以确定, 根节点的左子节点可以在先序序列(第二个元素)中确定, 根节点的左子二叉树, 可以在后序序列中确定(在后序序列中根节点的左子节点之前的都属于左子二叉树)
           根节点的右子节点可以在后序序列(倒数第二个元素)中确定, 根节点的右子二叉树, 可以在先序序列中确定(在先序序列中根节点的右子节点之后都属于右子二叉树)
'''


class BinNode():
    parent = None
    lChild = None
    rChild = None

    data = None
    height = -1

    def __init__(self):
        self.height = 0

    def insertAsLC(self, e):
        '''作为左孩子插入新节点'''
        self.lChild = e

    def insertAsRC(self, e):
        '''作为右孩子插入新节点'''
        self.rChild = e

    def succ(self):
        '''(中序遍历下)当前节点的直接后继'''
        pass

    def travLevel(self, x):
        '''子树层次遍历'''
        visit, 队列 = [], []
        if x.height != -1:
            队列.append(x)
        while 队列:
            x = 队列.pop(0)
            visit.append(x)
            if x.lChild is not None:
                队列.append(x.lChild)
            if x.rChild is not None:
                队列.append(x.rChild)
        return visit

    def travPre_recursion(self, x, visit):
        '''子树先序遍历(迭代版)
        如果是空节点, 那么就直接返回
        '''
        if x is None:
            return visit
        visit.append(x)
        self.travPre_recursion(x.lChild, visit)
        self.travPre_recursion(x.rChild, visit)
        return visit

    def travPre_iteration(self, x):
        '''子树先序遍历(迭代版)
        定义一个栈, 一个遍历列表. 如果传入的是一个节点, 那么将节点添加到栈中.
        如果栈中有节点, 那么就循环执行:
            取出栈节点, 将此节点添加到遍历列表中.
            如果此节点的右子节点存在节点, 那么将此子节点加入栈(先加入, 会压到左节点取出完毕后取出)
            如果此节点的左子节点存在节点, 那么将此子节点加入栈(后加入, 下次循环将现取出此节点)
        '''
        visit,  = [], []
        if x.height != -1:
            .append(x)
        while :
            x = .pop()
            visit.append(x)
            if x.rChild is not None:
                .append(x.rChild)
            if x.lChild is not None:
                .append(x.lChild)

    def travPre_iteration2(self, x):
        '''子树先序遍历(迭代版)(优化版)
        原理:
            在前两个方法中, 可以发现子树先序遍历会先一层一层的遍历左子节点, 左子节点的左子节点, 等等等等, 这个结论在任意大小的二叉树中都存在.
            因此, 可以先遍历左侧所有左子节点, 然后一一将以右节点为根节点的整个树加入栈中, 然后再次遍历.
        定义一个栈, 一个遍历列表. 如果传入的是一个节点, 那么将节点添加到栈中.
        如果栈中有节点, 那么就循环执行:
            取出一个节点, 添加到遍历列表中, 并再次开启一个子循环:
                如果这个节点没有子节点则子循环结束
                将这个节点的左子节点添加到遍历列表中
                如果存在右子节点, 则将右子节点添加到栈中
                左子节点替代这个节点进行下次循环
        '''
        visit,  = [], []
        if x.height != -1:
            .append(x)
        while :
            x = .pop()
            visit.append(x)
            while True:
                if x.lChild is None:
                    break
                visit.append(x.lChild)
                if x.rChild is not None:
                    .append(x.rChild)
                x = x.lChild

    def travIn_recursion(self, x, visit=[]):
        '''子树中序遍历(递归版)'''
        if not x:
            return visit
        self.travIn_recursion(x.lChild, visit)
        visit.append(x)
        self.travIn_recursion(x.rChild, visit)
        return visit

    def travIn_iteration2(self, x):
        '''子树中序遍历(迭代版)(优化版)
        原理:
            中序遍历会先遍历左子节点, 控制权会先流传到根节点的最后一层左子节点上, 遍历自己然后向上遍历, 最后一层左子节点的父节点在宏观上来看依旧是左侧一列的一部分, 所以和左序遍历类似, 中序遍历也有左侧一列的存在.
        '''
        visit,  = [], []
        while True:
            while x:
                if x.lChild is not None:
                    .append(x)
                    x = x.lChild
            if  is False:
                break
            x = .pop()
            visit.append(x)
            x = x.rChild
        return visit

    def travPost_recursion(self, x, visit=[]):
        '''子树后序遍历(递归版)'''
        if not x:
            return visit
        self.travPost_recursion(x.lChild, visit)
        self.travPost_recursion(x.rChild, visit)
        visit.append(x)
        return visit


class BinTree():
    _size = 0  # 节点数量
    _root = None  # 根节点

    def _updateHeight(self, x):
        '''更新节点x的高度'''
        x.height = (x.lChild.height + 1) if (x.lChild.height > x.rChild.height) else (x.rChild.height + 1)
        return x

    def _updateHeightAbove(self, x):
        '''更新节点x及其无限父类的高度'''
        while x:
            self._updateHeight(x)
            x = x.parent

    def size(self):
        '''获取数的节点数'''
        return self._size

    def empty(self):
        '''是否是空树'''
        return not self._root

    def root(self):
        '''获取根节点'''
        return self._root

    def insertAsRC(self, x, e):
        '''将节点 e 添加到节点 x 的右孩子上
        参数:
            x: 父节点
            e: 即将加入父节点右孩子的子节点
        返回值:
            父节点的右子节点

        节点数量加一, 执行父节点中的添加右孩子方法, 将节点 e 添加到节点 x 的右孩子上,
        更新节点 x 的高度, 返回节点 x 的右子节点
        '''
        self._size += 1
        x.insertAsRC(e)
        self._updateHeightAbove(x)
        return x.rChild

    def insertAsLC(self, x, e):
        '''将节点 e 添加到节点 x 的左孩子上
         insertAsRC 方法类似
        '''
        self._size += 1
        x.insertAsLC(e)
        self._updateHeightAbove(x)
        return x.lChild

'''
树和二叉树

节点 -- 树上的元素
叶子节点 -- 没有子节点的节点
前驱节点(父节点) -- 节点的上一节点
后继节点(子节点) -- 节点的直属下节点
根节点 -- 没有前驱节点的节点
: 某节点拥有子节点的个数
兄弟节点: 同一父节点的多个节点
堂兄弟节点: 不同父节点但在同层的节点
深度(高度): 层次

在二叉树上,  i 层最多有 2^(i-1) 个节点 (i >= 1)
高度为 k 的二叉树, 最多有 2^k - 1 个节点 (k >= 1)
在二叉树上, 叶子节点树为 n, 度为2的节点数为 m,  n = m + 1
具有 n 个节点的完全二叉树的深度为 log2n + 1


满二叉树 -- 深度为 k, 且有 2^k - 1个节点的二叉树
完全二叉树 -- 同一深度, 按从左到右排列, 没有空隙节点
'''


class 顺序存储():
    def __init__(self):
        self.tree = []


class 二叉链表节点():
    def __init__(self, data, lchild=None, rchild=None):
        self.data = data
        self.lchild = lchild
        self.rchild = rchild


class 三叉链表节点():
    def __init__(self, data, parent=None, lchild=None, rchild=None):
        self.data = data
        self.lchild = lchild
        self.rchild = rchild
        self.parent = parent


class 二叉树():
    tree = None

    def __init__(self):
        node5 = 二叉链表节点('5')
        node4 = 二叉链表节点('4')
        node3 = 二叉链表节点('3')
        node2 = 二叉链表节点('2', node4, node5)
        self.tree = 二叉链表节点('1', node2, node3)

    def 先序遍历(self):
        '''先遍历父节点'''
        datas = []
        self._先序遍历(self.tree, datas)
        return datas

    def _先序遍历(self, node=None, datas=[]):
        datas.append(node.data)
        if node.lchild is not None:
            self._先序遍历(node.lchild, datas)
        if node.rchild is not None:
            self._先序遍历(node.rchild, datas)

    def 中序遍历(self):
        '''第二遍历父节点'''
        datas = []
        self._中序遍历(self.tree, datas)
        return datas

    def _中序遍历(self, node=None, datas=[]):
        if node.lchild is not None:
            self._中序遍历(node.lchild, datas)
        datas.append(node.data)
        if node.rchild is not None:
            self._中序遍历(node.rchild, datas)

    def 后序遍历(self):
        datas = []
        self._后序遍历(self.tree, datas)
        return datas

    def _后序遍历(self, node=None, datas=[]):
        '''最后遍历父节点'''
        if node.lchild is not None:
            self._后序遍历(node.lchild, datas)
        if node.rchild is not None:
            self._后序遍历(node.rchild, datas)
        datas.append(node.data)


if __name__ == "__main__":
    obj = 二叉树()
    print(obj.先序遍历())
    print(obj.中序遍历())
    print(obj.后序遍历())