俄罗斯贵宾会 > 操作系统 > 俄罗斯贵宾会实现树的基本操作
俄罗斯贵宾会实现树的基本操作

       争论,在下将不胜感谢!

        }//switch结束
        //调节循环
        cout << "是或不是继续?继续请按1,退出请按0:" << endl;
        int ifgoon;
        cin >> ifgoon;
        if (ifgoon == 0)flager = false;
    }//while结束
}

    1.开立树并写入数据

    2.树的后根遍历与二叉树的中根遍历即有联系又有分别,请读者注意剖析心得。

template<typename T>             //在树中删去以某结点为根的树
void Tree<T>::Del(Node<T>* t)
{
    if (t != NULL)
    {
        Del(t->left);
        Del(t->right);
        Addqd(t->data);
        delete t;
        size--;
    }
}

Ⅱ.功能:

template<typename T>            //找出数据域为某值的结点
void Tree<T>::Search(Node<T>* t, const T& item, bool& sign)
{
    if (t)
    {
        Search(t->left, item, sign);
        Search(t->right, item, sign);
        if (t->data == item){ sign = true; Addqs(t); }
    }
}

template<typename T>             //Quefh出队三个结点
void Tree<T>::Outqh(Node<T>* &pn, int &levl)
{
    pn = hhead->nodrs;              
    levl = hhead->leve;
    Quefh<T>* itemph;
    itemph = hhead;
    hhead = hhead->hnext;
    delete itemph;
    hsize--;
}

template<typename T>          //Quefs布局函数
Quefs<T>::Quefs(Node<T>* snds, Quefs<T>* snxt)
{
    snodrs = snds;
    snext = snxt;
}

template<typename T>               //档案的次序遍历 LeveTra是level traversal的缩写
void Tree<T>::LeveTra(Node<T>* t)
{
    int count=0;
    Node<T>* pt;
    Addqs(t);
    while (ssize>0)
    {
        pt = Outqs();
        count++;
        cout << setiosflags(ios::left);
        cout << setw(10) << pt->data;
        if (count % 5 == 0)cout << endl;
        pt = pt->left;
        while (pt)
        {
            Addqs(pt);
            pt = pt->right;
        }
    }
}
template<typename T>          //计算树高
int Tree<T>::Couhg(Node<T>* t)
{
    int level = 0, lev, max = 0;
    Node<T>* pt;
    Addqh(t, level);
    while (hsize>0)
    {
        Outqh(pt, lev);
        level = lev + 1;
        if (max < lev)max = lev;
        while (pt)
        {
            if (pt->left)Addqh(pt->left, level);
            pt = pt->right;
        }
    }
    hhead = htail = NULL;
    return max;
}

template<typename T>               //输出队列Quefd内全部元素
void Tree<T>::D_ShowAll(Quefd<T>* dheader)
{
    Quefd<T>* dp = dheader;
    for (int i = 1; i <= dsize; i++)
    {
        cout << setiosflags(ios::left);
        cout << setw(10) << dp->ddata;
        if (i % 5 == 0)cout << endl;
        dp = dp->dnext;
    }
    cout << endl;
}

template<typename T>           //利用布局体Quefd布局的一时库房的入队操作
Node<T>* Tree<T>::Push(Node<T>* t)
{
    while (!t->right)
    {
        top = new Quefd<T>(t->data, top);
        t = t->left;
    }
    return t;
}

Ⅳ.结语:

template<typename T>           //类布局函数
Tree<T>::Tree()
{
    root = NULL;
    hhead = NULL;
    htail = NULL;
    shead = NULL;
    stail = NULL;
    dhead = NULL;
    dtail = NULL;
    top = NULL;
    size = 0;
    hsize = 0;
    ssize = 0;
    dsize = 0;
}

template<typename T>             //Quefd入队四个结点
void Tree<T>::Addqd(const T& dedata)
{
    if (!dhead){ dhead = dtail = new Quefd<T>(dedata, NULL); dsize = 1; }
    else
    {
        dtail->dnext = new Quefd<T>(dedata, NULL);
        dtail = dtail->dnext;
        dsize++;
    }
}

template<typename T>             //Quefs出队二个结点
Node<T>* Tree<T>::Outqs()
{
    Node<T>* pn;
    pn = shead->snodrs;
    Quefs<T>* itemps;
    itemps = shead;
    shead = shead->snext;
    delete itemps;
    ssize--;
    return pn;
}

