二叉树的定义

特别的二叉树

满（完美）二叉树Perfect Binary Tree

如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。【除了最后一层都有两个子结点】
满二叉树深度为k，有2^k-1个节点。
PS：区别于Full Binary Tree（完满二叉树），是指一棵二叉树的所有节点要么没有孩子节点，要么有两个孩子节点。

完全二叉树Complete Binary Tree

在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。


如果利用树的深度（即 根的深度为1）
则节点个数为： 2^深度 -1

二叉搜索（排序、查找）树

二叉搜索树是一个有序树。

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

• 它的左、右子树也分别为二叉排序树

  平衡二叉搜索树（AVL（Adelson-Velsky and Landis）树）

  定义：
  平衡因子(Balance Factor,简称BF):BF(T)=hl-hr，hl和hr为左右子树的高度
  AVL树定义为：
  1.空树
  2.任意节点左右子树的高度差不超过1，即|BF|<=1

  存储方式

  链式存储

  

  数组（顺序）存储

  
  如果父节点的数组下标是 i，那么它的左孩子就是 i 2 + 1，右孩子就是 i 2 + 2。

  遍历方式

  深度优先遍历

  • 前序遍历（递归法，迭代法）
  • 中序遍历（递归法，迭代法）

  • 后序遍历（递归法，迭代法）

    广度优先遍历

  • 层次遍历（迭代法）

    进阶高级遍历法morris

    morris遍历可以将非递归遍历中的空间复杂度降为$O(1)$

    节点定义

    C++：

    truct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };

    JS： ```javascript function TreeNode(val, left ,right){ this.val =(val ===undefined? 0:val) this.left =(left ===undefined?null:left) this.right =(right ===undefined?null:right) }

```