数据结构与算法二叉树

二叉树：

    使用常用的一种数据结构，处理起来比较方便，并且普通树可以很方便地转换成二叉树

    普通树转二叉树：孩子变左子树、兄弟变右子树

    定义：节点的度最多为2

    二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个节点

特殊的二叉树：

    满二叉树：

        如果一棵二叉树只有度为0的节点和度为2的节点，并且度为0的节点在同一层上，则这棵二叉树为满二叉树

    完全二叉树：

        深度为k，有n个节点的二叉树当且仅当其每一个节点都与深度为k的满二叉树中编号从1到n的节点一一对应时，称为完全二叉树

        除最后一层外，其它层全满，最后一层的节点必须从左到右依次排列，就称为完全二叉树

二叉树的性质(重点)：

    性质1：二叉树的第i层上至多有2^(i-1)（i≥1）个节点

    性质2：深度为h的二叉树中至多含有2^h-1个节点

    性质3：若在任意一棵二叉树中，有n0个叶子节点，有n2个度为2的节点，则必有n0=n2+1

    性质4：具有n个节点的满二叉树深为log2n+1

    性质5：若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n），那么，对于编号为i（i≥1）的节点：

        当i=1时，该节点为根，它无双亲节点

        当i>1时，该节点的双亲节点的编号为i/2

        若2i≤n，则有编号为2i的左节点，否则没有左节点

        若2i+1≤n，则有编号为2i+1的右节点，否则没有右节点

二叉树的操作：

    构建、销毁、遍历、高度、密度、插入、删除、查询、求左、求右

二叉树的遍历(重点)：

    前序：根、左、右

    中序：左、根、右

    后序：左、右、根

    层序：从上到下、从左到右的顺序依次遍历一棵树，必须配合队列完成

    注意：前中后序遍历取决于根的遍历顺序，左右子树的遍历顺序不会改变

    注意：可以根据 前序+中序 或者 后序+中序 就可以还原一棵树，但是只有一个遍历或者 前序+后序 是无法还原的

    要会写遍历结果、能倒推还原树

二叉树的存储：

    顺序：必须按照完全二叉树的顺序格式存储节点数据，如果有空位置则使用特殊数据代替，保证形成完全二叉树

        数据项：

            存储节点的内存首地址

            容量

改变指针变量就二级指针 普通变量就改变地址