数据结构_二叉树的应用_练习题

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

二叉排序树的一些基本操作

//二叉排序树的非递归查找
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);
}