精选优质文档-倾情为你奉上【黑马程序员】二叉树面试详解二叉树二叉树是每个节点最多有两个子树的树结构,通常子树被称作左子树和右子树,左子树和右子树同时也是二叉树,二叉树的子树有左右之分,并且次序不能任意颠倒.二叉树是递归定义的,特殊二叉树:斜树:所有的结点都只有左子树(左斜树),或者只有右子树(右斜树)满二叉树:所有的分支结点都存在左子树和右子树,并且所有的叶子结点都在同一层上,这样就是满二叉树.就是完美圆满的意思,关键在于树的平衡.特点为:叶子只能出现在最下一层非叶子节点度一定是在同样深度的二叉树中,满二叉树的结点个数最多,叶子树最多完全二叉树:对一颗具有n个结点的二叉树按层序排号,如果编号为i的结点与同样深度的满二叉树编号为i结点在二叉树中位置完全相同,就是完全二叉树,满二叉树必须是完全二叉树,反过来不一定成立特点:叶子结点只能出现在最下一层(满二叉树继承而来)最下层叶子结点一定集中在左部连续位置倒数第二层,如有叶子结点,一定出现在右部连续位置同样结点树的二叉树,完全二叉树的深度最小(满二叉树也是对的)二叉树的遍历
