设一棵二叉树的中序遍历结果为ABCDEFG，前序遍历结果为DBACFEG，则后序遍历结果为 【1】 。
参考答案：ACBEGFD
解析： 由于在前序遍历中首先访问根结点，因此，前序序列中的第一个结点为二叉树的根结点，即D为二叉树的根结点。又由于在中序遍历中访问根结点的次序为居中，而访问左于树上的结点为居先，访问右子树上的结点为最后，因此，在中序序列中，以根结点(D)为分界线，前面的子序列(ABC)一定在左子树中，后面的子序列(EFG)一定在右于树中。同样的道理，对于已经划分出的每一个子序列的所有结点中，位于前序序列最前面的一个结点为子树的根结点，而在中序序列中位于该根结点前面的结点构成左子树上的结点子序列，位于该根结点后面的结点构成右子树上的结点子序列。这个处理过程直到所有子序列为空为止。
根据上述道理，该二叉树恢复的过程如下图所示；
[*]
根据后序遍历的方法，对该二叉树后序遍历的结果为ACBEGFD。
Text 2
| The Boston Marathon is an annual marathon sporting event hosted by the city of Boston, Massachusetts, on Patriots’ Day, the third Monday of April. Begun in 1897 and inspired by the success of the first modem-day marathon competition in the 1896 Summer Olympics, the Boston Marathon is the world’s oldest annual marathon and ranks as one of the world’s most well-known road racing events. The marathon is one of five members of the World Marathon Majors. The event attracts an average of about 20,000 registered participants each year. In the 100th running of the Boston Marathon in 1996, the number of participants reached 38,000. While there are cash prizes awarded to the winners of the marathon, most of the runners participate for the accomplishment of having run the race at all. The Boston Marathon was originally a local event, but its fame and status have attracted runners from all over the world. For most of its history, the Boston Marathon was a free event, and the only prize awarded for winning the race was a wreath woven from olive branches. However, corporate-sponsored cash prizes began to be awarded in the 1980s, when professional athletes began to refuse to run the race without cash awards. The first cash prize for winning the marathon was awarded in 1986. Women were not allowed to enter the Boston Marathon officially until 1972. Roberta (Bobbi) Gibb is recognized as the first woman to run the entire Boston Marathon (in 1966). In 1967, Kathrine Switzer, who had registered as "K. V. Switzer", was the first woman to run with a race number. She finished, despite a celebrated incident in which race official Jock Semple tried to rip off her numbers and eject her from the race. In 1996 the B.A.A. retroactively recognized as champions the unofficial women’s leaders of 1966 through 1971. In recent years, critics have pointed to the dominance of foreign-born athletes in the event (especially runners from Kenya) to back their arguments that American professional running is lagging behind the rest of the world in terms of producing quality athletes. However, foreign dominance of the race is nothing new. Between 1946 and 1967 only one American (John J. Kelley in 1957) won the marathon in an era when Finland and Japan were the distance powerhouses. The Boston marathon is open to all runners, male and female, from any nation, but they must meet certain qualifying standards. To qualify, a runner must first complete a standard marathon course certified by a national governing body affiliated with the International Association of Athletics Federations within a certain period of time before the date of the desired Boston Marathon (usually within approximately 18 months prior). Prospective runners in the age range of 18-- 34 must run a time of no more than 3:10:59 (3 hours and 10 minutes) if male, or 3:40:59 (3 hours and 40 minutes) if female; the qualifying time is adjusted upward as age increases. For example, a 40--44 year old male can still qualify with a time of 3:20:59. An exception to the qualification requirement is awarded to 1,250 runners who raise a pre-determined level of sponsorship for officially designated local charities. Besides the Olympic trials and the Olympic marathons, Boston is the only major American marathon that requires a qualifying time. Thus for many marathoners to qualify for Boston (to "BQ") is a goal and achievement in itself, making it a "people’s Olympic event." |
Who can participate the Boston Marathon without a qualifying time
A．Male runners.
B．Female runners.
C．Amateur runners.
D．Charity raisers.