tree1_sort.cpp

是一本教程的实例代码,可以下载后直接运行,即可以得到答案.

#include "Tree1.h"                         //二叉树类

TreeNode1* insert(char ch,TreeNode1 *p)    //将ch插入到以p为根结点的子树中，递归算法
{                                     
    if(p==NULL)
        p=new TreeNode1(ch);               //建立叶子结点作为p的左孩子
    else
    { 
        if(ch<=p->data)
            p->left=insert(ch,p->left);    //将ch插入到p的左子树中,建立的叶子结点作为p的左孩子
        else
            p->right=insert(ch,p->right);  //将ch插入到p的右子树中,建立的叶子结点作为p的右孩子
    }
    return p;
}
  
void create(Tree1 &t1,char str[])          //以str字符串建立二叉排序树
{
    t1.root=NULL;
    int i=0;
    cout<<"建立二叉排序树：  ";
    while(str[i]!='\0')
    {
        cout<<str[i]<<" ";
        t1.root=insert(str[i],t1.root);
        i++;
    }
    cout<<"\n";
}

TreeNode1* search(Tree1 &t1,char ch)       //查找结点, 非递归算法
{
    TreeNode1 *p=t1.root,*find=NULL;
    cout<<"Search "<<ch<<": ";
    while(p!=NULL && find==NULL)
    {
        cout<<p->data<<" ";
        if(ch==p->data)
            find=p;
        else if(ch<p->data)
                 p=p->left;
             else 
                 p=p->right;
    }
    return find;
}

void insertnode(Tree1 &t1,char ch)         //将ch插入到子树t1中
{                                          //非递归算法
    if(t1.root==NULL)
        t1.root=new TreeNode1(ch);         //建立根结点
    else
    { 
        TreeNode1 *p=t1.root,*q=NULL;
        cout<<"InsertNode "<<ch<<endl;
        while(p!=NULL)                     //查找插入位置
        {
            q=p;                           //q是p的父母结点
            if(ch<p->data)
                p=p->left;
            else 
                p=p->right;
        }
        p=new TreeNode1(ch);               //插入作为叶子结点
    	if(ch<=q->data)
            q->left=p;                     //p是q的左孩子
        else
            q->right=p;                    //p是q的右孩子
    }
}

void main()
{
    char *str="58324715";
    Tree1 t1;
    create(t1,str);
    t1.inorder();                          //中序遍历二叉排序树

    TreeNode1 *find=search(t1,'1');
    if(find!=NULL)
        cout<<"  find "<<find->data<<"\n";
    else
        cout<<"not found!\n";
    char ch='9';    
    find=search(t1,ch);
    if(find!=NULL)
        cout<<"  find "<<find->data<<"\n";
    else
        cout<<"  not found!\n";

    insertnode(t1,ch);    
    t1.inorder();
}
/*
程序运行结果如下：
建立二叉排序树：  5 8 3 2 4 7 1 5 
中序遍历二叉树:  1 2 3 4 5 5 7 8 
Search 1: 5 3 2 1   find 1
Search 9: 5 8   not found!
InsertNode 9
中序遍历二叉树:  1 2 3 4 5 5 7 8 9 
撤销二叉树: 1 2 5 4 3 7 9 8 5 
*/