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

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

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

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

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

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

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

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

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

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

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

二叉树是由树演化而来的一种数据结构，上面所有术语均适用于二叉树。二叉树与树不同之处在于，树的每一个结点(除终端结点外)允许有若干子树分支;而二叉树只允许有左右两个子树分支，即不存在度大于 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、伸展树等。