第三部分 樹與二叉樹[8]

    （四）樹與二叉樹的應用
　　
　　二叉排序樹
　　
　　定義
　　二叉排序樹（也稱二叉查找樹）或者是一棵空的二叉樹或者是具有下列性質的二叉樹
　　
　　（）若它的左子樹不空則左子樹上所有結點的值均小於根結點的值
　　
　　（）若它的右子樹不空則右子樹上所有結點的值均大於根結點的值
　　
　　（）它的左右子樹也都是二叉排序樹
　　
　　【記】左小於右（左子樹<根<右子樹）
　　
　　二叉排序樹刪除結點
　　被刪除的結點是葉子
　　被刪除的結點只有左子樹或者只有右子樹
　　被刪除的結點既有左子樹也有右子樹
　　
　　平衡二叉樹
　　
　　平衡二叉樹或者是一棵空的二叉排序樹或者是具有下列性質的二叉排序樹
　　
　　（）根結點的左子樹和右子樹的深度最多相差;
　　
　　（）根結點的左子樹和右子樹也都是平衡二叉樹
　　
　　【記】左右高（最）多差一

    返回《數據結構》考研復習精編

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

From:http://tw.wingwit.com/Article/program/sjjg/201311/23659.html