浙江财经大学
信工学院ACM集训队

二叉树相关操作

本文由 Ocrosoft 于 2016-05-26 22:58:54 发表

实现以下功能:

1.根据括号表达式构建树。

2.输出树的括号表达式。

3.输出树的前序遍历、中序遍历、后序遍历、层次遍历、非递归前序遍历、非递归后序遍历。

4.以二叉查找树的方式插入一个节点。

5.插入一个孩子\父亲节点。

6.删除节点。

7.查找节点,判断是否存在。

8.查找给定节点的父节点,判断是否存在。

9.销毁树,重新建树。

10.退出。

Tree.h

#include <string>
using namespace std;
#ifndef TREE_H
#define TREE_H

class Tree
{
    public:
        Tree();
        virtual ~Tree();
        void Creat(Tree *&tree,string s);//根据括号表达式建树
        void PrintWithPara(Tree *p);//输出括号表达式
        void PrintByGraphics(Tree *p,int level,char disp_tab[128]);//输出树的图形
        void PrintPr(Tree *p);//先序遍历
        void PrintIn(Tree *p);//中序遍历
        void PrintAf(Tree *p);//后续遍历
        void PrintCe(Tree *p);//层次遍历
        void Insert1(Tree *p,char c);//插入1,自动排序
        bool Insert2(Tree *p,char c,char cc,int parent,int child);//插入2,为子节点
        bool Insert3(Tree *p,char c,char cc,int child);//插入3,为父节点
        Tree* Find(Tree *p,char c);//查找
        Tree* FindParent(Tree *p,char c);//查找父节点
        bool Delete(Tree *p,char c);//删除节点
        void Dispose(Tree *p);//销毁树
        void PrintData(Tree *p);//输出数据
        void PrintPrS(Tree *p);//非递归先序遍历
        void PrintInS(Tree *p);//非递归中序遍历

    protected:

    private:
        int data;
        Tree *left;
        Tree *right;
};

#endif // TREE_H

Tree.cpp