//.cpp文件

    5.等级次序遍历树

template<typename T>           //清空队列Quefh
void Tree<T>::Delqh()
{
    while (hhead)
    {
        Quefh<T>* itemphd;
        itemphd = hhead; hhead = hhead->hnext; delete itemphd;
    }
}

template<typename T>                         //获得某结点(以地点为机要值)的父结点之处
Node<T>* Tree<T>::GetFather(Node<T>* t, Node<T>* p)
{
    Node<T>* q;
    if (t == NULL)return NULL;
    if (t->left == p || t->right == p)return t;
    q = GetFather(t->left, p);
    if (q != NULL)return q;
    else return GetFather(t->right, p);
}

Ⅲ.代码:

Ⅰ.说明:

template<typename T>        //树结点初始化
Node<T>::Node(const T& item)  
{
    data = item;
    left = NULL;
    right = NULL;
}

template<typename T>           //树类
class Tree
{
private:
    Node<T>* root;
    Quefh<T> *hhead, *htail;
    Quefs<T> *shead, *stail;
    Quefd<T> *dhead, *dtail,*top;
    int size;
    int hsize;
    int ssize;
    int dsize;
public:
    Tree();
    ~Tree();
    void Operate();
private:
    Node<T>* Creat(Node<T>* &rt);
    void Destory(Node <T>* t);
    void Addqh(Node<T>* pn, int levl);
    void Addqs(Node<T>* spn);  
    void Addqd(const T& dedata);
    void Outqh(Node<T>* &pn, int &levl);
    Node<T>* Outqs();
    void Delqh();
    void Delqs();
    void Delqd();
    int Couhg(Node<T>* t);
    Node<T>* GetFather(Node<T>* t, Node<T>* p);
    void Search(Node<T>* t, const T& item, bool& sign);
    void Del(Node<T>* t);
    void D_ShowAll(Quefd<T>* dheader);
    void FiRoTra(Node<T>* rt, int& ct);
    void MiRoTra(Node<T>* rt, int& ct);
    void LeveTra(Node<T>* t);
    void ShowAll(Quefs<T>* header);
    Node<T>* Push(Node<T>* t);
    void PopAll(int& ct);
};

#include<iostream>
#include<iomanip>
using namespace std;

template<typename T>           //销毁树
void Tree<T>::Destory(Node<T>* t)
{
    if (t != NULL)
    {
        Destory(t->left);
        Destory(t->right);
        delete t;
        size--;
    }
}

template<typename T>           //清空队列Quefs
void Tree<T>::Delqs()
{
    Quefs<T>* itempsd;
    while(shead){ itempsd = shead; shead = shead->snext; delete itempsd; }
}

template<typename T>              //先根递归遍历 FiRoTra是first root traversal的缩写
void Tree<T>::FiRoTra(Node<T>* rt, int& ct)
{
    if (rt)
    {
        cout << setiosflags(ios::left);
        cout << setw(10) << rt->data;
        ct++;
        if (ct % 5 == 0)
            cout << endl;
        FiRoTra(rt->left, ct);
        FiRoTra(rt->right, ct);
    }
}

    2.先根遍历树

#include"Tree.h"
#include<iostream>
using namespace std;
int main()
{
    //是还是不是踏向程序
    int uscho;   bool flag = true;//uscho:user choice的缩写
    cout << "敬告;请你必得按提示供给操作,假使您举办了规定以外的操作,因而引致的整套后果,将总体由你个人担任,程序开拓者概不辜负担!" << endl;
    cout << "是或不是走入程序?走入请按1,否则按0;" << endl;
    cin >> uscho;
    if (uscho == 0) return 0;
    //顾客选择品种
    while (flag)
    {
        cout << "请接受你所要创立树的数据类型,输入类型前的数字实行分选;" << endl;
        cout << "1.整型  2.浮点  3.字符" << endl;
        cin >> uscho;
        if (uscho != 1 && uscho != 2 && uscho != 3)
        {
            cout << "您的输入有误!重新输入请按1,退出请按0:" << endl;
            cin >> uscho;
            if (uscho == 0)return 0;
            else  flag = false;
        }
        if (flag) flag = false;
        else flag = true;
    }
    switch (uscho)
    {
    case 1:
    {
              Tree<int> tree_int;
              tree_int.Operate();
              break;
    }
    case 2:
    {
              Tree<float> tree_float;
              tree_float.Operate();
              break;
    }
    case 3:
    {
              Tree<char> tree_char;
              tree_char.Operate();
              break;
    }
    default:
        cout << "您的输入有误!" << endl;
        break;
    }
    return 0;
}

