數據結構考研分類復習真題 第九章 集合[47]

　　 設二叉排序樹的存儲結構為

　　TYPE tree=^node;
　　node=RECORD
　　key: keytype;
　　size:int;
　　lchild rchild parents: tree;
　　END;

　　一個結點x^的size域的值是以該結點為根的子樹中結點的總數(包括x^本身)例如下圖中x所指結點的sixe值為設樹高為h試寫一時間為O(h)的算法Rank(T:tree;x:^node)返回x所指結點在二叉排序樹T的中序序列裡的排序序號即求x^結點是根為T的二叉排序樹中第幾個最小元素例如下圖x所指結點是樹T中第個最小元素(提示你可利用size值和雙親指針parents)【中科院軟件所 四(分)】【中國科學技術大學 】

[]  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []