树

度：树中结点拥有的子树个数称为结点的度

分支结点：度不为0度结点称为分支结点。
叶结点：度为0的结点称为叶结点，即终端结点

树的度：树内个节点的度的最大值
树的高度：树中结点的最大层次（根结点为第一层）称为树的高度

有序树：如果将树中结点的各子树堪称从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序数

森林：森林是m棵互不相交的树的集合

二叉树

二叉树定义：本身是有序树（左右子树不能互换），并且树中包含的各个节点的度不能超过 2，即只能是 0、1或者 2（这里的1可以是左子树也可以是右子树）

斜树：所有的结点都只有左子树的二叉树叫左斜树，所有结点都只有右子树的二叉树叫右斜树（可以理解为线性表）

满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有的叶子结点都在同一层上。

完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层所有的结点都**连续**集中在最左边

二叉树性质

**性质1**:在二叉树的第i层最多有2^(i-1)个结点

证明：  由题可知，易证，cnt[i]=2^(i-1);

**性质2**:深度为k的二叉树最多有2^k-1个结点

证明：  等比数列求和公式Sn=a1(1-q^n)/(1-q)

**性质3**:对任何一棵二叉树T，如果其叶子结点个数为n0，度为2的结点个数为n2，则n0=n2+1

证明：   一棵二叉树中只有度分别为0，1，2的三种结点
        设度为1的节点有n1个，则树T的总结点数n=n0+n1+n2

        又因为共有n个结点，则共有n-1条连线（总有一条连线指向除了根结点的结点-除根结点每个结点只有一个父亲）
        度为2的结点连出去两条，度为1的结点连出去一条，则连线数也可以算作

        故有2*n2+1*n1+0*n0=n-1==n0+n1+n2-1  -->  n0=n2+1

**性质4**:具有n个结点的完全二叉树的深度为|log2(n)|+1

证明：   设完全二叉树的高度为x，因为完全二叉树的究极形态是x层的满二叉树，最弱形态是x-1层多一个，满二叉树的结点个数为2^x-1
        则可列出n<=2^x-1    又因为这里n和x都是整数，所以n<2^x   得x>log2(n);
               n>=2^(x-1)-1+1  得x<=log2(n)+1  
        又因为x是整数，故只能是|log2(n)|+1（这里是向下取整）


**性质5**:如果对一棵具有n个结点的完全二叉树的结点按层序进行编号，则
      (1)如果i=1，则结点i为二叉树根结点，如果i>1,则其父结点为i/2（向下取整），2*i是其左子树，2*i+1是其右子树
      (2)如果2*i>n,则结点i无左子树（为叶子结点），否则其左子树是结点2*i
      (3)如果2*i+1>n,则结点i无左子树，否则其右子树是结点2*i+1

二叉树的遍历

概念：二叉树的遍历是指从根结点出发，按照某种次序一次访问二叉树中的所有节点，使得每个节点被访问一次且仅被访问一次

**前序遍历**：若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树

**中序遍历**：若二叉树为空，则空操作返回，否则先中序遍历左子树，再访问根结点，再中序遍历右子树

**后序遍历**：若二叉树为空，则空操作返回，否则从左到右先叶子结点后根结点的方式遍历访问左右子树，最后访问根结点

**层序遍历**：若二叉树为空，则空操作返回，否则从根结点开始逐层访问，每一层从左到右遍历结点。

因为老是忘记，就想着做个笔记，写的不好，不吝赐教