二叉树入门

树的常用名词

• 度：结点拥有子结点的数目
• 孩子节点：结点的子结点
• 双亲结点：结点的父结点
• 叶子结点：度为0的结点
• 分支结点：度不为0的结点
• 兄弟结点：若多个结点的父结点是同一个结点，则它们互为兄弟结点
• 树的深度：树的层数

二叉树分类

• 满二叉树：每一层的结点数目都达到最大数目
• 左斜数/右斜树：每个分支结点只有左树或右树
• 完全二叉树：第一层到次下层的每一层结点数目达到最大，且最下层的叶子结点集中在左侧

二叉树断言

• 推论1：第n层最多拥有的节点数为：
  数学公式
• 推论2：一个深度为n的树，最多拥有的节点数为(利用等比数列推导)：
  数学公式

• 推论3：对于除最后一层，其余各层均达到最大结点数目的二叉树，它的层数为：

  
  数学公式
• 推论4：满二插树一定是完全二叉树，反之不一定成立
• 推论5：度为0的节点数 = 度为2的节点数+1

二叉树存储结构(C++)

struct TreeNode {
       TreeNode *left, *right;
       int val;
       TreeNode(int v):left(nullptr), right(nullptr), val(v) {}
};

二叉树遍历

前序遍历

void preorder(TreeNode *node) {
       if (node != NULL) {
              printf("%d\n", node->val);
              preorder(node->left);
              preorder(node->right);
       }
}

中序遍历

void inorder(TreeNode *node) {
       if (node != NULL) {
              preorder(node->left);
              printf("%d\n", node->val);
              preorder(node->right);
       }
}

后序遍历

void postorder(TreeNode *node) {
       if (node != NULL) {
              preorder(node->left);
              preorder(node->right);
              printf("%d\n", node->val);
       }
}

层序遍历

void layerorder(TreeNode *node, std::vector<int> *nums, bool root = true) {
       // 不能确定node是否为空
       if (!node) {
              return;
       }
       // 是否为根结点?
       if (root) {
              nums->push_back(node->val);
       }
      // 将左结点和右结点的值push到队列中
       if (node->left != nullptr)
              nums->push_back(node->left->val);
       if (node->right != nullptr)
              nums->push_back(node->right->val);
      // 对该结点的左结点和右结点左同样的事
       layerorder(node->left, nums, false);
       layerorder(node->right, nums, false);
}

总结：前/中/后序遍历直观地看只是输出当前结点值这个操作位置不同。而层序遍历依赖队列实现，更为复杂