导图社区 树的结构
二叉树、二叉查找树、满二叉树、完全二叉树、平衡二叉树
社区模板帮助中心，点此进入>>
互联网9大思维
组织架构-单商户商城webAPP 思维导图。
域控上线
python思维导图
css
CSS
计算机操作系统思维导图
计算机组成原理
IMX6UL(A7)
考试学情分析系统
树
定义
节点
一个数据、两个指针如果有节点就指向节点、没有节点就指向null
节点连接起来就成了树
特点
树是一种非线性的数据结构链表、数组是线性的数据结构
树的平均运行时间更短
从根节点到最底层节点的层数叫树的深度|高度
空树的高度为0
没有儿子的节点叫叶子
一棵树至少会有一个节点(根节点)
类型
二叉树
每个节点不能多于有两个儿子
遍历
先序遍历
先访问根节点，然后访问左节点，最后访问右节点(根->左->右)
如果访问有孩子的节点，先处理孩子的，随后返回
中序遍历
先访问左节点，然后访问根节点，最后访问右节点(左->根->右)
后序遍历
先访问左节点，然后访问右节点，最后访问根节点(左->右->根)
性质
中序+先序
可以确定二叉树
必须有中序
中序+后序
先序+后序
不可以确定二叉树
若二叉树的层次从0开始，则在二叉树的第i层至多有2^i个节点
高度为k的二叉树最多有2^(k+1)-1个节点
二叉树的节点个数可以为0
二叉查找树|二叉搜索树
当前根节点的左边全部比根节点小当前根节点的右边全部比根节点大
无论任何一颗子树，左边都比根要小，右边比根要大
中序遍历二叉查找树得到的结果是排好顺序的
满二叉树
所有的叶节点全部在底层，并且在底层全部铺满的二叉树
一棵二叉树的结点要么是叶子结点，要么它有两个子结点
如果一个二叉树的层数为k且节点总数是(2^k)-1则它就是满二叉树
完全二叉树
叶节点只能出现在最后两层，并且最底层的叶节点都向左对齐
若二叉树的深度为k，除第k层外其它各层的节点数都达到最大个数，第k层所有的节点都连续集中在最左边
平衡二叉树
它是一棵空树或它的左右两个子树的高度差的绝对值不超过1左右两个子树都是一棵平衡二叉树并且满足二叉搜索树的规则
平衡二叉树必须是二叉搜索树
满二叉搜索树
既是满二叉树又是二叉搜索树
最优二叉树|哈夫曼树
带权路径长度最短的树，权值较大的结点离根较近
