[科技论文网] http://www.scipapers.com    2007-12-01  

二叉搜索树BSTree源码

// Binary_Search_Tree.cpp : Defines the entry point for the console application.
//二叉查找树：对于任何结点x,其左子树的关键值最大不超过key[x],右子树的关键值最小不超过key[x]
//某一结点的后继：如果关键值不同，某一结点的后继x,即大于key[x]中的最小的一个。
//
//
//
#include "stdafx.h"
#include <iostream>
#include <assert.h>

//#define CRTDBG_MAP_ALLOC//用于检查内存是否泄露
//#include <stdlib.h>
//#include <crtdbg.h>

template<class T>
class BSTree...{
        struct Link...{
        T    key;
        Link* right;
        Link* left;
        Link* parent;
        Link(T data, Link* r, Link* l, Link* p):
        key(data),right(r),left(l),parent(p)...{}
    };
    Link* root;

public:
  BSTree(T ndata,Link* p, Link* q, Link* e):
      root(new Link(ndata, p, q, e))...{}
  BSTree(T a[],int size):root(new Link(a[0],NULL,NULL,NULL))
      ...{
          
          for(int i = 1; i < size; i++ )
              TreeInsert(a[i]);
      }
 void TreeInsert(T data_/**//*Link* z)*/)
 ...{  
        Link* z = new Link(data_,NULL,NULL,NULL);
        Link* y = NULL;
        Link* x = root;
        while(x != NULL)
        ...{
            y = x; //y作为x的父节点
            if(z->key < x->key)
                x = x->left;
             else
                x = x->right;
        }
        z->parent= y;//父指针只向父结点
        if(y == NULL)
            root = z; //空树
        else if((z->key) < (y->key))//当y不为空的时候
            y->left = z;//父结点指向当前插入结点
         else
            y->right = z;
        
        
    }
    void TreeDeleteNode(T inputdata)
    ...{
        assert(TreeSearchNumber(root, inputdata)->key == inputdata);//查找看有没有值和同结点指示的一样
        Link* z = TreeSearchNumber(root, inputdata);//找到此结点
        Link* y = NULL;
        Link* x = NULL;
        if((z->left == NULL) || (z->right ==NULL))
             y = z;//算法确定要删除节点y,该结点y或者是输入结点z(如果z至多只有一个子女)
        else//上面语句y=z代表代表两种情况，要么是左子女，要么是右子女。下面一句代表有两个子女都存在的情况。
             y = TreeSuccessor(z);//或是z的后继(如果z有两个子女)，而后继本身至多有一个子女。
        if( y->left != NULL)//x被置为y的非NULL子女，或当y无子女被置为NULL。
             x = y->left;
        else
             x = y->right;
        if( x != NULL)//当y的非空子女不为空时，让子女的父指针指向y的父指针
            x->parent = y->parent;
        if( y->parent == NULL)//父结点为空，那么y就是根结点。
            root = x;//让y的子女结点作为根结点
        else 

        ...{   if (y==(y->parent->left))//看看y是不是左结点。
            y->parent->left = x;//让y的父结点的left指向x
            else  
                y->parent->right = x;//否则，right指向x
        
        if(y != z)
            z->key = y->key;
        }
        delete y;
    }
    Link* TreeSearchNumber(Link* x, T k)
    ...{
        if( x == NULL || k == x->key )
            return x;
        if( k < x->key )
            return TreeSearchNumber(x->left, k);
        else
            return TreeSearchNumber(x->right, k);
    }
    Link* TreeMinIMUM(Link* x )
    ...{
        while(x->left != NULL)
            x = x->left;
        return x;
    }
    Link* TreeMaxIMUM(Link* x)
    ...{
       while((x->right) != NULL)
            x = x->right;
        return x;
    }

    Link* TreeSuccessor(Link* x)//存在两种情况:
    ...{
        if (x->right != NULL)//如果结点x的右子树非空，则x的后继即右子树中的最左的结点。
            return TreeMinIMUM(x->right) ;
        Link* y = x->parent;//如果结点x的右子树为空，且x有一个后继y，则y是x的最低祖先结点，
        while( (y != NULL) && (x == x->right))//且y的左儿子也是x的祖先票篇 p154,p155《算法导论》
        ...{
            x = y;
            y = y->parent;
        }
        return y;
    }
    void PrintTree(Link*x)
    ...{   
        if(x)
        ...{
         std::cout<<x->key<<std::endl;
         PrintTree(x->left);
         PrintTree(x->right);
        }
        
    }
    Link*Get(void)
    ...{
        return root;
    }
    void DeleteTree(Link* x)
    ...{
        if(x)
        ...{   
            DeleteTree(x->left);
            DeleteTree(x->right);
            delete x;
            x = NULL;
        }
    }

    ~BSTree()
    ...{  
      DeleteTree(root);
    }
};

int main(int argc, char* argv[])
...{    
    
    BSTree<int>m(15,NULL,NULL,NULL);
    m.TreeInsert(3);
    m.TreeInsert(5);
    m.TreeInsert(12);
    m.TreeInsert(10);
    m.TreeInsert(13);
    m.TreeInsert(6);
    m.TreeInsert(7);
    m.TreeInsert(16);
    m.TreeInsert(20);
    m.TreeInsert(18);
    m.TreeInsert(23);
    m.PrintTree(m.Get());
    //std::cout<<m.TreeMaxIMUM(m.Get())->key<<std::endl;
    //std::cout<<m.TreeMinIMUM(m.Get())->key<<std::endl;
//    m.PrintTree(m.Get());
//_CrtDumpMemoryLeaks();//用于检查内存是否泄露
    m.TreeDeleteNode(5);
    std::cout<<"********"<<std::endl;
//    std::cout<<m.TreeSearchNumber(m.Get(),678)->key<<std::endl;
//    std::cout<<m.TreeSearchNumber(m.Get(),45)->key<<std::endl;
//    std::cout<<m.TreeSearchNumber(m.Get(),234)->key<<std::endl;
//    std::cout<<m.TreeSearchNumber(m.Get(),34)->key<<std::endl;
//    std::cout<<m.TreeSearchNumber(m.Get(),100)->key<<std::endl;
    m.PrintTree(m.Get());
    std::cout<<"----(_________)---"<<std::endl;
    int a[8] = ...{4566,89,34,23,3,1,2,90008};
    BSTree<int>n(a,8);
    n.PrintTree(n.Get());
    

    return 0;
}

    来源：

声明：本文由网友推荐或作者提交，版权归原作者所有，刊登此文仅为传播知识，展示研究成果，提高文章引用率。未经原作者授权，禁止用于任何形式的商业行为。科技论文网倡导尊重知识、尊重劳动、保护原创、知识共享。由于部分论文文章来于网络，文章作者不祥，请相关的原创作者与我们联系，以便加上您的署名。