#include "Tree.h"
#include <iostream>
#include <stack>
#include <cstdio>
#include <queue>
using namespace std;
Tree::Tree()
{
    //ctor
}
Tree::~Tree()
{
    //dtor
}
//根据括号表达式建树
void Tree::Creat(Tree *&tree,string s)
{
    stack<Tree*> st;
    Tree *p = NULL;
    int k;
    tree = NULL;
    string::iterator it=s.begin();
    while(it!=s.end())
    {
        if(*it=='(')
        {
            st.push(p);
            k=1;
        }
        else if(*it==')')st.pop();
        else if(*it==',')k=2;
        else
        {
            p=new Tree();
            p->data=*it;
            p->left=p->right=NULL;
            if(tree==NULL)tree=p;//如果是根节点
            else
            {
                if(k==1)st.top()->left=p;
                else st.top()->right=p;
            }
        }
        it++;
    }
}
//输出括号表达式
void Tree::PrintWithPara(Tree *tree)
{
    if(tree != NULL)
    {
        printf("%c",tree->data);
        if(tree->left!=NULL||tree->right!=NULL)
            cout<<"(";
        PrintWithPara(tree->left);
        if(tree->right!=NULL)
            cout<<",";
        PrintWithPara(tree->right);
        if(tree->left!=NULL||tree->right!=NULL)
            cout<<")";
    }
}
//输出图形化二叉树
void Tree::PrintByGraphics(Tree *p,int level,char disp_tab[128])
{
    int i;
    if (level < 127)
    {
        for (i = 1; i < level; ++i)
            printf(disp_tab[i] ? "| " : "  ");
        if (level)
            printf("+-");
        if (p == NULL)
            printf("\n");
        else
        {
            printf("%c\n", p->data);
            if (p->left != NULL || p->right != NULL)
            {
                disp_tab[level + 1] = 1;
                PrintByGraphics(p->right, level + 1, disp_tab);
                disp_tab[level + 1] = 0;
                PrintByGraphics(p->left, level + 1, disp_tab);
            }
        }
    }
}
//先序遍历
void Tree::PrintPr(Tree *p)
{
    if(p==NULL)return;
    else
    {
        printf("%c ",p->data);
        PrintPr(p->left);
        PrintPr(p->right);
    }
}
//中序遍历
void Tree::PrintIn(Tree *p)
{
    if(p==NULL)return;
    else
    {
        PrintIn(p->left);
        printf("%c ",p->data);
        PrintIn(p->right);
    }
}
//后序遍历
void Tree::PrintAf(Tree *p)
{
    if(p==NULL)return;
    else
    {
        PrintAf(p->left);
        PrintAf(p->right);
        printf("%c ",p->data);
    }
}
//插入节点1,自动判断,插入后必为叶子节点
void Tree::Insert1(Tree *p,char c)
{
    Tree *pp;
    while(p!=NULL)
    {
        if(c>p->data)
        {
            pp=p;
            p=p->right;
        }
        else
        {
            pp=p;
            p=p->left;
        }
    }
    p=new Tree();
    p->data=c;
    p->left=p->right=NULL;
    if(p->data>pp->data)
        pp->right=p;
    else
        pp->left=p;
}
//查找
Tree* Tree::Find(Tree *p,char c)
{
    if(p==NULL)return NULL;
    else
    {
        if(p->data==c)return p;
        Tree *q;
        q=Find(p->left,c);
        if(q!=NULL)return q;
        q=Find(p->right,c);
        if(q!=NULL)return q;
        return NULL;
    }
}
//插入节点2,插入到给出的节点的指定位置
bool Tree::Insert2(Tree *p,char c,char cc,int parent,int child)
{
    Tree *q;
    q=Find(p,c);
    if(q==NULL)
        return false;
    else
    {
        Tree *pq=new Tree();
        pq->data=cc;
        pq->left=pq->right=NULL;
        if(parent==1)//左边
        {
            if(child==1)//左边
                pq->left=q->left;
            else pq->right=q->left;//右边
            q->left=pq;
        }
        else//右边
        {
            if(child==1)//左边
                pq->left=q->right;
            else pq->right=q->right;//右边
            q->right=pq;
        }
        return true;
    }
}
//查找父节点
Tree* Tree::FindParent(Tree *p,char c)
{
    if(p->data==c)
    {
        cout<<"该节点是根节点,";
        return NULL;
    }
    if(p->left==NULL&&p->right==NULL)return NULL;
    else
    {
        if(p->left!=NULL&&p->left->data==c)return p;
        if(p->right!=NULL&&p->right->data==c)return p;
        Tree *q;
        q=FindParent(p->left,c);
        if(q!=NULL)return q;
        q=FindParent(p->right,c);
        if(q!=NULL)return q;
        return NULL;
    }
}
//删除节点
bool Tree::Delete(Tree *p,char c)
{
    Tree *q;
    if(p->data==c)
    {
        cout<<"不允许删除根节点,";
        return false;
    }
    q=Find(p,c);
    if(q==NULL)
        return false;
    else
    {
        if(q->left!=NULL&&q->right!=NULL)//左右子树均存在
        {
            cout<<"该节点左右子树均存在,保留:1.左子树;2.右子树;3.不保留:";
            int child;
            while(1)
            {
                cin>>child;
                if(child>=1&&child<=3)
                {
                    break;
                }
                else cout<<"输入错误,请重新输入:";
            }
            Tree *pq=FindParent(p,c);
            if(child==1)//删除左子树
            {
                if(pq->left==q)pq->left=q->right;
                else pq->right=q->right;
                Dispose(q->left);
            }
            else if(child==2)//删除右子树
            {
                if(pq->left==q)pq->left=q->left;
                else pq->right=q->left;
                Dispose(q->right);
            }
            else//删除子树
            {
                if(pq->left==q)pq->left=NULL;
                else pq->right=NULL;
                Dispose(q->left);
                Dispose(q->right);
            }
            delete q;
            q=NULL;
        }
        else if(q->left!=NULL||q->right!=NULL)//存在一子树
        {
            cout<<"该节点存在子树,1.保留;2.删除:";
            int child;
            while(1)
            {
                cin>>child;
                if(child>=1&&child<=2)
                {
                    break;
                }
                else cout<<"输入错误,请重新输入:";
            }
            Tree *pq=FindParent(p,c);
            if(child==1)
            {
                if(q->left==NULL)
                {
                    if(pq->left==q)pq->left=q->right;
                    else pq->right=q->right;
                }
                else
                {
                    if(pq->left==q)pq->left=q->left;
                    else pq->right=q->left;
                }
                delete q;
                q=NULL;
            }
            else
            {
                if(pq->left==q)pq->left=NULL;
                else pq->right=NULL;
                Dispose(q);
            }
        }
        else//无子树
        {
            Tree *pq=FindParent(p,c);
            if(pq->left==q)pq->left=NULL;
            else pq->right=NULL;
        }
        return true;
    }
}
//层次遍历
void Tree::PrintCe(Tree *p)
{
    queue<Tree*> q;
    while(!q.empty())q.pop();
    q.push(p);
    while(!q.empty())
    {
        p=q.front();
        q.pop();
        printf("%c ",p->data);
        if(p->left!=NULL)
            q.push(p->left);
        if(p->right!=NULL)
            q.push(p->right);
    }
}
//销毁树
void Tree::Dispose(Tree *p)
{
    if(p==NULL)return;
    else
    {
        Dispose(p->left);
        Dispose(p->right);
        delete p;
        p=NULL;
    }
}
//输出某个节点的数据
void Tree::PrintData(Tree *p)
{
    printf("%c",p->data);
}
//非递归先序遍历
void Tree::PrintPrS(Tree *p)
{
    stack s;
    Tree *q=p;
    while(!s.empty()||q!=NULL)
    {
        while(q!=NULL)
        {
            printf("%c",q->data);
            s.push(q);
            q=q->left;
        }
        if(!s.empty())
        {
            q=s.top();
            s.pop();
            q=q->right;
        }
    }
}

