计算机vB中的二叉树

发布网友发布时间：2022-05-04 15:19

共1个回答

热心网友时间：2022-06-23 12:42

二叉树是个有限元素的集合，该集合或者为空，或者由一个称为“根”的元素及两个不相交的，被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称为也称做一个结点。（笔者认为，二叉树可以理解为每一个点最多分成两个叉的树或空树是二叉树，如果有一个分支在三个以上就不是了。）二叉树每一个结点的度最大为2.二叉树是树结构的一种，在树的结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称为树的根。在树的图形表示中，总是认为在用直线连起来的两端结点中，上端结点是前件，下端结点是后件。在树的结构中，每一个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点。在树的结构中，一个结点所拥有的后件个数称为该结点的度，在树中，所有结点中最大的度称为树的度。
如图所示的二叉树中ABCDEFG为树的结点，其中A为根结点，BDE为子结点，CGF为叶子结点根结点A度为1 （只有B一个结点）
结点B、D度均为2（有两个结点C、D和E、F），因此树的度为2 二叉树的计算（性质）：(1)
在二叉树中，第i层的结点总数不超过2^(i-1)；
　　(2)
深度为h的二叉树最多有2^（h+1）-1个结点(h>=1)，最少有h个结点；
　　(3)
对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，
　　则N0=N2+1；
　　(4)
具有n个结点的完全二叉树的深度为int（log2n）+1
　　(5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：
　　若I为结点编号则
如果I<>1，则其父结点的编号为I/2；
　　如果2*I<=N，则其左结点（即左子树的根结点）的编号为2*I；若2*I>N，则无左子树；
　　如果2*I+1<=N，则其右子树的结点编号为2*I+1；若2*I+1>N，则无右子树。
　　(6)给定N个节点，能构成h(N)种不同的二叉树。
　　h(N)为卡特兰数的第N项。h(n)=C(n,2*n)/(n+1)。