以二叉链表作为二叉树的储存结构,在具有n个结点的二叉链表中n(n>0),空链域的个数为n+1。
二叉链表结构描述:
typedef struct CSNode{
ElemType data;
struct CSNode *firstchild , *netsibling;
} CSNode,* CSTree;
由于二叉树的存储结构比较简单,处理起来也比较方便,所以有时需要把复杂的树,转换为简单的二叉树后再作处理。
扩展资料:
二叉树类型:
1、完全二叉树——若设二叉树的高度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第h层有叶子结点,并且叶子结点都是从左到右依次排布,这就是完全二叉树。
2、满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
3、平衡二叉树——平衡二叉树又被称为AVL树(区别于AVL算法),它是一棵二叉排序树,且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。
n个结点的二叉树二叉链表中有n+1个空链域,三叉链表中有n个(多了一个根结点中的空链域)
二叉树的度表示节点的子树或直接继承者的数目,二叉树的度是一个子树或单子树。2度是两个孩子,或者左和右子树有两个叉树,最大度数为2。
一棵深度为k,且有2^k-1个节点的二叉树,称为满二叉树。这种树的特点是每一层上的节点数都是最大节点数。而在一棵二叉树中,除最后一层外,若其余层都是满的,并且最后一层或者是满的,或者是在右边缺少连续若干节点,则此二叉树为完全二叉树。
具有n个节点的完全二叉树的深度为floor(log2n)+1。深度为k的完全二叉树,至少有2k-1个节点,至多有2k-1个节点。
本回答被网友采纳