algorithm mirror

2008-07-28 7:31 pm
there is a binary tree T(T points to the root of the tree) and write an algorithm to convert T to its mirror image. (optional, what is the complexity of your algorithm, prove it.)

回答 (1)

2008-07-30 9:11 am
✔ 最佳答案

Algorithm

Mirror-Binary-Tree(T)
1 if T =/= nil then
2 T.Left = Mirror-Binary-Tree(T.Right)
3 T.Right= Mirror-Binary-Tree(T.Left)
4 return T


It take constant time C to process a node with no child.
T(1) = C.

For all other nodes, we have
T(n) = T(a) + T(n-1-a) + D, for all possible split of the tree, with a nodes on the left and n - 1 - a nodes on the right.

Let S(n) be the statement T(n) = O(n).
S(1) is true because T(1) = C = O(1).

Assume S(n) to be true for all n <= k.
For n = k+1, we have
T(n) = T(a) + T(n - 1 - a) + D = O(a) + O(n - 1 - a) + O(1) = O(n).

Therefore, by the principle of (strong) Mathematical Induction, the statement S(n) is true for all positive integer n.

Notice this running time is also the lower bound for this problem because you will need to produce the output (which has size n) anyway. Producing the output takes time proportional to the size of the tree = O(n).
參考: 從不抄襲。


收錄日期: 2021-04-14 19:27:54
原文連結 [永久失效]:
https://hk.answers.yahoo.com/question/index?qid=20080728000051KK00757

檢視 Wayback Machine 備份