特性：
- 如左子树不空，则左子树上所有结点均小于根结点的值
- 如右子树不空，则右子树上所有结点均大于根结点的值
- 左右子树也分别是二叉查找树
由上面3个特性可知：二叉查找树中结点的值不允许重复,它的中序遍历序列是有序的。
1. 判别二叉树T是否为二叉排序树
二叉排序树的类型BSTree定义如下：
typedef struct {
KeyType key;
... ... // 其他数据域
} TElemType;
typedef struct BSTNode {
TElemType data;
struct BSTNode *lchild,*rchild;
}BSTNode, *BSTree;
根据二叉排序树特性，写出算法
// 若是二叉排序树，则返回TRUE，否则FALSE
Status IsBSTree(BSTree T)
{
if(T==NULL) return TRUE;
//左子树,右子树,左孩子,右孩子
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. 递归算法，从大到小输出给定二叉排序树
二叉排序树的类型BSTree定义如下：
typedef struct {
KeyType key;
... ... // 其他数据域
} TElemType;
typedef struct BSTNode {
TElemType data;
struct BSTNode *lchild,*rchild;
}BSTNode, *BSTree;
分析：因为二叉排序树的中序遍历是从小到大排列的,所以只需要中序排序逆过来就是从大到小排序的(右->根->左)
// 调用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. 输入一个整数数组，判断该数组是否是一棵二叉查找树的后序遍历序列
二叉排序树的定义如下：
class TreeNode {
int value;
TreeNode left;
TreeNode right;
}
分析：
from: 玉刚说
由特性知：左子树结点< 根结点 < 右子树结点，所以
后续遍历根结点肯定在最后。
- 数组中最后一个元素10是根结点
- 10之前，比10小的元素都是10的左子树（3~8）
- 10之前，比10大的元素都是10的右子树（12~13）
- 左子树与5同理（右子树比较短，比较容易分析哈哈），一直递归遍历下去
- 右子树（12~13）中13排最后，那么13是根结点；12<13，是13的左子树；15>13是右子树
由分析可知：根结点之前的数组元素，分为两部分：连续的元素比根结点小是左子树，连续的元素比根结点大是右子树。
那么从array[0]开始往后遍历，当数组元素开始大于根结点时（array[x]大于根结点），可以把根结点（array[root]）之前元素分为两部分：array[0] ~ array[x-1]为左子树，array[x]~array[root-1]为右子树，它们都必须大于array[root]。如果满足条件，证明：对于这个结点来说，它的左右子树是满足二叉查找树特性的。接下来就递归遍历左子树和右子树，当所有的非叶子结点都满足以上条件时，证明这个二叉树是二叉查找树。
算法：
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开始就是右子树了
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;
}
对于这道题目，如果改为判断是否为一棵二叉查找树的先序遍历序列，我们也可以用同样的思路去解，只不过如果是先序遍历序列，则数组的第一个元素为根节点的值，但后面的数组仍可分为两部分并分别代表左右子树。
4. 将二叉搜索树转换成一个排序的双向链表（要求不能创建任何新的结点，只能调整树中结点指针的指向）
二叉排序树的定义如下：
class TreeNode {
int value;
TreeNode left;
TreeNode right;
}
该算法内容均来自 FutureFlyme 的CSDN 博客 ，全文地址请点击：
https://blog.csdn.net/FutureFlyme/article/details/69937007?utm_source=copy
分析：
1. 将左子树构成双链表，并返回该链表的头节点(左子树最左边的节点)
2. 定位到左链表的最后一个节点(左子树最右边的节点)
3. 如果左子树链表不为空，则将当前root追加到左子树链表后
4. 将右子树构造成双向链表，并返回链表头结点(右子树最左边的节点)
5. 如果右子树链表不为空，将右子树链表追加到当前root后
6. 根据左子树链表是否为空返回的整体双向链表的头节点
4.1 递归实现
//Convert函数把一个二叉搜索树变成一个有序的双向链表，返回双向链表的头结点，参数root为二叉搜索树的根节点
public TreeNode Convert(TreeNode root){
if(root==null){//假如根节点为空，返回空
return null;
}
if(root.left==null&&root.right==null){//假如只有一个根节点，则返回根节点
return root;
}
//1、将左子树构造成双链表，并返回该链表头结点left
TreeNode left=Convert(root.left);
//2、定位到左子树链表的最后一个节点（左子树最右边的节点）
TreeNode p=left;//创建一个临时节点P,用来遍历找到左链表的最后一个节点(左子树最右边的节点)，p初始化指向做左子树的根节点，
while(p!=null&&p.right!=null){
p=p.right;//最终p为左子树最右边的节点
}
//3、如果左子树链表不为空，将当前root追加到左子树链表后
if(left!=null){//左子树链表不为空
p.right=root;//左子树链表的最后一个节点p（左子树最右边节点）的右指针指向当前root节点
root.left=p;//当前root节点的左指针指向左子树链表的最后一个节点p（左子树最右边节点）
}
//4、将右子树构造成双链表，并返回该链表的头结点right
TreeNode right=Convert(root.right);
//5、如果右子树链表不为空，将右子树链表追加到当前root后
if(right!=null){//右子树链表不为空
right.left=root;//右子树链表的头结点right的左指针指向当前root
root.right=right;//当前root的右指针指向右子树链表的头结点right
}
return left!=null?left:root;//根据左子树链表是否为空返回整个双向链表的头指针。
}
4.2 借助Stack，非递归实现
import java.util.Stack;
public TreeNode ConvertBSTToBiList(TreeNode root){
if(root==null){
return null;
}
Stack<TreeNode> stack=new Stack<TreeNode>();
TreeNode p=root;//p为临时节点用来遍历树的节点，初始值为根节点root
TreeNode rootList=null;//用于记录双向链表的头结点
TreeNode pre=null;//用于保存中序遍历序列的上一个节点，即p的上一个节点
boolean isFirst=true;//判断是否为左子树链表的第一个节点
while(p!=null||!stack.isEmpty()){
while(p!=null){
stack.push(p);
p=p.left;
}
p=stack.pop();//此时的p为左子树最左边的节点，
if(isFirst){//假如是左子树链表的第一个节点
rootList=p;//将p赋值给root节点
pre=rootList;
isFirst=false;
}else{
pre.right=p;
p.left=pre;
pre=p;
}
p=p.right;
}
return rootList;
}
5. 找出二叉查找树中第K大的值
二叉排序树的定义如下：
class TreeNode {
int value;
TreeNode left;
TreeNode right;
}
分析：因为二叉排序树的中序遍历是从小到大排列的,所以只需要中序排序逆过来就是从大到小排序的(右->根->左)
算法如下：
public TreeNode findKthBigNode(TreeNode root ,int k){
if(root==null) { return null;}
if(root.right!=null){ findKthBigNode(root.right,k); }
k--; //减一表示访问了这个点
if(k==0) return root; //当k==0时，说明已经访问了k个点，剩余0个点。该Node为第k大
if(root.right!=null){ findKthBigNode(root.left,k); }
}
6. 非递归往二叉排序树插入元素
/**********
【题目】试写一非递归算法，在二叉查找树T中插入元素e。
二叉查找树的类型BSTree定义如下：
typedef struct {
KeyType key;
... ... // 其他数据域
} 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)
/* 在二叉查找树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;
}
----------------------------------------------------------------------
/* 这个方法没实现功能
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
}
} */
网友评论