采用左孩子右兄弟结构实现森林

71 阅读 0 评论 47 点赞

我是靠谱客的博主长情电脑，最近开发中收集的这篇文章主要介绍采用左孩子右兄弟结构实现森林，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

森林也就是多棵树组合在一起，本文采用左孩子右兄弟结构实现

请一定看清，我说的是森林，不是树

请不要修改我的弹栈函数，那样写是有必要的

先说一下我的过程

要求如下：

1、定义左儿子 —右兄弟链接存储的树类和森林类。
2、验证如下算法的正确性、各种功能及指标：
     1）创建树和森林；
     2）树和森林的先根遍历递归迭代算法；
    3）树和森林的后根遍历递归迭代算法；
    4）树和森林的层次遍历算法。

其实建一个树类就够了，因为森林也是可以转化成二叉树的

因为之前做过二叉树的，而这个也可以转化成二叉树，所以联系起来就比较简单

这里请注意：森林的先根遍历就是二叉树的先根遍历，森林的后根遍历就是二叉树的中根遍历，知道了这个，做起来就比较简单了

关于迭代遍历，需要用到栈类，层次遍历需要用到列表类

输入的时候，比如下边的树

B C

创建的时候则应输入ABD###C##

恩，要说的就这么多了，用codeblocks测试通过，下面上代码

//树结点类TreeNode声明  TreeNode.h
#ifndef TREENODE_H
#define TREENODE_H

#include<iostream>
using namespace std;
class TreeNode
{
private:
    char data;
    TreeNode *firstChild, *nextBrother;
public:
    TreeNode(char value = NULL, TreeNode *L = NULL, TreeNode *R = NULL) :data(value), firstChild(L), nextBrother(R) {}//构造函数

    TreeNode * GetFirstChild()const
    {
        return firstChild;    //大孩子
    }
    void SetFirstChild(TreeNode *t)
    {
        firstChild = t;
    }

    TreeNode * GetNextBrother()const
    {
        return nextBrother;    //右兄弟
    }
    void SetNextBrother(TreeNode *t)
    {
        nextBrother = t;
    }

    char& GetData()
    {
        return data;
    }
    void SetData(const char& item)
    {
        data = item;
    }
};

#endif // TREENODE_H

//顺序队列类  头文件  AQueue.h
#ifndef AQUEUE_H
#define AQUEUE_H

#include"TreeNode.h"
class AQueue
{
private:
    int Size;
    int front, rear, count;
    TreeNode* *QArray;
public:
    AQueue(int MaxQueueSize);
    ~AQueue();

    bool QInsert(TreeNode*& item);    //将元素item插入队尾
    bool QDelete(TreeNode*& item);         //删除队首元素，并将其元素值赋给item
    bool AFront(TreeNode*& item);          //将队首元素赋给变量item

    bool IsFull()
    {
        return count >= Size;
    }
    bool IsEmpty()
    {
        return count == 0;
    }
};

#endif // AQUEUE_H

//顺序队列类具体实现  AQueue.cpp

#include "AQueue.h"

//构造函数
AQueue::AQueue(int MaxQueueSize)
{
    Size = MaxQueueSize;
    QArray = new TreeNode*[MaxQueueSize];
    front = 0;
    rear = 0;
    count = 0;
}

//析构函数
AQueue::~AQueue()
{
    delete[] QArray;
}

//将元素item插入队尾
bool AQueue::QInsert(TreeNode*& item)
{
    if (IsFull())                    //队列满情况
    {
        cout << "队列已满！" << endl;
        return false;
    }
    QArray[rear] = item;       //添加队尾元素
    rear = (rear + 1) % Size;   //修改队尾指针
    count++;                   //队列长度加1
    return true;
}

//删除队首元素，并将其元素值赋给item
bool AQueue::QDelete(TreeNode*& item)
{
    if (IsEmpty())
    {
        cout << "队列已空！" << endl;
        return false;
    }
    item = QArray[front];
    front = (front + 1) % Size;   //front顺时针移动一格
    count--;                        //队列长度减1
    return true;
}

//将队首元素赋给变量item
bool AQueue::AFront(TreeNode*& item)
{
    if (IsEmpty())
    {
        cout << "队列已空！" << endl;
        return false;
    }
    item = QArray[front];
    return true;
}

