二叉树的定义

2024-11-01 03:37:56
推荐回答(1个)
回答(1):

二叉树(Binary Tree)是n(n>=0)个数据元素的有限集合,该集合可以为空(空二叉树),也可以由一个称为根(root)的元素及两个不相交的,被分别称为左子树和右子树的二叉树组成。

如下图中含有7个结点,其中A是根节点,左子树TL由{B,D,E}构成,右子树TR由{C,F,G}构成;而左子树TL中B是根结点,左子树是{D},右子树是{E}。

右子树TR中,C是根结点,左子树为空,右子树为{F,G};以此类推。由上述可以看出在二叉树中用到了递归的概念。即用二叉树来定义二叉树。

二叉树的性质

1、一颗非空二叉树的第i层上最多有2^(i-1)个结点(i>=1)。

2、一颗深度为k的二叉树中,最多有2^k-1个结点。

3、对于一颗非空二叉树,如果叶结点数为n0,度数为2的结点数为n2,则有n0=n2+1。

4、具有n个结点的完全二叉树的深度为 |lbn|+1。

5、对于具有n个结点的完全二叉树,如果按照从上到下和从左到右的顺序对二叉树中所有结点从1开始编号,则对于任意序号结点来说,有:

①如果i>1,则序号i的结点的双亲结点序号为i/2;如果i=1,则此时结点为根结点,无双亲结点。②如果2i<=n,则序号为i的结点的左孩子为2i;若2i>n,则序号为i的结点无左孩子。③如果2i+1<=n,则序号为i的结点的右孩子为2i+1;如果2i+1>n,则序号为i的结点无右孩子。