首先要了解什么是搜索二叉樹(或者界查找二叉樹):
它或者是一棵空樹,或者是具有下列性質(zhì)的二叉樹: 若它的左子樹不空伙狐,則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值; 若它的右子樹不空曼玩,則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值鳞骤; 它的左、右子樹也分別為二叉排序樹黍判。
給出兩種解法。
第一種比較巧妙篙梢,在中序遍歷的過程中不斷查找是否有節(jié)點的值異常(所謂異常就是因為搜索二叉樹的值永遠(yuǎn)是:左子樹<根<右子樹顷帖,找到不符合這樣情況的節(jié)點),分別存放到a,b中去渤滞,最后在互換過來贬墩。
第二種索性先把搜索二叉樹所有的節(jié)點按中序遍歷一遍放到容器中去,再直接將容器中的元素從小到大排序妄呕,一個For循環(huán)創(chuàng)建容器中元素個數(shù)的節(jié)點陶舞,每個節(jié)點的值都對應(yīng)著容器中的元素值。