一、完全二叉树的数组表示
1.使用数组表示完全二叉树:将数据从根结点开始存储,第0个位置存储为A,第1和第2个位置分别存储L和G,依次都是从左边开始存储。
2.数组存储方便的原因
1)根结点总是出现在数组0的位置。
2)假设一个非根结点的位置在数组中的第i个位置,那么它的双亲总在(i-1)/2的位置上。如:i=3,数据为O,(3-1)/2=1,双亲在数组中的1的位置,数据为L。
3)假设一个结点的数据在数组中的位置是i,那么它的孩子总是出现在下面的两个位置
左孩子在:2*i+1
右孩子在:2*i+2
二、完全二叉树的结点类表示
1.二叉树的每个结点可以看作一个二叉树结点类的对象存储,结点类包含指向书中其它结点的引用的私有实例变量。一个完整的树表示为根结点的引用。
2.一棵二叉树:每个结点含一个私有变量保存数据,指向自己左孩子和右孩子的两个引用。
class BTNode <E>{
private E data;
private BTNode<E> left;
private BTNode<E> right;
...
}
3.如图所示表示字符二叉树,斜线表示没有引用。
There is no such thing as a great talent without great will - power.——Balzac
没有伟大的意志力,便没有雄才大略。——巴尔扎克