template<typename T>          //创建树
Node<T>* Tree<T>::Creat(Node<T>* &rt)   
{
    int choice; bool flag;
    if (size > 0)
    {
        cout << "是还是不是持续创制子树?是请按1,否请按0:" << endl;
        cin >> choice;
        flag = true;
    }
    if (size == 0)
    {
        cout << "请输入根结点数据;" << endl;
        T data; cin >> data;
        rt = new Node<T>(data);
        if (!rt卡塔尔国{ cout << "根结点创造败北!" << endl; return NULL; }
        size++;
        flag = false;
        cout << "根结点成立成功!" << endl;
        cout << "近些日子树中国共产党有结点" << size << "个。" << endl;
    }
    if (flag)
    {
        if (choice == 0)return 0;
        else
        {
            cout << "请输入子结点数据;" << endl;
            T data; cin >> data;
            rt = new Node<T>(data);
            if (!rt卡塔尔{ cout << "子结点创立战败!" << endl; return NULL; }
            size++;
            cout << "子结点创立成功!" << endl;
            cout << "近来树中国共产党有结点" << size << "个。" << endl;
        }
    }
    Creat(rt->left);
    Creat(rt->right);
    return root;
}

//.h文件

template<typename T>          //类析构函数
Tree<T>::~Tree()
{
    Destory(root);
}

template<typename T>           //帮忙队列,删除结点 Quefd:queue for delete
struct Quefd                   //此队列同期在后根遍历中做有时库房
{
    T ddata;
    Quefd<T>* dnext;
    Quefd(const T& ddt, Quefd<T>* dnxt);
};

template<typename T>            //二遍性弹骑行列中持有因素
void Tree<T>::PopAll(int& ct)
{
    while (top)
    {
        cout << setiosflags(ios::left);
        cout << setw(10) << top->ddata;
        ct++;
        if (ct % 5 == 0)cout << endl;
        Quefd<T>* itemp4;
        itemp4 = top; top = top->dnext; delete itemp4;
    }
}
template<typename T>           //清空队列Quefs
void Tree<T>::Delqd()
{
    Quefd<T>* itempdd;
    while (dhead){ itempdd = dhead; dhead = dhead->dnext; delete itempdd; }
}

template<typename T>        //Quefh布局函数
Quefh<T>::Quefh(Node<T>* nds, int lel, Quefh<T>* hnxt)
{
    nodrs = nds;
    leve = lel;
    hnext = hnxt;
}

template<typename T>        //扶助队列,查找结点 Quefs:queue for search
struct Quefs                //此队列相同的时候用于层次遍历   
{
    Node<T>* snodrs;        //Quefs::node's adress
    Quefs<T>* snext;
    Quefs(Node<T>* snds, Quefs<T>* snxt);
};

template<typename T>           //Quefd布局函数
Quefd<T>::Quefd(const T& ddt, Quefd<T>* dnxt)
{
    ddata = ddt;
    dnext = dnxt;
}

    7.剔除数据域为某值的结点及其子树

template<typename T>       //树结点
struct Node            
{
    T data;
    Node<T> *left, *right;
    Node(const T& item);
};

    6.寻找数据域为某值的结点

template<typename T>             //Quefh入队三个结点
void Tree<T>::Addqh(Node<T>* pn, int levl)
{
    if (!hhead){ hhead = htail = new Quefh<T>(pn, levl, NULL); hsize = 1; }
    else
    {
        htail->hnext = new Quefh<T>(pn, levl, NULL);
        htail = htail->hnext;
        hsize++;
    }
}

    4.后根遍历树

    代码已由此测量试验,在VS二〇一一上打响运营!
    发此文有两大目标:
    1.和大家交换涉世,供应和需要要的人参照他事他说加以考察。
    2.在下生手,代码中难免有不妥之处,哀告大神商量指正。您的商议正是在下拉长的起源,对于你的

#ifndef TREE_H
#define TREE_H

    1.使用左孩子右兄弟的方法,转变为二叉树来得以完结。

    8.销毁树

#endif

template<typename T>               //输出队列Quefs内整个成分
void Tree<T>::ShowAll(Quefs<T>* header)
{
    Quefs<T>* p = header;
    for (int i = 1; i <= ssize; i++)
    {
        cout << p->snodrs << "  ";
        if (i % 5 == 0)cout << endl;
        p = p->snext;
    }
    cout << endl;
}

template<typename T>             //Quefs入队三个结点
void Tree<T>::Addqs(Node<T>* spn)
{
    if (!shead){ shead = stail = new Quefs<T>(spn, NULL); ssize = 1; }
    else
    {
        stail->snext = new Quefs<T>(spn, NULL);
        stail = stail->snext;
        ssize++;
    }
}

template <typename T>
void Tree<T>::Operate()
{
    bool flager = true;
    while (flager)
    {
        cout << "请您选取操作(输入操作前的数字进行分选):" << endl;
        cout << "1.开立树并写入数据" << endl;
        cout << "2.先根遍历树" << endl;
        cout << "3.总括树高" << endl;
        cout << "4.后根遍历树" << endl;
        cout << "5.档期的顺序遍历树" << endl;
        cout << "6.搜索数据域为某值的结点" << endl;
        cout << "7.刨除数据域为某值的结点及其子树" << endl;
        cout << "8.销毁树" << endl;
        int choice;
        cin >> choice;
        switch (choice)
        {
        //由客商成立树
        case 1:
        {
                  if (root卡塔尔国{ cout << "树已经创办,不须求再建!若想新建,请你先销毁旧树!" << endl; break; }
                  Creat(root);
                  cout << "树成立实现!" << endl;
                  cout << "此树中国共产党有结点" << size << "个!" << endl;
                  break;
        }
        //先根遍历树
        case 2:
        {
                  if (!rootState of Qatar{ cout << "树尚未创造或已被销毁,不只怕实行遍历操作,请你先制造树!" << endl; break; }
                  int counter2 = 0;
                  FiRoTra(root, counter2);
                  cout << endl;
                  break;
        }
        //总结树高    
        case 3:
        {
                  if (!root卡塔尔{ cout << "树还未有成立或已被销毁,不能够测算树高,请你先创建树!" << endl; break; }
                  int high;
                  high= Couhg(root);     
                  cout << "树的万丈为:" <<high<< endl;
                  break;
        }
        //后根遍历树
        case 4:
        {
                  if (!root卡塔尔(قطر‎{ cout << "树还没创立或已被灭亡,不能够实施遍历操作,请您先创设树!" << endl; break; }
                  Node<T>* pt4 = Push(root);
                  int counter4 = 0;
                  MiRoTra(pt4, counter4);
                  PopAll(counter4);
                  cout << endl;
                  break;
        }
        //档次遍历树
        case 5:
        {
                  if (!root卡塔尔国{ cout << "树还没创制或已被死灭,不可能施行遍历操作,请您先创制树!" << endl; break; }              
                  LeveTra(root);
                  cout << endl;
                  shead = stail = NULL;
                  break;
        }
        //找寻数据域为某值的结点    
        case 6:
        {
                  if (!root卡塔尔{ cout << "树还没创制或已被销毁,无法奉行寻找操作,请你先创立树!" << endl; break; }
                  cout << "请您输入数据域的值;" << endl;
                  T indata;  cin >> indata;
                  bool flag = false;
                  Search(root, indata, flag);
                  if (!flagState of Qatar{ cout << "该树中未有数据域为" << indata << "的结点!" << endl; break; }
                  else cout << "该树中数据域为" << indata << "的结点共有" << ssize << "个。" << endl;
                  cout << "是或不是输出那些结点的地址?是请按1,不然按0:" << endl;
                  int choice6; cin >> choice6;
                  if (choice6 == 1)    ShowAll(shead);
                  Delqs(); shead = stail = NULL; ssize = 0;
                  break;
        }
        //删除数据域为某值的结点及其子树
        case 7:
        {
                  if (!root卡塔尔{ cout << "树还未有成立或已被销毁,不能推行删除操作,请你先制造树!" << endl; break; }
                  T data7; bool flag7 = false; bool sign7 = true; int choice7;
                  cout << "请您输入结点数据的值:" << endl;
                  cin >> data7;
                  Search(root, data7, flag7);
                  if (!flag7State of Qatar{ cout << "近年来树中众多据域为" << data7 << "的结点!" << endl;  break; }
                  while (sign7)
                  {
                      Node<T> *p7, *fp7;
                      Quefs<T> *item7;
                      p7 = shead->snodrs;
                      item7 = shead; shead = shead->snext; delete item7; ssize--;
                      if (p7 == root)
                      {
                          cout << "数据域为" << data7 << "的结点为根结点,若实施删除操作将会销毁整棵树!" << endl;
                          cout << "是还是不是明确实行删除操作?鲜明请按1,撤消请按0:" << endl;
                          cin >> choice7;
                          if (choice7 == 0){ Delqs(); shead = stail = NULL; ssize = 0; goto mark7; }
                          else
                          {
                              Destory(p7); root = NULL; size = 0;
                              cout << "删除成功!同有时候整棵树也被销毁!" << endl;
                              Delqs(); shead = stail = NULL; ssize = 0;
                              goto mark7;
                          }
                      }
                      fp7 = GetFather(root, p7);
                      if (p7->right卡塔尔(قطر‎               //其实那一个if可以合成一个,但思索到程序的可读性,分开来写
                      {
                          if (fp7->left == p7)fp7->left = p7->right;
                          if (fp7->right == p7) fp7->right = p7->right;
                          p7->right = NULL;
                      }
                      if (!p7->right)
                      {
                          if (fp7->left == p7)fp7->left = NULL;
                          if (fp7->right == p7)fp7->right = NULL;
                      }
                      Del(p7);
                      cout << "删除成功!" << endl;
                      if (ssize == 0卡塔尔国{ cout << "这个时候树中已过多据域为" << data7 << "的结点及其子树!" << endl; sign7 = false; }
                      if (ssize > 0State of Qatar{ cout << "但那时树中数据域为" << data7 << "的结点还有" << ssize << "个!" << endl; }
                      cout << "本次共剔除结点" << dsize << "个," << "近来树中还应该有结点" << size << "个。" << endl;
                      cout << "是还是不是出示被剔除的各结点的值?是请按1,不然请按0:" << endl;
                      cin >> choice7;
                      if (choice7 == 1)D_ShowAll(dhead);
                      Delqd(); dhead = dtail = NULL; dsize = 0;
                      if (ssize > 0)
                      {
                          cout << "是还是不是继续删除数据域为" << data7 << "的结点及其子树?是请按1,不然按0:" << endl;
                          cin >> choice7;
                          if (choice7 == 0)sign7 = false;
                      }
                  }
                  Delqs(); shead = stail = NULL; ssize = 0;
              mark7:break;
        }
        
        //销毁树
        case 8:
        {
                  if (!root卡塔尔(قطر‎{ cout << "树还未有创制或已被消亡!" << endl; break; }
                  cout << "您显著销毁该树啊?分明请按1,撤废请按0:" << endl;
                  int choice8; cin >> choice8;
                  if (choice8 == 0)break;
                  else Destory(root);
                  root = NULL;
                  size = 0;
                  cout << "树已毁灭!" << endl;
                  break;
        }
            //管理客商的大谬不然输入    
        default:
        {
                   cout << "您的输入有误,不可能举办操作!" << endl;
                   break;
        }

template<typename T>              //中根递归遍历 MiRoTra是middle root traversal的缩写 这里用来打开树的后根遍历
void Tree<T>::MiRoTra(Node<T>* rt, int& ct)
{
    if (rt)
    {
        MiRoTra(rt->left, ct);
        cout << setiosflags(ios::left);
        cout << setw(10) << rt->data;
        ct++;
        if (ct % 5 == 0)
            cout << endl;
        MiRoTra(rt->right, ct);
    }
}

template<typename T>      //援救队列,计算树高 Quefh:queue for high    
struct Quefh
{
    Node<T>* nodrs;       //node's adress
    int leve;             //level
    Quefh<T>* hnext;
    Quefh(Node<T>* nds, int lel, Quefh<T>* hnxt);
};

    3.测算树高

上一篇:没有了 下一篇:2014.11.24
返回列表