自己实现了一下二叉搜索树的数据结构，记录一下：

#include <iostream>

using namespace std;

struct TreeNode{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int value) { val=value; left=NULL; right=NULL; }
};


class SearchTree{

public:
    SearchTree();
    ~SearchTree();
    void Destory(TreeNode *);
    void Insertnode(int);
    void Preorder(TreeNode *);
    void Inorder(TreeNode *);
    void Postorder(TreeNode *);
    void Predisplay();
    void Indisplay();
    void Postdisplay();
private:
    TreeNode *root;

};

SearchTree::SearchTree()
{
    root=NULL;
}

SearchTree::~SearchTree()
{
    cout<<"析构二叉搜索树："<<endl;
    Destory(root);
}

void SearchTree::Destory(TreeNode *node)
{
    if(node!=NULL)
    {
        Destory(node->left);
        Destory(node->right);
        cout<<node->val<<" ";
        delete node;
    }
}

void SearchTree::Insertnode(int value)
{
    if(root==NULL)
        root=new TreeNode(value);
    else
    {
        TreeNode *p,*pre;
        pre=p=root;
        while(p)
        {
            if(p->val==value)
                return;
            else if(p->val>value)
            {
                pre=p;
                p=p->left;
            }
            else
            {
                pre=p;
                p=p->right;
            }

        }
        p=new TreeNode(value);
        if(pre->val>value)
            pre->left=p;
        else
            pre->right=p;
    }
}


void SearchTree::Predisplay()
{
    Preorder(root);
}

void SearchTree::Preorder(TreeNode *root)
{
    if(root)
    {
        cout<<root->val<<" ";
        Preorder(root->left);
        Preorder(root->right);
    }
}

void SearchTree::Indisplay()
{
    Inorder(root);
}

void SearchTree::Inorder(TreeNode *root)
{
    if(root)
    {
        Inorder(root->left);
        cout<<root->val<<" ";
        Inorder(root->right);
    }
}

void SearchTree::Postdisplay()
{
    Postorder(root);
}

void SearchTree::Postorder(TreeNode *root)
{
    if(root)
    {
        Postorder(root->left);
        Postorder(root->right);
        cout<<root->val<<" ";
    }
}

int main()
{
    SearchTree t;
    int a[]={7,4,2,3,15,35,6,45,55,20,1,14};
    int n=sizeof(a)/sizeof(a[0]);
    cout<<"构造二叉搜索树："<<endl;
    for(int i=0;i<n;++i)
    {
        cout<<a[i]<<" ";
        t.Insertnode(a[i]);
    }
    cout<<endl<<"先序遍历序列: "<<endl;
    t.Predisplay();
    cout<<endl<<"中序遍历序列: "<<endl;
    t.Indisplay();
    cout<<endl<<"后序遍历序列: "<<endl;
    t.Postdisplay();
    cout<<endl;
    return 0;
}

c++实现二叉搜索树,布布扣,bubuko.com

c++实现二叉搜索树