树与二叉树

树

树，不是我们常见的长在土里的树木，而是计算机语言中的一种结构。

• 树是一种简单的非线性结构

  • 父节点
    • 树结构中，每一个节点只有一个前件，称为该节点的父节点；没有前件的节点只有一个，称为树的根节点，简称树的根
  • 子节点和叶子节点
    • 树结构中，每一个节点可以有多个后件，称为该节点的子节点。没有后件的节点称为叶子节点
  • 度
    • 树结构中，每一个节点所拥有的后件个数称为该节点的度，所有节点中最大的度称为树的度
  • 深度
    • 定义一棵树的根节点所在的层次为1，其他节点所在的层次等于它的父节点所在的层次加1。树的最大层次称为树的深度
  • 子树
    • 在树中，以某节点的一个子节点为根构成的树称为该节点的一棵子树

• 在树中，树中的节点数等于树中所有节点的度之和再加1

二叉树

1.特点

• 二叉树可以为空，空的二叉树没有节点，非空二叉树有且只有一个根节点
• 每个节点最多有两棵子树，即二叉树中不存在度大于2的节点
• 二叉树的子树有左右之分，其次序不能任意颠倒

2.性质

• 在二叉树的第k层上，最多有$ 2 ^{k-1}(k \geq 1)$个节点
• 深度为m的二叉树中，最多有$ 2 ^{m}-1$个节点
• 对任何一棵二叉树，度为0的节点（即叶节点）总是比度为2的节点多一个
• 具有n个节点的二叉树，其深度至少为$[log{2}n]+1$,其中$[log{2}n]$表示取$log_{2}n$的整数部分
• 具有n个节点的完全二叉树的深度为$[log_{2}n]+1$

3.满二叉树和完全二叉树

• 满二叉树
  • 满二叉树是指除最后一层外，每一层上的所有节点都有两个子节点的二叉树
• 完全二叉树
  • 完全二叉树是指除最后一层外，每一层上的节点数均达到最大值，在最后一层上只缺少右边的若干节点的二叉树
  • 满二叉树一定是完全二叉树，完全二叉树一般不是满二叉树
  • 完全二叉树特点
  • 叶子节点只可能在最后两层出现
  • 对于任一节点，若其右子树的深度为m，则该节点左子树的深度为m或为m+1
  • 二叉树采用链式存储结构。用于存储二叉树中元素的存储节点由数据域和指针域两部分构成
  • 二叉树的存储结构中每一个存储节点有两个指针域，因此，二叉树的链式存储结构也称为二叉链表。对于满二叉树与完全二叉树可以按层次进行顺序存储

二叉树的遍历

1.前序遍历

• 首先访问根节点，然后遍历左子树，最后遍历右子树；并且在遍历左子树和右子树时，仍然先访问根节点，然后遍历左子树，最后遍历右子树

2.中序遍历

• 首先遍历左子树，然后访问根节点，最后遍历右子树。并且在遍历左子树和右子树时，仍然首先遍历左子树，然后访问根节点，最后遍历右子树

3.后序遍历

• 首先遍历左子树，然后遍历右子树，最后访问根节点；并且在遍历左子树和右子树时，仍然首先遍历左子树，然后遍历右子树，最后访问根节点
  • 如果已知一棵二叉树的前序遍历序列和中序遍历序列，可以唯一确定这棵二叉树；已知一棵二叉树的后序遍历序列和中序遍历序列，也可以唯一确定这棵二叉树。但是，已知一棵二叉树的前序列遍历序列和后序遍历序列，不能唯一确定这棵二叉树