1.什么是树2.树的相关定义3.二叉树的定义4.二叉树的性质5.几种特殊形态的二叉树6.二叉树的存储方式7.二叉树的遍历7.1二叉树前中后序遍历非递归/递归7.2二叉树层序遍历普通正S倒S8.二叉树的构建方法9.二叉搜索树BST树10.平衡二叉树 — AVL树80%— 旋转11.平衡二叉树 — 红黑树20%12.B-树B树13.B树1.什么是树是由n(n0)个节点组成的有限集合2.树的相关定义1.有且仅有一个特定的被称为根(root)的节点只有直接后继没有直接前驱2.当n1的时候除根之外其余节点可以分成m个互不相交的有限集合T1,T2,……Tm,这m个互不相交的树的相关概念1.树的节点包含一个数据域和若干的指向其子树的分支指针域2.节点的度节点包含的子树的个数3.树的度一棵树中最大的节点的度当作该树的度4.叶子节点终端节点度为0的节点5.非叶子节点分支节点度不为0的节点6.孩子节点子节点节点的子树的根节点称为该节点的孩子7.双亲结点父节点相应的该节点就是其孩子节点的双亲节点8.节点的层次从根节点出发根节点为第一层根的孩子为第二层以此类推9.节点的深度从根节点出发到该节点的唯一路径上边的个数根节点的深度是010.节点的高度从根节点出发到其叶子节点的最长路径上边的个数叶子节点的高度是03.二叉树的定义4.二叉树的性质性质1.二叉树的第i层最多可以有2^(i-1)个节点 性质2.深度为k的二叉树最多可以有2^k -1个节点 性质3.任意一棵二叉树度为0的节点个数记为N0度为2的节点个数记为N2N0N215.几种特殊形态的二叉树满二叉树(完美二叉树) 由2^k-1个节点组成的一棵深度为k的二叉树就是满二叉树 完全二叉树 首先对满二叉树进行编号从根节点出发根是1号从上至下从左至右6.二叉树的存储方式7.二叉树的遍历7.1二叉树前中后序遍历非递归/递归7.2二叉树层序遍历普通正S倒S8.二叉树的构建方法9.二叉搜索树BST树10.平衡二叉树 — AVL树80%— 旋转11.平衡二叉树 — 红黑树20%12.B-树B树13.B树