二叉树概念

  1.树的定义。

    树就是节点与节点连接形成的，每个节点连接的下一个节点间不能彼此连接，否则就是图不是树了。

  2.树节点的分类。

    根节点：树的第一个节点。

    度：连接2个节点，就是度为2，连接1个节点，就是度为1，不连接节点，就是度为0。

    叶节点：不连接节点的节点称为叶节点。

  3.树的层次。

    树中节点的最大深度。

  4.树图形简述(二叉树例)。

  5.二叉树的定义。

    每个节点最多有两个子树，左右子树存在顺序。

  6.二叉树的五种基本形态。

    ①空二叉树。

    ②只有一个根节点。

    ③只有左子树。

    ④只有右子树。

    ⑤既有左子树也有右子树。

  7.二叉树的特殊情况。

    ①斜树：相当于左子树和右子树

    ②满二叉树：最高深度—最底深度等于0，并且不存在度为1的情况。

    ③平衡子树：最高深度—最低深度小于等于1的都是。

    ④完全二叉树：1、叶节点只有最后二层。2、最下层的叶子只能从左到右排布。3、倒数第2层，若有叶节点，必是右连续。4、若节点度为1，必是连接左节点。5、同节点排布，完全二叉树深度最小。

  8.二叉树的性质。

    ①每层至多2^(i-1)个节点。

    ②深度为k的二叉树最多有2^k-1个节点。

    ③对任何一个二叉树，度为0的节点(总N0)是度为2的节点(总N2)的：N0=N2-1。

    ④具有n个节点的二叉树深度为|log2^n|+1，如log2^15+1=4。

    ⑤对于一个n个节点的二叉树，按编号编好后

    1、如果i=1，则无连接他的上一个节点。若i>1，则连接它的节点是|i/2|，如3/2=1。

    2、如果2i>n，则节点i无左子树，否则左子树编号为2i。

    3、如果2i+1>n，则节点i无右子树，否则右子树编号为2i+1。

  9.二叉树的遍历。

    DFS深度优先遍历：简称深优。

    BFS广度优先遍历：简称广优。

    以下图二叉树作为讲解分析。

    D该节点值  L该节点的左子树值  R该节点的右子树值 

    深优 ①——前序遍历DLR：输出ABDGHJCEIF

分析：A先进栈，出来后，将右左顺序进栈，每出一个后将右左放入栈，直到完成就是前序遍历的元素输出。

    深优 ②——中序遍历LDR：输出GDJHBAEICF

分析：A开始将左边全部节点放进栈，每出一个将右子树的左边全部放进栈，没有右的话就出。

    深优 ③——后序遍历LRD：输出GJHDBIEFCA

分析：A开始将左边一个个全部放入栈，到最后一个时候判断右边有没节点，有的话将右子树的左边一个个全部放进栈，直到没有为止才出一个，出了后，再对即将要出的判断右子树存在节点不，存在继续将右的左边所有进栈，直到元素全部输出完成。

    广优——层序遍历(队列)：输出ABCDEFGHIJ

分析：A先进，出来后将左右顺序放入，每出一个都将左右顺序放入，直到完成。