C++:二叉排序树

/ C++ / 没有评论 / 1403浏览

最近要面试整理的二叉树知识

  /*
若它的左子树不为空,则左子树上所有结点的值均小于它的根结点的值;

若它的右子树不为空,则右子树上所有结点的值均大于它的根结点的值;

它的左、右子树分别为二叉排序树。
*/

#include <iostream>

using namespace std;

#define MAXSIZE 100

typedef struct BiTNode{
    int data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;


/**
 * 递归查找二叉排序树 T 中是否存在 key
 * 指针 f 指向 T 的 双亲,其初始调用值为NULL
 * 若查找成功,则指针 p 指向该数据元素结点,并返回TRUE
 * 若查找不成功, 则指针 p 指向查找路径上访问的最后一个结点并返回FALSE
 */
/*
原理:
先将要查找的关键字和根节点进行比较;
若和根节点值相同,则返回根节点值;若比根节点小,就递归查找左子树,若比根节点大,则递归查找右子树
*/
int SearchBST(BiTree T, int key, BiTree f, BiTree *p)
{
    if(!T) //为空树或者为空节点
    {
        *p = f;
        return false;
    }
    else if(key == T->data)
    {
        *p = T;
        return true;
    }
    else if(key < T->data) //在左子树中递归查找
    {
        return SearchBST(T->lchild,key,T,p);
    }
    else
    {
        return SearchBST(T->rchild,key,T,p);
    }
    return false;
}

/**
 * 二叉排序树的插入
 * 当二叉排序树中不存在关键字等于 key 的数据元素时,插入 key 并返回TRUE
 */
/*
原理:
如果在原有的二叉排序树中没有要插入的关键字,则将关键字与查找的结点p(在查找操作中返回的结点)的值进行比较
若p为空,则插入关键字赋值给该节点
若小于结点p的值,则插入关键字作为结点p的左子树;
若大于结点p的值,则插入关键字作为结点p的右子树;
*/
int InsertBST(BiTree *T,int key)
{
    BiTree p,s;
    if(!SearchBST(*T,key,NULL,&p))
    {
        s = (BiTree)malloc(sizeof(BiTNode));
        s->data = key;
        s->lchild = s->rchild = nullptr;

        if(!p)
        {
            *T = s;
        }
        else if(key < p->data)
        {
            p->lchild = s;
        }
        else
        {
            p->rchild = s;
        }
        return true;
    }
    return false;
}

/*
原理:
叶子结点;(很容易实现删除操作,直接删除结点即可)
仅有左或者右子树的结点;(容易实现删除操作,删除结点后,将它的左子树或者右子树整个移动到删除结点的位置)
左右子树都有的结点。(实现删除操作很复杂):将它的直接前驱或者直接后继作为删除结点的数据
*/
int Delete(BiTree *p)
{
    BiTree q,s;
    if((*p)->rchild == nullptr)//需要重接它的左子树
    {
        q = *p;
        *p = (*p)->lchild;
        free(q);
    }
    else if((*p)->lchild == nullptr)//需要重接它的右子树
    {
        q = *p;
        *p = (*p)->rchild;
        free(q);
    }
    else
    {
        q = *p;
        s = (*p)->lchild;
        while (s->rchild) 
        {  // 向右到尽头,找到待删结点的前驱
            q = s;
            s = s->rchild;
        }
        (*p)->data = s->data;  // s 指向被删除结点的直接前驱 (将被删结点前驱的值取代被删结点的值)

        if (q != *p)
            q->rchild = s->lchild;  // 重接 q 的右子树
        else
            q->lchild = s->lchild;  // 重接 q 的左子树

        free(s);
    }
    return true;
}

int DeleteBST(BiTree* T,int key)
{
    if(!*T)
    {
        return false;
    }
    else
    {
        if(key == (*T)->data)
        {
            
        }
        else if(key < (*T)->data)
        {
            return DeleteBST(&(*T)->lchild,key);
        }
        else
        {
            return DeleteBST(&(*T)->rchild,key);
        }
    }

    return true;
}

//中序遍历
void InOrderTraverse(BiTree T)
{
    if (!T)
        return;

    InOrderTraverse(T->lchild);
    //printf("%d ", T->data);
    cout<< T->data << ' ';  
    InOrderTraverse(T->rchild);
}

int main()
{
    int i;
    int a[10] ={62,88,58,47,35,73,51,99,37,93};

    BiTree T = NULL;
    for (i = 0; i < 10; i++) 
    {  // 通过插入操作来构建二叉排序树
        InsertBST(&T, a[i]);
    }

    InOrderTraverse(T);
    system("PAUSE");
    return 0;
}

/* 那么从树根开始: 如果当前结点t 大于结点u、v,说明u、v都在t 的左侧,所以它们的共同祖先必定在t 的左子树中,故从t 的左子树中继续查找; 如果当前结点t 小于结点u、v,说明u、v都在t 的右侧,所以它们的共同祖先必定在t 的右子树中,故从t 的右子树中继续查找; 如果当前结点t 满足 u <t < v,说明u和v分居在t 的两侧,故当前结点t 即为最近公共祖先; 而如果u是v的祖先,那么返回u的父结点,同理,如果v是u的祖先,那么返回v的父结点。 */

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==NULL)
          return NULL;
        while(root){
            if(p->data>root->data&&q->data>root->data)
                root=root->right;
            else if(p->data<root->data&&q->data<root->data)
                root=root->left;
            else return root;
        }
    }