当前位置:编程学习 > C/C++ >>

[算法导论]二叉查找树的操作C++实现

[cpp]
#include <iostream> 
#include <vector> 
using namespace std; 
/*二叉查找树结构*/ 
typedef struct BSTree 

    int node_value; 
    struct BSTree * left; 
    struct BSTree * right; 
    struct BSTree * parent; 
}Tree; 
Tree * root = NULL; 
/*****构造二叉查找树**********************************************/ 
void  CreateBSTree(Tree * root,int node_value); 
Tree * CreateBSTree(int * array_list,int array_length); 
 
void Print(Tree* root); 
 
/***************************************************************/ 
int Minimum(Tree * p); 
Tree * TreeMinimum(Tree * root); 
int Maximum(Tree * p); 
Tree * TreeMaximum(Tree * root); 
Tree * FindNode(Tree * root,int node_value); 
Tree * Successor(Tree * root); 
Tree * PredeSuccessor(Tree * p); 
bool DeleteTreeNode(Tree * root,int node_value); 
bool DeleteTreeNode(Tree * n); 
/***************************************************************/ 
int main(int argc,char * argv[]) 

     
    //int list[]={5,3,4,9,1,7,11}; 
    int list[]={15,5,16,3,12,20,10,13,18,23,6,7}; 
    root = CreateBSTree(list,12); 
    std::cout<<"Cearte BSTree."<<std::endl; 
    //Print(root); 
    //std::cout<<Successor(FindNode(root,4))->node_value; 
    //Print(root); 
    //std::cout<<std::endl; 
    //DeleteTreeNode(root,15); 
    //Print(root); 
    Tree * t = FindNode(root,18); 
    std::cout<<PredeSuccessor(t)->node_value; 
    getchar(); 
    return 0; 

/*找出树中的最小节点
p数的根节点
*/ 
int Minimum(Tree * p) 

    Tree * t = TreeMinimum(p); 
    if(t != NULL) 
    { 
        return t->node_value ; 
    } 
    else 
    { 
        return -1; 
    } 

Tree * TreeMinimum(Tree * p) 

    if(p->left == NULL) 
    { 
        return p; 
    } 
    TreeMinimum(p->left); 

/*找出树中的最大节点*/ 
int Maximum(Tree * p) 

    Tree * t = TreeMaximum(root); 
    if(t != NULL) 
    { 
        return t->node_value ; 
    } 
    else 
    { 
        return -1; 
    } 

Tree * TreeMaximum(Tree * p) 

    if(p->right == NULL) 
    { 
        return p; 
    } 
    TreeMaximum(p->right); 

/*假定所有的节点值都不相同,找到一个节点的指针
p树的根节点,
node_value要查找的节点的值
*/ 
Tree * FindNode(Tree * p,int node_value) 

    if(p == NULL) 
    { 
        return NULL;/*递归返回标志*/ 
    } 
    if(p->node_value == node_value) 
    { 
        return p; 
    } 
    if(p->node_value < node_value) 
    { 
        FindNode(p->right, node_value); 
    } 
    else 
    { 
        FindNode(p->left, node_value); 
    } 
     

/*找出一个节点的后继结点*/ 
Tree * Successor(Tree * p) 

    if(p == NULL) 
    { 
        return NULL; 
    } 
    if(p->right != NULL) 
    { 
        return TreeMinimum(p->right); 
    } 
    Tree * t = p->parent ; 
    while((t != NULL) && (p == t->right)) 
    { 
        p = t; 
        t = t->parent ; 
    } 
    return t; 

/*找到一个节点的前驱节点
p为节点的指针
*/ 
Tree * PredeSuccessor(Tree * p) 

    if(p == NULL) 
    { 
        return NULL; 
    } 
    else if(p->left != NULL) 
    {/*如果左子树不为空,则前驱为其左子树的最大值节点*/ 
        return TreeMaximum(p->left); 
    } 
    else 
    { 
        Tree * t = p->parent ; 
        while((t != NULL) && (p == t->left)) 
        {/*注意节点t的方向,这个与寻找后继节点相反*/ 
            p = t; 
            t = t->parent; 
        } 
        return t; 
    } 

/*删除一个节点
p为树根节点指针
node_value要删除的节点的值
*/ 
bool DeleteTreeNode(Tree * p,int node_value) 

    Tree * t = FindNode(p,node_value); 
    if(t == NULL) 
    { 
        return false; 
    } 
    if((t->left == NULL)&&(t->right == NULL)) 
    {/*没有子节点*/ 
        Tree* tmp = t; 
        if(tmp->parent->left == tmp) 
        { 
            tmp->parent->left
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,