//栈类 头文件  AStack.h
#ifndef ASTACK_H
#define ASTACK_H

#include "TreeNode.h"

class AStack
{
private:
    int size;
    TreeNode* *stackArray;  //数组
    int top;
public:
    AStack(int MaxStackSize);  //构造函数
    ~AStack();   //析构函数
    bool Push(TreeNode*& item);  //压栈
    bool Pop(TreeNode*& item);    //出栈
    bool Peek(TreeNode*& item)const; //取栈顶元素

    int IsEmpty()const
    {
        return top == -1;    //栈为空？
    }
    int IsFull()const
    {
        return top == size - 1;    //栈为满？
    }
};

#endif // ASTACK_H

//栈类 具体实现  AStack.cpp

#include"AStack.h"

//构造函数
AStack::AStack(int MaxStackSize)
{
    size = MaxStackSize;
    stackArray = new TreeNode*[MaxStackSize];
    top = -1;
}

//析构函数
AStack::~AStack()
{
    delete[] stackArray;
}

//向栈顶压入一个元素
bool AStack::Push(TreeNode*& item)
{
    if (IsFull())
    {
        cout << "栈满！" << endl;
        return false;
    }
    stackArray[++top] = item;
    return true;
}

//从栈顶弹出一个元素
bool AStack::Pop(TreeNode*& item)
{
    if (IsEmpty())
    {
        cout << "栈空" << endl;
        return false;
    }
    item = stackArray[top--];
    return true;
}

//读取栈顶元素
bool AStack::Peek(TreeNode*& item)const
{
    if (IsEmpty())
    {
        cout << "读取栈已空！" << endl;
        return false;
    }
    item = stackArray[top];
    return true;
}

// Tree.h
#ifndef TREE_H
#define TREE_H


#include"TreeNode.h"

class Tree
{
private:
    TreeNode *root;
public:
    Tree()
    {
        root = NULL;    //构造函数
    }

    TreeNode* FirstChild(TreeNode *p);     //返回结点p的大儿子结点
    TreeNode* NextBrother(TreeNode *p);     //返回结点p的下一个兄弟结点

    void PreOrder(TreeNode *t);        //递归先根遍历,同二叉树先根遍历
    void PostOrder(TreeNode *t);        //递归后根遍历，同二叉树中根遍历

    void NorecPreOrder(TreeNode *t);    //先根遍历以t为根指针的树的迭代算法

    void NorecPostOrder(TreeNode *t);     //后根遍历以t为根指针的树的迭代算法,其实是抄的二叉树中根迭代遍历算法。。

    void LevelOrder(TreeNode *t);      //按层次次序遍历以当前结点为根的树，利用一个辅助队列


    TreeNode* GetRoot()
    {
        return root;
    }
    void SetRoot(TreeNode *t)
    {
        root = t;
    }

    TreeNode* Create();    //创建一棵树
    void CreateTree();     //调用Create()函数创建二叉树
};

#endif // TREE_H

//Tree.cpp

#include"Tree.h"
#include"AStack.h"
#include"AQueue.h"

//搜索指针p所指结点的大孩子结点
TreeNode* Tree::FirstChild(TreeNode *p)
{
    if (p != NULL && (p->GetFirstChild()) != NULL)
        return p->GetFirstChild();
    return NULL;
}

//搜索指针p所指向结点的下一个兄弟结点
TreeNode* Tree::NextBrother(TreeNode *p)
{
    if (p != NULL && (p->GetNextBrother()) != NULL)
        return p->GetNextBrother();
    return NULL;
}


//递归先根遍历
void Tree::PreOrder(TreeNode *t)
{
    if (t != NULL)
    {
        cout << t->GetData() << endl;
        PreOrder(t->GetFirstChild());
        PreOrder(t->GetNextBrother());
    }
}

//递归后根遍历
void Tree::PostOrder(TreeNode *t)
{
    if (t != NULL)
    {
        PostOrder(t->GetFirstChild());
        cout << t->GetData() << endl;
        PostOrder(t->GetNextBrother());
    }
}


