Question

一颗具有N个结点的完全二叉树以一维数组作为存储结构，试设计一个对该完全二叉树进行线序遍历的算法。

Answer 1

preorder (R) //先序遍历二叉树R

int R[n];

{ int root;

SqStack *s; //s为一个指针栈，类型为seqstack，其中包含top域和数组data

s->top= -1; //s栈置空

root=1;

while ((root<=n) && (s->top>-1))

{ while (root<=n)

{ printf(R[root]);

s->top++;

s->data[s->top]=root;

root=2*root;

}

if (s->top>-1) //栈非空访问，遍历右子树

{ root=s->data[s->top]*2+1;

s->top--;

}

}

}

Answer 2

完全二叉树有1000个结点，度为1的节点个数可能是0或1，若为0，则该题无解，所以显然不能为0了，若为1，则度为2的结点个数为499个，度为1的节点数为1，度为0的节点为500