树是实现抽象数据类型(ADT )或抽象数据类型的数据结构，它模拟具有树结构性质的数据集合。 这是由n(n=1)个有限节点构成的具有层次关系的集合。 之所以将其称为“树”，是因为它看起来像是倒挂着的树。 也就是说，是因为根朝上，叶子朝下。
树的性质：
树可以没有节点。 在这种情况下，树称为空树。 树的层次是从根节点开始计数的，根节点是第一个层次，而“寄生树”的根节点是第二个层次。 节点的部分树的根数称为节点度，树中节点的最大度称为树度。 因为一边连接两个节点，且树上不存在环，所以对于具有n个节点的树，边的数量必须为n-1。
满足连通，边数等于顶点数-1的结构必须是一棵树。 因为叶节点被定义为度0的节点，所以如果树上只有一个节点，即只有根节点，根节点也算作叶节点。 节点深度是从根节点(深度1 )自上而下累积在节点上的深度值。
节点的高度是指从最下层叶的节点从底向上逐层累积到该节点时的高度值。
树的深度是指树中节点的最大深度，树的高度是指树中节点的最大高度。 对树来说，深度和高度相等。 把多棵树组合起来称为森林。 也就是说，森林是几棵树的集合。
之所以将其称为“树”，是因为它看起来像是倒挂着的树。 也就是说，是因为根朝上，叶子朝下。 具有以下特征：
(01 )每个节点有零或多个子节点；
) 02 )没有父节点的节点称为根节点；
) 03 )每个非根节点只有一个父节点。
) 04 )除了根节点外，每一子节点可划分成不相交的多个子树。 二叉树是每个节点最多有两个子树的树结构。 这有五种基本形式。 二叉树可以是空集合。 有根的左子树或右子树； 或者左、右子树为空。
二叉树的性质
二叉树具有TODO (上标和下标)的性质
性质1 (二叉树第I层上的节点数最大为2(I-1 ) ) I1 )。
性质2 )深度为k的二叉树最多具有2{k}-1个节点(k1 )。
性质3 :包含n个节点的二叉树的高度至少为log2(n1 )。
性质4 :在任意一棵二叉树中，设终端节点数为n0、度为2的节点数为n2，则n0=n2 1。
性质1：二叉树第i层上的结点数目最多为 2{i-1} (i1)
证明：用“数学归纳法”证明。
(01 ) i=1时，第I层的节点数为2{i-1}=2{0}=1。 因为第一层只有一个根节点，所以命题成立。
) 02 )假设为i1，则第I层的节点数为2{i-1}。 这是根据(01 )推算的！
基于此假设，可推断‘第(i 1 )层的节点数目为2。
因为二叉树的每个节点至多有两个孩子，所以“第(i 1)层上的节点数”是“第I层的节点数的两倍”。 也就是说，第(i 1 )层上的节点数的最大值=22(I-1 )=2(I ) )。
因此，如果假说成立，则原命题得到证实！
性质2：深度为k的二叉树至多有2{k}-1个结点(k1)
证明：在具有相同深度的二叉树中，当每层包含最大节点数时，该树中节点数最多。 利用“性质1”，深度k的二叉树的节点数至多如下
20 21 … 2k-1=2k-1
所以，原来的命题得到了证明！
性质3：包含n个结点的二叉树的高度至少为log2 (n+1)
证明：从“性质2”可以看出，高度为h的二叉树最多具有2 { h }1个节点。 相反，包含n个节点的二叉树的高度至少是log2(n1 )。
性质4：在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2 1
证明：由于二叉树中所有节点的频数都在2以下，所以节点总数(记为n ) )、0度节点数(n0 )、1度节点数) n1 )、2度节点数) n2 )。 由此，得到方程式1。
(等式1 ) n=n0 n1 n2
另一方面，0度节点中没有孩子，1度节点中有一个孩子，2度节点中有两个孩子，所以二叉树中孩子的节点总数为n1 2n2。 另外，只有根不是任何节点的孩子。 因此，二叉树中的节点总数可以用等式2表示。
(等式2 ) n=n1 2n2 1
根据(等式1 )和等式2 )计算，n0=n2 1。 原来的命题得到了证实！
二叉树的定义：高度为h且具有2 { h }1个节点的二叉树称为二叉树。
二叉树的定义：在一棵二叉树中，只有最下面的两个节点的度可以小于2，而最下面的叶节点集中在靠左的几个位置。 这样的二叉树叫做完全二叉树。
特点：叶片节点仅出现在最下层和次下层，最下层叶片节点集中在树的左侧。 显然，一棵二叉树一定是一棵完全二叉树，而完全二叉树并不一定是二叉树。