2020计算机考研复习要点：二叉树

2020考研初试的时间已经越来越近了，大家的专业课的复习也要抓紧了，报考计算机的小伙伴要考哪些知识呢？跟着天任启航一起来看看二叉树的知识点吧！

先来看一下树的基本概念：

树的深度：树中结点的较大层次

树的高度：从叶子结点开始定义，叶子结点为第1层，往上依次递增，直至根结点。

结点：树的结点包含一个数据元素以及若干指向其子树的分支

度：结点所拥有的子树数量

终端节点：度为0的结点称为叶子结点或终端结点

树的度：树中各结点度的较大值

层次：从根开始定义，根为第1层，依次递增

有序树：树中结点的各子树从左往右是有次序的，不可相互交换；反之则是无序树

森林：一棵非空树删掉根结点，即是森林

二叉树是由树演化而来的一种数据结构，上面所有术语均适用于二叉树。二叉树与树不同之处在于，树的每一个结点（除终端结点外）允许有若干子树分支；而二叉树只允许有左右两个子树分支，即不存在度大于 2结点。

1、二叉树的性质

二叉树第i层上的结点数目较多为 2{i-1} (i≥1)；

深度为k的二叉树至多有2{k}-1个结点(k≥1)；

包含n个结点的二叉树的高度至少为log2 (n+1)；

在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1。

2.二叉树的分类

二叉树分为包括满二叉树、完全二叉树和二叉搜索树。

(1)满二叉树

最后一层没有子节点，其余每层都有两个子节点，最后一层都是叶子结点。

最后一层叶子节点数为2k-1；

第i层的节点数是2i-1；

总结点数是：2k-1,且总数为奇数；

(2)完全二叉树

有n 层深度的二叉树，除了第n层其余各层节点都达到较大数，且第n层的节点都在左边。完全二叉树只允许最后一层的右侧有空缺，对任一节点，如果其右子树的深度为j，则其左子树的深度必为j或j+1。 即度为1的点只有1个或0个；除最后一层，第 i 层的节点数是：2i−1；有n个节点的完全二叉树，其深度为：log2n+1或为log2n+1；满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。

(3)二叉搜索树

它是一棵空树或它的左右两个子树的高度差的绝 对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。