特性：
- 如左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)均小于根結(jié)點(diǎn)的值
- 如右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)均大于根結(jié)點(diǎn)的值
- 左右子樹(shù)也分別是二叉查找樹(shù)
由上面3個(gè)特性可知：二叉查找樹(shù)中結(jié)點(diǎn)的值不允許重復(fù),它的中序遍歷序列是有序的。
1. 判別二叉樹(shù)T是否為二叉排序樹(shù)
二叉排序樹(shù)的類型BSTree定義如下：
typedef struct {
KeyType key;
... ... // 其他數(shù)據(jù)域
} TElemType;
typedef struct BSTNode {
TElemType data;
struct BSTNode *lchild,*rchild;
}BSTNode, *BSTree;
根據(jù)二叉排序樹(shù)特性，寫出算法
// 若是二叉排序樹(shù)，則返回TRUE，否則FALSE
Status IsBSTree(BSTree T)
{
if(T==NULL) return TRUE;
//左子樹(shù),右子樹(shù),左孩子,右孩子
Status bLeft,bRight,bChildL,bChildR;
bLeft=bRight=bChildL=bChildR=FALSE;
if(T->lchild==NULL || T->lchild->data.key<T->data.key){
bChildL=TRUE;
}
if(T->rchild==NULL || T->rchild->data.key>T->data.key){
bChildL=TRUE;
}
bLeft=IsBSTree(T->lchild);
bRight=IsBSTree(T->rchild);
return bLeft && bRight && bChildL && bChildR;
}
2. 遞歸算法，從大到小輸出給定二叉排序樹(shù)
二叉排序樹(shù)的類型BSTree定義如下：
typedef struct {
KeyType key;
... ... // 其他數(shù)據(jù)域
} TElemType;
typedef struct BSTNode {
TElemType data;
struct BSTNode *lchild,*rchild;
}BSTNode, *BSTree;
分析：因?yàn)槎媾判驑?shù)的中序遍歷是從小到大排列的,所以只需要中序排序逆過(guò)來(lái)就是從大到小排序的(右->根->左)
// 調(diào)用visit(T->data)輸出
void OrderOut(BSTree T, KeyType k, void(*visit)(TElemType))
{
if(T==NULL) return;
OrderOut(T->rchild,k,visit);
visit(T->data);
else return;
OrderOut(T->lchild,k,visit);
}
3. 輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是否是一棵二叉查找樹(shù)的后序遍歷序列
二叉排序樹(shù)的定義如下：
class TreeNode {
int value;
TreeNode left;
TreeNode right;
}
分析：
from: 玉剛說(shuō)
由特性知：左子樹(shù)結(jié)點(diǎn)< 根結(jié)點(diǎn) < 右子樹(shù)結(jié)點(diǎn)，所以
后續(xù)遍歷根結(jié)點(diǎn)肯定在最后。
- 數(shù)組中最后一個(gè)元素10是根結(jié)點(diǎn)
- 10之前，比10小的元素都是10的左子樹(shù)（3~8）
- 10之前，比10大的元素都是10的右子樹(shù)（12~13）
- 左子樹(shù)與5同理（右子樹(shù)比較短，比較容易分析哈哈），一直遞歸遍歷下去
- 右子樹(shù)（12~13）中13排最后，那么13是根結(jié)點(diǎn)；12<13，是13的左子樹(shù)；15>13是右子樹(shù)
由分析可知：根結(jié)點(diǎn)之前的數(shù)組元素，分為兩部分：連續(xù)的元素比根結(jié)點(diǎn)小是左子樹(shù)，連續(xù)的元素比根結(jié)點(diǎn)大是右子樹(shù)。
那么從array[0]開(kāi)始往后遍歷，當(dāng)數(shù)組元素開(kāi)始大于根結(jié)點(diǎn)時(shí)（array[x]大于根結(jié)點(diǎn)），可以把根結(jié)點(diǎn)（array[root]）之前元素分為兩部分：array[0] ~ array[x-1]為左子樹(shù)，array[x]~array[root-1]為右子樹(shù)，它們都必須大于array[root]。如果滿足條件，證明：對(duì)于這個(gè)結(jié)點(diǎn)來(lái)說(shuō)，它的左右子樹(shù)是滿足二叉查找樹(shù)特性的。接下來(lái)就遞歸遍歷左子樹(shù)和右子樹(shù)，當(dāng)所有的非葉子結(jié)點(diǎn)都滿足以上條件時(shí)，證明這個(gè)二叉樹(shù)是二叉查找樹(shù)。
算法：
boolean isPostOrderArrayOfBST(int[] array, int start, int end) {
if (array == null || start < 0 || end > array.length || start >= end) {
return false;
}
int root = array[end - 1];
int i = start;
for (; i < end - 1; i++) {
if(array[i] > root) {
break;
}
}
int j = i; // j開(kāi)始就是右子樹(shù)了
for (; j < end - 1; j++) {
if (array[j] < root) {
return false;
}
}
boolean left = true;
if (i > 0) {
left = isPostOrderArrayBST(array, start, i);
}
boolean right = true;
if (i < end - 1) {
right = isPostOrderArrayBST(array, i, end - 1);
}
return left && right;
}
對(duì)于這道題目，如果改為判斷是否為一棵二叉查找樹(shù)的先序遍歷序列，我們也可以用同樣的思路去解，只不過(guò)如果是先序遍歷序列，則數(shù)組的第一個(gè)元素為根節(jié)點(diǎn)的值，但后面的數(shù)組仍可分為兩部分并分別代表左右子樹(shù)。
4. 將二叉搜索樹(shù)轉(zhuǎn)換成一個(gè)排序的雙向鏈表（要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只能調(diào)整樹(shù)中結(jié)點(diǎn)指針的指向）
二叉排序樹(shù)的定義如下：
class TreeNode {
int value;
TreeNode left;
TreeNode right;
}
該算法內(nèi)容均來(lái)自 FutureFlyme 的CSDN 博客 ，全文地址請(qǐng)點(diǎn)擊：
https://blog.csdn.net/FutureFlyme/article/details/69937007?utm_source=copy
分析：
1. 將左子樹(shù)構(gòu)成雙鏈表，并返回該鏈表的頭節(jié)點(diǎn)(左子樹(shù)最左邊的節(jié)點(diǎn))
2. 定位到左鏈表的最后一個(gè)節(jié)點(diǎn)(左子樹(shù)最右邊的節(jié)點(diǎn))
3. 如果左子樹(shù)鏈表不為空，則將當(dāng)前root追加到左子樹(shù)鏈表后
4. 將右子樹(shù)構(gòu)造成雙向鏈表，并返回鏈表頭結(jié)點(diǎn)(右子樹(shù)最左邊的節(jié)點(diǎn))
5. 如果右子樹(shù)鏈表不為空，將右子樹(shù)鏈表追加到當(dāng)前root后
6. 根據(jù)左子樹(shù)鏈表是否為空返回的整體雙向鏈表的頭節(jié)點(diǎn)
4.1 遞歸實(shí)現(xiàn)
//Convert函數(shù)把一個(gè)二叉搜索樹(shù)變成一個(gè)有序的雙向鏈表，返回雙向鏈表的頭結(jié)點(diǎn)，參數(shù)root為二叉搜索樹(shù)的根節(jié)點(diǎn)
public TreeNode Convert(TreeNode root){
if(root==null){//假如根節(jié)點(diǎn)為空，返回空
return null;
}
if(root.left==null&&root.right==null){//假如只有一個(gè)根節(jié)點(diǎn)，則返回根節(jié)點(diǎn)
return root;
}
//1、將左子樹(shù)構(gòu)造成雙鏈表，并返回該鏈表頭結(jié)點(diǎn)left
TreeNode left=Convert(root.left);
//2、定位到左子樹(shù)鏈表的最后一個(gè)節(jié)點(diǎn)（左子樹(shù)最右邊的節(jié)點(diǎn)）
TreeNode p=left;//創(chuàng)建一個(gè)臨時(shí)節(jié)點(diǎn)P,用來(lái)遍歷找到左鏈表的最后一個(gè)節(jié)點(diǎn)(左子樹(shù)最右邊的節(jié)點(diǎn))，p初始化指向做左子樹(shù)的根節(jié)點(diǎn)，
while(p!=null&&p.right!=null){
p=p.right;//最終p為左子樹(shù)最右邊的節(jié)點(diǎn)
}
//3、如果左子樹(shù)鏈表不為空，將當(dāng)前root追加到左子樹(shù)鏈表后
if(left!=null){//左子樹(shù)鏈表不為空
p.right=root;//左子樹(shù)鏈表的最后一個(gè)節(jié)點(diǎn)p（左子樹(shù)最右邊節(jié)點(diǎn)）的右指針指向當(dāng)前root節(jié)點(diǎn)
root.left=p;//當(dāng)前root節(jié)點(diǎn)的左指針指向左子樹(shù)鏈表的最后一個(gè)節(jié)點(diǎn)p（左子樹(shù)最右邊節(jié)點(diǎn)）
}
//4、將右子樹(shù)構(gòu)造成雙鏈表，并返回該鏈表的頭結(jié)點(diǎn)right
TreeNode right=Convert(root.right);
//5、如果右子樹(shù)鏈表不為空，將右子樹(shù)鏈表追加到當(dāng)前root后
if(right!=null){//右子樹(shù)鏈表不為空
right.left=root;//右子樹(shù)鏈表的頭結(jié)點(diǎn)right的左指針指向當(dāng)前root
root.right=right;//當(dāng)前root的右指針指向右子樹(shù)鏈表的頭結(jié)點(diǎn)right
}
return left!=null?left:root;//根據(jù)左子樹(shù)鏈表是否為空返回整個(gè)雙向鏈表的頭指針。
}
4.2 借助Stack，非遞歸實(shí)現(xiàn)
import java.util.Stack;
public TreeNode ConvertBSTToBiList(TreeNode root){
if(root==null){
return null;
}
Stack<TreeNode> stack=new Stack<TreeNode>();
TreeNode p=root;//p為臨時(shí)節(jié)點(diǎn)用來(lái)遍歷樹(shù)的節(jié)點(diǎn)，初始值為根節(jié)點(diǎn)root
TreeNode rootList=null;//用于記錄雙向鏈表的頭結(jié)點(diǎn)
TreeNode pre=null;//用于保存中序遍歷序列的上一個(gè)節(jié)點(diǎn)，即p的上一個(gè)節(jié)點(diǎn)
boolean isFirst=true;//判斷是否為左子樹(shù)鏈表的第一個(gè)節(jié)點(diǎn)
while(p!=null||!stack.isEmpty()){
while(p!=null){
stack.push(p);
p=p.left;
}
p=stack.pop();//此時(shí)的p為左子樹(shù)最左邊的節(jié)點(diǎn)，
if(isFirst){//假如是左子樹(shù)鏈表的第一個(gè)節(jié)點(diǎn)
rootList=p;//將p賦值給root節(jié)點(diǎn)
pre=rootList;
isFirst=false;
}else{
pre.right=p;
p.left=pre;
pre=p;
}
p=p.right;
}
return rootList;
}
5. 找出二叉查找樹(shù)中第K大的值
二叉排序樹(shù)的定義如下：
class TreeNode {
int value;
TreeNode left;
TreeNode right;
}
分析：因?yàn)槎媾判驑?shù)的中序遍歷是從小到大排列的,所以只需要中序排序逆過(guò)來(lái)就是從大到小排序的(右->根->左)
算法如下：
public TreeNode findKthBigNode(TreeNode root ,int k){
if(root==null) { return null;}
if(root.right!=null){ findKthBigNode(root.right,k); }
k--; //減一表示訪問(wèn)了這個(gè)點(diǎn)
if(k==0) return root; //當(dāng)k==0時(shí)，說(shuō)明已經(jīng)訪問(wèn)了k個(gè)點(diǎn)，剩余0個(gè)點(diǎn)。該Node為第k大
if(root.right!=null){ findKthBigNode(root.left,k); }
}
6. 非遞歸往二叉排序樹(shù)插入元素
/**********
【題目】試寫一非遞歸算法，在二叉查找樹(shù)T中插入元素e。
二叉查找樹(shù)的類型BSTree定義如下：
typedef struct {
KeyType key;
... ... // 其他數(shù)據(jù)域
} TElemType;
typedef struct BSTNode {
TElemType data;
struct BSTNode *lchild,*rchild;
} BSTNode, *BSTree;
**********/
BSTree SearchInsertPosition(BSTree T, TElemType k)
{
BSTNode *pos, *p;
p = T;
while (p)
{
pos = p;
if (p->data.key == k.key)
return NULL;
p = (k.key < p->data.key) ? p->lchild : p->rchild;
}
return pos;
}
Status InsertBST_I(BSTree &T, TElemType k)
/* 在二叉查找樹(shù)T中插入元素e的非遞歸算法 */
{
BSTNode *new, *p;
new = (BSTNode*)malloc(sizeof(BSTNode));
if (!new)
return OVERFLOW;
new->data = k;
new->lchild = new->rchild = NULL;
if (!T)
T = new;
else
{
p = SearchInsertPosition(T, k);
if (!p)
{
free(new);
return FALSE;
}
if (k.key < p->data.key)
p->lchild = new;
else
p->rchild = new;
}
return TRUE;
}
----------------------------------------------------------------------
/* 這個(gè)方法沒(méi)實(shí)現(xiàn)功能
Status InsertBST_I(BSTree &T, TElemType k)
{
BSTree p=T;
while(1){
if(NULL==p){
BSTree s;
s=(BSTNode*)malloc(sizeof(BSTNode));
if(NULL==s) return OVERFLOW;
s->data=k; s->lchild=NULL; s->rchild=NULL;
p=s;
return TRUE;
}
if(k.key < p->data.key) {p=p->lchild ; continue;}
else if(k.key > p->data.key) {p=p->rchild; continue;}
else return FALSE;//k.key==p->data.key
}
} */