//非递归中序遍历
void Tree::PrintInS(Tree *p)
{
    stack s;
    Tree *q=p;
    while(!s.empty()||q!=NULL)
    {
        while(q!=NULL)
        {
            s.push(q);
            q=q->left;
        }
        if(!s.empty())
        {
            q=s.top();
            s.pop();
            printf("%c",q->data);
            q=q->right;
        }
    }
}
//插入父节点
bool Tree::Insert3(Tree *p,char c,char cc,int child)
{
    Tree* q;
    if(p->data==c)//插入到根节点前
    {
        q=new Tree();
        q->data=p->data;
        p->data=cc;
        q->left=p->left;
        q->right=p->right;
        if(child==1)
        {
            p->left=q;
            p->right=NULL;
        }
        else
        {
            p->left=NULL;
            p->right=q;
        }
        return true;
    }
    q=FindParent(p,c);
    if(q==NULL)
        return false;
    else
    {
        Tree *pq=new Tree();
        pq->data=cc;
        pq->left=pq->right=NULL;
        if(q->left->data==c)
        {
            if(child==1)//左边
            {
                pq->left=q->left;
                q->left=pq;
            }
            else
            {
                pq->right=q->left;
                q->left=pq;
            }
        }
        else
        {
            if(child==1)
            {
                pq->left=q->right;
                q->right=pq;
            }
            else
            {
                pq->right=q->right;
                q->right=pq;
            }
        }
        return true;
    }
}

main.cpp