//先根遍历以t为根指针的树的迭代算法
void Tree::NorecPreOrder(TreeNode *t)
{
    if (t == NULL) return;
    AStack s(15);   //s是元素类型为树节点的栈
    TreeNode *p = t;
    do
    {
        while (p != NULL)                   //循环（1）
        {
            cout << p->GetData() << " ";    //访问结点p
            s.Push(p);                      //结点p入栈
            p = FirstChild(p);
        }
        while (p == NULL&&!s.IsEmpty())       //循环（2）
        {
            s.Pop(p);
            p = NextBrother(p);
        }
    }
    while (p!=NULL||!s.IsEmpty());                    //循环（3）  这儿的控制 P!=NULL使得算法可以一次输出树的全部
    cout << endl;
}

//后根遍历以t为根指针的树的迭代算法
void Tree::NorecPostOrder(TreeNode *t)
{
    if (t == NULL)return;
    AStack s(20);             //顺序栈
    while (t != NULL || !s.IsEmpty())
    {
        while (t != NULL)
        {
            s.Push(t);             //入栈
            t = FirstChild(t);
        }
        if (s.IsEmpty())return;
        s.Pop(t);
        cout << t->GetData() << endl;
        t = NextBrother(t);
    }
}


//按层次次序遍历以当前结点为根的树，利用一个辅助队列
void Tree::LevelOrder(TreeNode *t)
{
    AQueue q(20);                         //队列
    while (t != NULL)                        //若树不为空树，开始树的层次遍历
    {
        TreeNode *p;
        q.QInsert(t);                      //结点t入队
        while (!q.IsEmpty())
        {
            q.QDelete(p);                  //出队一个结点
            cout << p->GetData() << " ";  //访问结点p
            p = FirstChild(p);            //将结点p的所有子结点入队
            while (p != NULL)
            {
                q.QInsert(p);
                p = NextBrother(p);
            }
        }
        t = NextBrother(t);
    }
    cout << endl;
}

//通过调用Creat()函数，创建一棵以root为根的二叉树
void Tree::CreateTree()
{
    cout << "请把森林转化成二叉树形式，并以先根遍历序列输入："<< endl;
    root = Create();
    if (root != NULL)
        cout << "树已创建！"<< endl;
}

//创建一棵二叉树，并返回该二叉树根节点
TreeNode* Tree::Create()
{
    TreeNode *t, *t1, *t2;
    char item;
    cin >> item;                  //顺序读入序列中的一个符号
    if (item == '#')
    {
        t = NULL;
        return t;
    }
    else
    {
        if (!(t = new TreeNode(item, NULL, NULL)))return NULL;
        t1 = Create();            //创建左孩子树
        t->SetFirstChild(t1);
        t2 = Create();            //创建右兄弟树
        t->SetNextBrother(t2);
        return t;
    }
}

// main.cpp
#include"Tree.h"
#include <stdlib.h>

int main()
{
    cout << "     --------------森林------------" << endl;
    cout << " 注意：" << endl;
    cout << " 创建森林，输入的树根节点右孩子需要置空（即不能有右孩子）" << endl;
    cout << " 如果一个节点的某个孩子为空，请用‘#’代替" << endl << endl;
    Tree aTree;
    int i = 1;
    while (i >= 1 && i <= 6)
    {
        cout << " 请选择：" << endl;
        cout << " 1.创建森林" << endl;
        cout << " 2.先根递归遍历" << endl;
        cout << " 3.后根递归遍历" << endl;
        cout << " 4.先根迭代遍历" << endl;
        cout << " 5.后根迭代遍历" << endl;
        cout << " 6.层次遍历" << endl;
        cout << " 7.退出" << endl;
        cin >> i;
        switch (i)
        {
        case 1:
            aTree.CreateTree();
            break;
        case 2:
            aTree.PreOrder(aTree.GetRoot());
            break;
        case 3:
            aTree.PostOrder(aTree.GetRoot());
            break;
        case 4:
            aTree.NorecPreOrder(aTree.GetRoot());
            break;
        case 5:
            aTree.NorecPostOrder(aTree.GetRoot());
            break;
        case 6:
            aTree.LevelOrder(aTree.GetRoot());
            break;
        default:
            break;
        }
        system("pause");
        system("cls");
    }
    return 0;
}