二叉树及其储存结构

0x00 二叉树的定义

二叉树： 有穷的节点集合，可为空，若非空，则分为根节点和左子树和右子树，且不相交（递归定义）

一些特殊的二叉树

0x01 二叉树性质

1一个二叉树第i层的最大节点数为：2^(i-1),i>=1;

2深度为k的二叉树有最大节点总数为：2^k-1,k>=1;

3对于任何非空二叉树，如n0表示叶节点个数，n2表示度为2的节点个数，那么关系为n0=n2+1

原因 从上往下看 边的总数为：n1+2*n2,从下往上看为：n0+n1+n2-1,两者相等，故 n0=n2+1

二叉树的抽象数据类型定义

0x02 二叉树的实现

1顺序储存结构，对于完全二叉树，按从上往下，从左往右进行编号，储存在数组里

一般二叉树也可以这么存，但是由于空缺节点的存在，会产生空间浪费。

2链表储存