#include "src\Tree.cpp"
#include <windows.h>
void sleep()
{
    for(int i=0; i<3; i++)
    {
        Sleep(500);
        cout<<".";
    }
    Sleep(500);
}
void sleepE()
{
    Sleep(500);
}
void red()
{
    SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_RED);
}
void white()
{
    SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_GREEN|FOREGROUND_RED|FOREGROUND_BLUE);
}
//A(B(D(,G)),C(E,F))
int main()
{
    Tree *NewTree=NULL,*p;
    string s;
    char ch,cc,disp_tab[128];
    int parent,child;
    int operation;
    while(1)
    {
        white();
        if(NewTree==NULL)
        {
            cout<<"1    根据括号表达式建树\n";
        }
        else
        {
            cout<<"2    输出树括号表达式\n";
            cout<<"3    输出树的图形显示\n";
            cout<<"4    输出树的前序遍历\n";
            cout<<"5    输出树的中序遍历\n";
            cout<<"6    输出树的后序遍历\n";
            cout<<"7    输出树的层次遍历\n";
            cout<<"8    插入二叉查找节点\n";
            cout<<"9    插入一个孩子节点\n";
            cout<<"10   插入一个父亲节点\n";
            cout<<"11   树中删除一个节点\n";
            cout<<"12   查找节点是否存在\n";
            cout<<"13   查找节点的父节点\n";
            cout<<"999  销毁树后重新建树\n";
        }
        cout<<"0    退出\n";
        cin>>operation;
        red();
        if(operation!=0)
        {
            if(NewTree==NULL)
            {
                if(operation!=1)operation=-1;
            }
            else
            {
                if(operation!=999)
                {
                    if(operation>=2&&operation<=15) {}
                    else operation=-1;
                }
            }
        }
        switch(operation)
        {
        case -1:
            cout<<"无效操作命令";
            break;
        case 0:
            white();
            return 0;
        case 1:
            cout<<"括号表达式为:";
            cin>>s;
            cout<<"正在建树";
            sleep();
            NewTree->Creat(NewTree,s);//根据括号表达式建树
            cout<<"已完成";
            sleepE();
            break;
        case 2:
            cout<<"正在输出括号表达式";
            sleep();
            cout<<endl;
            NewTree->PrintWithPara(NewTree);//输出括号表达式
            sleepE();
            break;
        case 3:
            cout<<"正在输出图形二叉树";
            sleep();
            cout<<endl;
            NewTree->PrintByGraphics(NewTree,0,disp_tab);
            sleepE();
            break;
        case 4:
            cout<<"正在输出先序遍历";
            sleep();
            cout<<endl;
            NewTree->PrintPr(NewTree);//输出先序遍历
            sleepE();
            break;
        case 5:
            cout<<"正在输出中序遍历";
            sleep();
            cout<<endl;
            NewTree->PrintIn(NewTree);//输出中序遍历
            sleepE();
            break;
        case 6:
            cout<<"正在输出后序遍历";
            sleep();
            cout<<endl;
            NewTree->PrintAf(NewTree);//输出后序遍历
            sleepE();
            break;
        case 7:
            cout<<"正在输出层次遍历";
            sleep();
            cout<<endl;
            NewTree->PrintCe(NewTree);
            break;
        case 8:
            red();
            cout<<"输入要插入的字符:";
            cin>>ch;
            cout<<"正在自动插入为叶子节点";
            sleep();
            NewTree->Insert1(NewTree,ch);//自动插入为叶子节点
            cout<<"已完成";
            sleepE();
            break;
        case 9:
            cout<<"输入要插入子节点的节点:";
            cin>>cc;
            cout<<"输入要插入的子节点:";
            cin>>ch;
            cout<<"插入到1.左节点;2.右节点:";
            while(1)
            {
                cin>>parent;
                if(parent==1||parent==2)break;
                else cout<<"输入错误,请重新输入:";
            }
            cout<<"原子节点置于新节点的1.左;2.右:";
            while(1)
            {
                cin>>child;
                if(child==1||child==2)break;
                else cout<<"输入错误,请重新输入:";
            }
            cout<<"正在插入节点";
            sleep();
            if(NewTree->Insert2(NewTree,cc,ch,parent,child))
                cout<<"已完成";
            else cout<<"插入失败";
            sleepE();
            break;
        case 10:
            cout<<"输入要插入父节点的节点:";
            cin>>cc;
            cout<<"输入要插入的父节点:";
            cin>>ch;
            cout<<"原有节点作为新父节点的1.左子节点;2.右子节点:";
            while(1)
            {
                cin>>child;
                if(child==1||child==2)break;
                else cout<<"输入错误,请重新输入:";
            }
            cout<<"正在插入节点";
            sleep();
            if(NewTree->Insert3(NewTree,cc,ch,child))
                cout<<"已完成";
            else cout<<"插入失败";
            sleepE();
            break;
        case 11:
            cout<<"要删除的节点:";
            cin>>cc;
            if(NewTree->Delete(NewTree,cc))
                cout<<"删除成功";
            else cout<<"删除失败";
            sleepE();
            break;
        case 12:
            cout<<"要查找的节点:";
            cin>>cc;
            if(NewTree->Find(NewTree,cc)==NULL)
                cout<<"未找到指定节点";
            else cout<<"该节点存在";
            sleepE();
            break;
        case 13:
            cout<<"要查找的父节点:";
            cin>>cc;
            p=NewTree->FindParent(NewTree,cc);
            //Tree *p=NewTree->FindParent(NewTree,cc);
            if(p==NULL)
                cout<<"无法找到父节点,请检查该节点是否存在,父节点是否存在";
            else
            {
                cout<<"已找到父节点,父节点数据为:";
                NewTree->PrintData(p);
            }
            sleepE();
            break;
        case 14:
            cout<<"正在输出先序遍历(非递归)"; sleep(); cout<PrintPrS(NewTree);//输出先序遍历
            sleepE();
            break;
        case 15:
            cout<<"正在输出中序遍历(非递归)"; sleep(); cout<PrintInS(NewTree);//输出中序遍历
            sleepE();
            break;
        case 999:
            cout<<"正在销毁树";
            sleep();
            NewTree->Dispose(NewTree);
            NewTree=NULL;
            cout<<"已完成";
            break;
        }
        scanf("%*c%*c");
    }
    return 0;
}

欢迎转载,请保留出处与链接。Ocrosoft » 二叉树相关操作

点赞 (0)or拍砖 (2)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址