定理6.1当输入的树T有n≥0个结点时，设t(n)和s(n)分别表示这些 周游算法中的任意一个算法所需要的最大时间和空间。如果访问一个 结点所需要的时间和空间是⊙(1)，则t(n)=⊙(n),s(n)=⊙(n)。 证明： 时间：由于已知访问一个结点所需时间是⊙(1)，故可用常数c限界。 设T的左子树中的结点数是n1,则t(n)有： t (n)=maxni{t (n1)+t (n-n1-1)+ci}n>1 其中，t(0)≤c1 归纳法证明t(n)≤c2n+c1,其中c2是一使得c2≥2c1的常数。 1)当n=0时，成立 2)假定当n=0,1,…,m-1时均成立。则当n=m时有， 设T是一棵有m个结点的树，T左子树结点数为n1,则 t (n)=maxni{t (n1)+t(n-n1-1)+c1} <maxniic2n1+c1+c2(n-n1-1)+ci+c1} =maxn1ic2n+3c1-c2 ≤c2n+c1 同理，存在c'2和c'1有t(n)≥c'2n+c'1。所以t(n)=⊙(n) 空间：若T的深度为d,则所需空间为⊙(d),d≤n,所以s(n)=⑧(n)。定理6.1 当输入的树T有n≥0个结点时，设t(n)和s(n)分别表示这些 周游算法中的任意一个算法所需要的最大时间和空间。如果访问一个 结点所需要的时间和空间是Θ(1)，则t(n)=Θ(n), s(n)=Θ(n)。 证明： 时间:由于已知访问一个结点所需时间是Θ(1),故可用常数c1限界。 设T的左子树中的结点数是n1，则t(n)有： t(n)=maxn1{t(n1)+t(n-n1-1)+c1} n≥1 其中，t(0)≤c1。 归纳法证明t(n)≤c2n+c1，其中c2是一使得c2≥2c1的常数。 1)当n=0时，成立 2)假定当n=0,1,…,m-1时均成立。则当n=m时有， 设T是一棵有m个结点的树，T左子树结点数为n1,则 t(n)＝maxn1{t(n1)+t(n-n1-1)+c1} ≤maxn1{c2n1+c1+c2(n-n1-1)+c1+c1} ＝maxn1{c2n+3c1-c2} ≤c2n+c1 同理，存在c'2和c'1有t(n)≥c'2n+c'1。所以t(n)=Θ(n) 空间：若T的深度为d，则所需空间为Θ(d), d≤n，所以s(n)=Θ(n)