二叉树的顺序存储关键在于理清父子节点与下标之间的关系。
#define MAXSIZE 100 template <typename T> class ArrayTree { public: ArrayTree() { count = 0; } void Init(int data[],int len)//构造完全二叉树。 { if (len > MAXSIZE) { count = MAXSIZE; } else { count = len; } for (int i=1;i <= count;i++)//为了方便计算,从1开始 { value[i] = data[i]; } } int getLeftChild(int pos) { if (pos > count) { //节点不存在。 return -1; } if (pos*2 > count) { //节点没有左孩子。 return -1; } else return pos*2; } int getRightChild(int pos) { if (pos > count) { return -1; } if (pos*2+1 > count) { return -1; } else return pos*2 + 1; } int getParent(int pos) { if (pos < 1 || pos > count) { return -1; } if (pos == 1) { return -1; } return pos/2; } void PreOrder(int root)//先序遍历 { if (isEmpty()) { return ; } if (root < 1 && root > count) { //不存在的点 return; } else { printf("%d\t",value[root]); if (getLeftChild(root) != -1) { PreOrder(getLeftChild(root)); } if (getRightChild(root) != -1) { PreOrder(getRightChild(root)); } } } bool isEmpty() { if (count == 0) { return true; } else { return false; } } private: int count; int value[MAXSIZE]; };
int main() { ArrayTree<int> atree; int a[11]={0,18,24,32,5,6,7,8,9,10,11}; atree.Init(a,10);//取a[1]-a[10] atree.PreOrder(1); }
实验结果: