数据结构 二叉树的定义和性质 C语言_什么是左子树和右子树

原创作者：小林
1.二叉树的定义：

二叉树是每个结点最多有两个子树的树结构

1

根节点：一棵树最上面的节点称为根节点。
左右子树：某个节点的左分支叫做左子树，右分支叫做右子树。
左右孩子：某个节点的左、右分支的根节点叫做该节点的左、右孩子。
兄弟节点：具有相同父节点的节点互为兄弟节点。
节点的度：节点拥有的子树数。
叶子节点：没有任何子节点的节点称为叶子节点。
内部节点：非叶子节点称为内部节点。
根的层次：从根节点开始定义，根为第一层，根的孩子为第二层，如此计数，直到该结点为止。
树的深度和高度：二叉树中节点的最大层次称为二叉树的深度或高度。

1

2.二叉树的性质：
二叉树具有以下五个性质：

1. 二叉树的第ｉ（ｉ>=１）层最多有２＾(ｉ - １)个结点。

2. 深度为k的二叉树最少有k个结点，最多有 （２＾ｋ）－１ （k>=1）个结点。

最多的情况：
.
最少的情况：

3. 二叉树T叶子结点总数为n0，度为2的结点个数为n2，则**n0=n2+1**

（提示）叶子节点：
就是没有子节点的节点
1
2
3
4
5

（尽量背下来 如果不搞算法研究）

这张绿色图片就是证明过程

4. 具有n个结点的完全二叉树的深度为（log(2，ｎ+1)）

5：对于含n个节点的完全二叉树中编号为 i 的节点：
如果i=1，则i节点是这可完全二叉树的根，没有双亲，否则其双亲的编号为i的一半。

如果2i>n，则i节点没有左孩子，否则其左孩子的编号为2i。

如果2i+1>n,则i节点没有右孩子，否则其有孩子的编号为2i+1。

以上为C语言数据结构 二叉树的定义和性质