二叉树的存储方式

二叉树的存储方式分为两种，一个是顺序存储，一个是链表存储

顺序存储：数组方式存储，表现上是一个一维数组，逻辑上是一颗二叉树

链表存储：采用链表的方式进行存储，链表包含逻辑关系，左指针，右指针。从表现到逻辑都是一颗二叉树。

二叉树一般可以使用两种结构存储,一种顺序结构,一种链式结构、

2.

顺序存储: 完全二叉树和满二叉树是可以通过顺序表来存储的,这是因为他们两种二叉树有一个特点,即,从根节点开始,一层一层的按照顺序依次放进顺

1。对于完全二叉树就用数组表示法，结点i的左孩子为2*i，右孩子为2*i+1，双亲为i/2

2。双亲数组表示法。这个我没用过，大概是对每个结点记录其双亲，但是结点不一定是连续的，比如：

结点

双亲

1

0

4

1

3

4

5

2

2

1

嘛，这个只是从底向上的遍历比较简单，所以一般不用

3。孩子链表表示法

对于每个结点给予两个指针域分别指向其左孩子，右孩子，若指针域为空则表示没有这边的孩子。

详细的实现比较长懒的写了，随便找点资料好了。

基础的就这三种，一般用到的也是这样，其他也就是没有大改动只是加入一些域什么的而已。。。

以上纯手打

---