什么是二叉树
4.1节的树,一个结点可以有任意多个孩子。这一节看一种更规整的树:每个结点最多两个孩子,而且两个孩子分左右。这样的树叫二叉树。
它的定义也是递归的。二叉树是n个结点的有限集合。n等于0时,叫空二叉树。n大于0时,它由一个根和两棵互不相交的二叉树组成,这两棵分别叫根的左子树和右子树。
把定义代入一棵具体的二叉树。这一节一直用它:
根。这棵二叉树有5个结点,不是空的,所以有一个根,就是A。图里的虚线框,是空着的位置。
左子树。A的左下挂着B和D。它们合起来,是A的左子树。
右子树。A的右下挂着C和G,是A的右子树。两棵子树没有共同的结点。
子树又是二叉树。A的左子树,根是B。B的左子树只有D,右子树是空的。D的两棵子树也是空的。一层一层往下拆,最后都拆到空二叉树。
本节问题B只有一个孩子D,C也只有一个孩子G。这两个结点的情况一样吗?
学完这一节,你能判断什么样的数据可以看成二叉树,分清左孩子和右孩子,说出一棵二叉树是哪种形态。
左孩子和右孩子
左子树的根,叫左孩子。右子树的根,叫右孩子。
A的两个孩子。A的左子树以B为根,B是A的左孩子。A的右子树以C为根,C是A的右孩子。
B只有左孩子。B的左孩子是D。B的右子树是空的,所以B没有右孩子。
C只有右孩子。C的左子树是空的,所以C没有左孩子。C的右孩子是G。
4.1节的名词照样用。度只数孩子,不管在左还是在右:
双亲和叶子。D的双亲是B,G的双亲是C。D和G没有孩子,是叶子。
度。A有两个孩子,度是2。B、C各有一个孩子,度是1。D、G的度是0。
层次和高度。A在第1层,B、C在第2层,D、G在第3层。这棵二叉树的高度是3。
五种基本形态
由定义,一棵二叉树要么是空的,要么有根。有根时,左子树、右子树各自可能是空的,也可能不是。合起来一共五种情况,叫二叉树的五种基本形态。
这棵树里,五种都找得到:
只有根。以D为根的子树,左右都是空的,只有一个根。
以D为根
只有左子树。以B为根的子树,左子树不空,右子树是空的。
以B为根
只有右子树。以C为根的子树,左子树是空的,右子树不空。
以C为根
任何一棵二叉树,只看它的根,一定是这五种之一。它的左子树、右子树,又各是这五种之一。
只有一个孩子的时候
回到本节问题。B和C都只有一个孩子。可是D挂在B的左下,G挂在C的右下:B只有左孩子,C只有右孩子。这两个结点的情况不一样。
把D换到B的右下,看看会怎样:
看成二叉树,是两棵。一棵里D是B的左孩子,另一棵里D是B的右孩子。左右不同,就是两棵不同的二叉树。
看成有序树,是同一棵。4.1节的有序树,孩子只分先后。B只有一个孩子,D就是它的第一个孩子,没有左右可说。这两棵画成有序树,一模一样。
所以在二叉树里,只有一个孩子时,也要说清它是左孩子还是右孩子。空着的那一边,也是这棵二叉树的一部分。
程序为什么在乎:存二叉树时,每个结点要留出左、右两个位置。D放进哪个位置,存下来的就是哪一棵。
二叉树和度为2的有序树
二叉树的每个结点最多两个孩子。度为2的有序树,每个结点也最多两个孩子,孩子也有先后。它们是不是一回事?
不是。差在两点:
二叉树可以没有度为2的结点。树的度是2,说明至少有一个结点有两个孩子,所以至少有3个结点。二叉树没有这个要求。它可以是空的,可以只有一个根,也可以排成一条链。
只有一个孩子时,二叉树也分左右。有序树的先后,是两个孩子互相比出来的。只有一个孩子时,没得比,它就是第一个孩子。二叉树的左右是两个固定的位置,一个孩子也要放进其中一个。
二叉树:左孩子二叉树:右孩子有序树:第一个孩子
所以,二叉树不是度为2的有序树。它是另一种树:每个孩子都有定好的位置,不是左,就是右。
至于有三个以上孩子的结点,二叉树里没有。4.1节文件夹树里的"文档"有4个孩子,那棵树就不是二叉树。