摘要:
1,二叉树的介绍
2,树的常见术语
3,二叉树的特性
1,二叉树的介绍
二叉树(Binary tree)是每个节点最多只有两个分支(即不存在分支度大于 2 的节点)的树结构,两个分支分别是左子树和右子树。除了根节点以外每个节点有且只有一个父节点,其中根节点没有父节点。
二叉树的种类非常多,根据不同的特性分为二叉搜索树,AVL树,红黑树,笛卡尔树,二叉堆,线段树,哈夫曼树等。
二叉树的节点可以为空,如果节点为空,就是空的二叉树。在一颗非空树中,如果度为 0 的节点(叶子节点)个数为 a ,度为 1 的节点个数为 b ,度为 2 的节点个数为 c ,我们可以找到他们的对应关系:
1,总的节点个数就是:a+b+c。
2,边的个数 e 就是:b+2*c。
3,总的节点个数又等于边的个数加 1 :e+1。
4,由边的个数相等可以得到:a+b+c=b+2*c+1,整理一下就是 a = c + 1 。
也就是说在任何二叉树中叶子节点的个数都等于度为 2 的节点个数加 1 ,这在很多笔试中经常考到。
下面我们来分析一下,度为 2 的节点指向两个子节点,也就是说一个度为 2 的节点贡献的边数是 2 ,一个度为 1 的节点贡献的边数是 1 ,度为 0 的节点贡献的边数是 0 ,所以一颗二叉树中总的边数就是:度为 2 的节点个数*2+度为 1 的节点个数。
又因为一条边只能指向一个节点,而根节点是没有边指向它的,所以在二叉树中:边的个数+1=总的节点个数。