叉树节点计算法方法

1．6 树与二叉树树是一种简单的非线性结构，所有元素之间具有明显的层次特性。在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件

1．6树与二叉树 树是一种简单的非线性结构，所有元素之间具有明显的层次特性。 在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结 点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个 后件，称为该结点的子结点。没有后件的结点称为叶子结点。 在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结 点中最大的度称为树的度。树的最大层次称为树的深度。 （1）非空二叉树只有一个根结点；（2）每一个结 二叉树的特点： 点最多有两棵子树，且分别称为该结点的左子树与右子树。 二叉树的基本性质： （1）在二叉树的第k层上，最多有2k-1(k≥1)个结点； （2）深度为m的二叉树最多有2m-1个结点； （3）度为0的结点（即叶子结点）总是比度为2的结点多一个； （4）具有n个结点的二叉树，其深度至少为[log2n]+1,其中[log2n] 表示取log2n的整数部分； （5）具有n个结点的完全二叉树的深度为[log2n]+1； （6）设完全二叉树共有n个结点。如果从根结点开始，按层序（每 一层从左到右）用自然数1，2，….n给结点进行编号（k=1,2….n）， 有以下结论： ①若k=1，则该结点为根结点，它没有父结点；若k>1，则该结点 的父结点编号为INT(k/2)；