Skip to content
第4章

4.5 二叉树 ​

什么是二叉树 ​

4.1节的树,一个结点可以有任意多个孩子。这一节看一种更规整的树:每个结点最多两个孩子,而且两个孩子分左右。这样的树叫二叉树。

它的定义也是递归的。二叉树是n个结点的有限集合。n等于0时,叫空二叉树。n大于0时,它由一个根和两棵互不相交的二叉树组成,这两棵分别叫根的左子树和右子树。

把定义代入一棵具体的二叉树。这一节一直用它:

根。这棵二叉树有5个结点,不是空的,所以有一个根,就是A。图里的虚线框,是空着的位置。

ABDCG

左子树。A的左下挂着B和D。它们合起来,是A的左子树。

ABDCG

右子树。A的右下挂着C和G,是A的右子树。两棵子树没有共同的结点。

ABDCG

子树又是二叉树。A的左子树,根是B。B的左子树只有D,右子树是空的。D的两棵子树也是空的。一层一层往下拆,最后都拆到空二叉树。

BD
本节问题
B只有一个孩子D,C也只有一个孩子G。这两个结点的情况一样吗?

学完这一节,你能判断什么样的数据可以看成二叉树,分清左孩子和右孩子,说出一棵二叉树是哪种形态。

选中正文里的任意文字,就可以针对它发表评论