树怎样转成二叉树?关于二叉树的公式有哪些?如题.最好详细些.关于二叉树的公式最基本的就可以,不要推导过程也行.

Question

树怎样转成二叉树?关于二叉树的公式有哪些?
如题.
最好详细些.
关于二叉树的公式最基本的就可以,不要推导过程也行.

Answer 1

树与二叉树
树是一种简单的非线性结构,所有元素之间具有明显的层次特性.
在树结构中,每一个结点只有一个前件,称为父结点,没有前件的结点只有一个,称为树的根结点,简称树的根.每一个结点可以有多个后件,称为该结点的子结点.没有后件的结点称为叶子结点.
在树结构中,一个结点所拥有的后件的个数称为该结点的度,所有结点中最大的度称为树的度.树的最大层次称为树的深度.
二叉树的特点：（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)；
②若2k≤n,则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（也无右子结点）；
③若2k+1≤n,则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点.
满二叉树是指除最后一层外,每一层上的所有结点有两个子结点,则k层上有2k-1个结点深度为m的满二叉树有2m-1个结点.
完全二叉树是指除最后一层外,每一层上的结点数均达到最大值,在最后一层上只缺少右边的若干结点.
二叉树存储结构采用链式存储结构,对于满二叉树与完全二叉树可以按层序进行顺序存储.
二叉树的遍历：
（1）前序遍历（DLR）,首先访问根结点,然后遍历左子树,最后遍历右子树；
（2）中序遍历（LDR）,首先遍历左子树,然后访问根结点,最后遍历右子树；
（3）后序遍历（LRD）首先遍历左子树,然后访问遍历右子树,最后访问根结点.