树与二叉树的应用包括二叉排序树、平衡二叉树、哈夫曼树等等

一、二叉排序树的一些基本操作
//二叉排序树的非递归查找
BiTree BSTSearch(BiTree T, ElemType key) {
while (T != nullptr && T->data != key) {
if (key < T->data)
T = T->lchild;
else
T = T->rchild;
}
return T;
}

//二叉排序树的递归查找
BiTree BSTSearch2(BiTree T, ElemType key) {
if (T == nullptr)
return 0;
if (key == T->data)
return T;
if (key < T->data)
return BSTSearch2(T->lchild, key);
else
return BSTSearch2(T->rchild, key);
}

//二叉排序树的插入
bool BSTInsert(BiTree &T, ElemType key) {
//当查找失败时,会开始插入key结点
if (T == nullptr) {
T = (BiTree) malloc(sizeof(BiTree));
T->data = key;
T->lchild = T->rchild = nullptr;
return 1;
} else if (key == T->data) {
//若已经存在,则插入失败
return 0;
} else if (key < T->data)
return BSTInsert(T->lchild, key);
else
return BSTInsert(T->rchild, key);
}

//二叉排序树的构造
void BSTCreate(BiTree &T, ElemType key[], int n) {
//初始时二叉排序树为空
T = nullptr;
int i = 0;
while (i < n) {
BSTInsert(T, key[i]);
i++;
}
}
二、二叉树树的应用

判断一个给定的二叉树是否是二叉排序树,算法思想,因为二叉排序树的中序遍历是从小到大的,因此只需判断其中序遍历是否从小到大有序即可

int MIN = -32767;    //首先设定一个用于比较的最小值

bool JudegBST(BiTree T) {
int b1, b2;
if (T == nullptr)
return 1; //空树
else {
b1 = JudegBST(T->lchild);
if (b1 == 0 || MIN >= T->data)
return 0;
MIN = T->data;
b2 = JudegBST(T->rchild);
return b2;
}
}

求出指定结点在二叉排序树中的层次,算法思想:查找一次就下降一层

int SarchLevel(BiTree T, BiTree key) {
int n = 0;
BiTree p = T;
if (T) {
n++;
while (p->data != key->data) {
if (key->data < p->data)
p = p->lchild;
else
p = p->rchild;
n++;
}
}
return n;
}

用二叉树遍历的思想判断一个二叉树是否是平衡二叉树,算法思想:高度为0或1,则为平衡二叉树,否则左右子树的高度差不能大于1,balance判断是否是平衡二叉树,h表示高度,int &balance, int &h加引用(&)的原因是会被修改

void JudgeAVL(BiTree T, int &balance, int &h) {
//左右子树的平衡标记和高度
int bl, br, hl, hr;
if (T == nullptr) { //树空
balance = 1;
h = 0;
} else if (T->lchild == nullptr && T->rchild == nullptr) {
//仅有根结点
h = 1;
balance = 1;
} else {
JudgeAVL(T->rchild, bl, hl);
JudgeAVL(T->rchild, br, hr);
//这里加1加的是根结点,因为前面已经处理了根结点
h = (hl > hr ? hl : hr) + 1;
if (abs(hl - hr) < 2) {
//左右子树都平衡才整体平衡
balance = bl & br;
} else {
balance = 0;
}
}
}

求出给定二叉排序序树中的最大值和最小值的关键字,算法思想:对于二叉排序树,最小值在左下角,最大值在右下角

ElemType MaxKey(BiTree T) {
while (T->rchild != nullptr)
T = T->rchild;
return T->data;
}

ElemType MinKey(BiTree T) {
while (T->lchild != nullptr)
T = T->lchild;
return T->data;
}

从大到小输出二叉排序树中所有不小于k的值,算法思想:因为是从大到小输出,所以先遍历右子树,再遍历左子树,用递归的方法可以从最大开始,直到最小

void OutPutKey(BiTree T, ElemType k) {
if (T == nullptr)
return;
if (T->rchild != nullptr)
OutPutKey(T->rchild, k);
if (T->data == k)
cout << T->data << endl;
if (T->lchild != nullptr)
OutPutKey(T->lchild, k);
}