请高手帮忙树的创建为什么不能执行

主题：请高手帮忙树的创建为什么不能执行

ningwshyhm [专家分：0] 发布于 2006-12-04 15:00:00

// 树的孩子兄弟链表创建.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<malloc.h>
#include<iostream.h>
#define null 0
typedef struct CSNode
{
    char data;
    struct CSNode *firstchild, *nextsibling;
} CSNode, *CSTree;
typedef struct QNode{
    CSTree data;
    struct QNode *next;
}QNode, *QueuePtr;

typedef struct{
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;

int InitQueue(LinkQueue &Q){
    Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
    if(!Q.front)
        printf("初始化失败！");
    Q.front->next=null;
    return 1;
}

int EnQueue(LinkQueue &Q,CSTree e){
    QueuePtr p;
    p=(QueuePtr)malloc(sizeof(QNode));
    if(!p)  return 0;
    p->data=e;
    p->next=null;
    Q.rear->next=p;
    Q.rear=p;
    return 1;
}

int DeQueue(LinkQueue &Q,CSTree &e)
{
    QueuePtr p;
    if(Q.front=Q.rear)
        printf("队列为空！");
    p=Q.front->next;
    e=p->data;
    Q.front->next=p->next;
    if(Q.rear==p)
        Q.rear=Q.front;
    free(p);
    return 1;
}

void GetHead(LinkQueue &Q,CSTree &e){
    QueuePtr p;
    if(Q.front=Q.rear)
        printf("队列为空！");
    p=Q.front->next;
    e=p->data;
}

void CreatTree( CSTree &T )
{
    LinkQueue Q;
    InitQueue(Q);
    char ch,fa;
    CSTree p,s,r;
    T = NULL;
    for( scanf("%C,%C",&fa, &ch); ch!=' '; scanf("%C,%C",&fa, &ch))
      {
        p->data = ch;    // 创建结点
        EnQueue(Q, p);       // 指针入队列
        if (fa ==' ')  T = p;     // 所建为根结点
        else
        {
            GetHead(Q,s);  // 取队列头元素(指针值)
            while (s->data != fa ) // 查询双亲结点
            {
                DeQueue(Q,s);  GetHead(Q,s);
            }
           if (!(s->firstchild))
           {
               s->firstchild = p; r = p;
           }// 链接第一个孩子结点
           else
           {
               r->nextsibling = p;  r = p;
           } // 链接其它孩子结点
        }     // 非根结点的情况
      } // for
} // CreateTree

int main(int argc, char* argv[])
{
    CSTree T;
    CreatTree( T ) ;
    printf("Hello World!\n");
    return 0;
}[em18][em18][em18][em18][em18]

本帖地址： http://bbs.pfan.cn/post/207623.html

回复列表（共11个回复）

沙发

hqin6 [专家分：140] 发布于 2006-12-05 00:37:00

我写了一个你看看，或许有些帮助：
template<class T>
void Tree<T>::InputTree()
{
    LinkedQueue<TreeNode<T>*>Node_Q;
    T node_data=0;
    cout<<"请输入你要建立的树的高度："<<endl;
    int num;
    cin>>num;
    if (num==0)
    {
        cout<<"空树!"<<endl;
        exit(1);
    }
    if(num<0) throw OutOfBounds();
    floor=new int[num+1];
    floor[0]=num;
    cout<<"请输入你要建立的树的根节点数据："<<endl;
    cin>>node_data;
    TreeNode<T>*now,*mid;
    root=new TreeNode<T>(node_data);
    TreeNode<T>*last=root;
    bool begin=true;
    floor[1]=1;
    Node_Q.Add(root);
    for (int i=2;i<=floor[0];i++)//每一层i
    {
        floor[i]=0;
        last=Node_Q.First();
        for (int j=1;j<=floor[i-1]&&last;j++)//每一层里每个节点j
        {
            cout<<"请输入节点"<<last->data<<"的子节点，并以#结束："<<endl;
            cin>>node_data;
            while (node_data!='#')
            {
                if (begin)
                {
                    now=new TreeNode<T>(node_data);
                    last->first_child=now;
                    begin=false;
                    Node_Q.Add(now);
                }
                else
                {
                    mid=new TreeNode<T>(node_data);
                    now->next_brother=mid;
                    now=mid;
                    Node_Q.Add(now);
                }
                last->children_num++;
                floor[i]++;
                cin>>node_data;
            }
            if (!Node_Q.IsEmpty())
            {
                Node_Q.Delete(last);
            }
            if(!Node_Q.IsEmpty())last=Node_Q.First();
            begin=true;
        }
    }
}

板凳

hqin6 [专家分：140] 发布于 2006-12-05 00:42:00

要想看结果，我把所有的都发上去吧！
debug.h
//*********
class NoMem//异常类
{
public:
    NoMem(){}
protected:
private:
};
class OutOfBounds
{
public:
    OutOfBounds(){}
protected:
private:
};
//********
LinkedQueue.h
#include "Node.h"
template<class T>
class LinkedQueue
{
public:
    LinkedQueue(){front=rear=0;}
    ~LinkedQueue();
    bool IsEmpty()const{return ((front)?false:true);}
    bool IsFull()const;
    T First()const;
    T Last()const;
    LinkedQueue<T>&Add(const T&x);
    LinkedQueue<T>&Delete(T&x);
protected:
private:
    Node<T>*front;
    Node<T>*rear;
};
template<class T>
LinkedQueue<T>::~LinkedQueue()
{
    Node<T> *next;
    while (front)
    {
        next=front->link;
        delete front;
        front=next;
    }
}
template<class T>
bool LinkedQueue<T>::IsFull()const
{
    Node<T>*p;
    try
    {
        p=new Node<T>;
        delete p;
        return false;
    }
    catch (NoMem)
    {
        return false;
    }
}
template<class T>
T LinkedQueue<T>::First()const
{
    if (IsEmpty())throw OutOfBounds();
    return front->data;
}
template<class T>
T LinkedQueue<T>::Last()const
{
    if (IsEmpty())throw OutOfBounds();
    return rear->data;
}
template<class T>
LinkedQueue<T>&LinkedQueue<T>::Add(const T&x)
{
    Node<T>*p=new Node<T>;
    p->data=x;
    p->link=0;
    if (front)rear->link=p;
    else front=p;
    rear=p;
    return *this;
}
template<class T>
LinkedQueue<T>&LinkedQueue<T>::Delete(T&x)
{
    if (IsEmpty())throw OutOfBounds();
    x=front->data;
    Node<T> *p=front;
    front=front->link;
    delete p;
    return *this;
}
//********
Node.h
template<class T> class LinkedQueue;
template <class T>
class Node
{
    friend LinkedQueue<T>;
public:
protected:
private:
    T data;
    Node<T> *link;
};
//******
stack.h
#include "debug.h"
template <class T>
class SNode
{
public:
    T data;
    SNode<T> *link;
protected:
private:

};
template<class T>
class Stack
{
public:
    Stack(){top=0;}
    ~Stack();
    bool IsEmpty()const{return top==0;}
    bool IsFull()const;
    T Top()const;
    SNode<T>* TopAddress()const{return top;}
    Stack<T>& Add(const T&x);
    Stack<T>&Delete(T&x);
    void OutPut();
protected:
private:
    SNode<T>*top;
};
template<class T>
Stack<T>::~Stack()
{
    SNode<T>*next;
    while (top)
    {
        next=top->link;
        delete top;
        top=next;
    }
}
template<class T>
bool Stack<T>::IsFull()const
{
    try
    {
        SNode<T> *p=new Node<T>;
        delete p;
        return false;
    }
    catch (NoMen)
    {
        return true;
    }
}
template<class T>
T Stack<T>::Top()const
{
    if(IsEmpty())throw OutOfBounds();
    return top->data;
}
template<class T>
Stack<T>& Stack<T>::Add(const T&x)
{
    SNode<T>*p=new SNode<T>;
    p->data=x;
    p->link=top;
    top=p;
    return *this;
}
template<class T>
Stack<T>&Stack<T>::Delete(T&x)
{
    if (IsEmpty())throw OutOfBounds();
    x=top->data;
    SNode<T>*p=top;
    top=top->link;
    delete p;
    return *this;
}
template<class T>
void Stack<T>::OutPut()
{
    SNode<T>*p=top;
    while (p)
    {
        cout<<p->data;
        p=p->link;
        if(p)cout<<"->";
    }
    cout<<endl;
}

3 楼

hqin6 [专家分：140] 发布于 2006-12-05 00:47:00

还有

4 楼

hqin6 [专家分：140] 发布于 2006-12-05 00:47:00

接着还有：
//*******
tree.h
#include <iostream>
#include <vector>
#include "LinkedQueue.h"
#include "stack.h"
#include "treenode.h"
using namespace std;
template <class T>
class Tree
{
public:
    Tree(){root=0;floor=0;}
    ~Tree(){}
    void InputTree();
    void ShowTree();
    void Show_BinaryTree();
    void ShowPath();
    void Show_BPath();
    void DeleteTree();
protected:
private:
    void DeleteNode(TreeNode<T>*p);
    void SearchPath(TreeNode<T>*p,Stack<T>&mystack);
    void Search_BPath(TreeNode<T>*p,Stack<T>&mystack);
    void Print_BNode(TreeNode<T> *p, int c, vector<bool>& isend,bool RorL);
    void PrintNode(TreeNode<T> *p, int c, vector<bool>& isend);
    TreeNode<T> *root;
    int *floor;
};
//析构函数
//*******************************************
template<class T>
void Tree<T>::DeleteTree()
{
    cout<<"销毁所建的树:"<<endl<<endl;
    delete []floor;
    Stack<TreeNode<T>*> node_stack;
    DeleteNode(root);
}
template<class T>
void Tree<T>::DeleteNode(TreeNode<T>*p)
{
    if (!p)
    {
        return;
    }
    if (!p->first_child&&!p->next_brother)
    {
        cout<<"删除节点"<<p->data<<"!"<<endl;
        delete p;
        return;
    }
    DeleteNode(p->first_child);
    p->first_child=0;
    DeleteNode(p->next_brother);
    p->next_brother=0;
    DeleteNode(p);
    p=0;
}

5 楼

hqin6 [专家分：140] 发布于 2006-12-05 00:48:00

//********************************************************
//输入树
//********************************************************
template<class T>
void Tree<T>::InputTree()
{
    LinkedQueue<TreeNode<T>*>Node_Q;
    T node_data=0;
    cout<<"请输入你要建立的树的高度："<<endl;
    int num;
    cin>>num;
    if (num==0)
    {
        cout<<"空树!"<<endl;
        exit(1);
    }
    if(num<0) throw OutOfBounds();
    floor=new int[num+1];
    floor[0]=num;
    cout<<"请输入你要建立的树的根节点数据："<<endl;
    cin>>node_data;
    TreeNode<T>*now,*mid;
    root=new TreeNode<T>(node_data);
    TreeNode<T>*last=root;
    bool begin=true;
    floor[1]=1;
    Node_Q.Add(root);
    for (int i=2;i<=floor[0];i++)//每一层i
    {
        floor[i]=0;
        last=Node_Q.First();
        for (int j=1;j<=floor[i-1]&&last;j++)//每一层里每个节点j
        {
            cout<<"请输入节点"<<last->data<<"的子节点，并以#结束："<<endl;
            cin>>node_data;
            while (node_data!='#')
            {
                if (begin)
                {
                    now=new TreeNode<T>(node_data);
                    last->first_child=now;
                    begin=false;
                    Node_Q.Add(now);
                }
                else
                {
                    mid=new TreeNode<T>(node_data);
                    now->next_brother=mid;
                    now=mid;
                    Node_Q.Add(now);
                }
                last->children_num++;
                floor[i]++;
                cin>>node_data;
            }
            if (!Node_Q.IsEmpty())
            {
                Node_Q.Delete(last);
            }
            if(!Node_Q.IsEmpty())last=Node_Q.First();
            begin=true;
        }
    }
}

6 楼

hqin6 [专家分：140] 发布于 2006-12-05 00:49:00

//************************************************************************
//输出树
//***********************************************************************
template<class T>
void Tree<T>::ShowTree()
{
    cout<<"您输入的树是:"<<endl;
    if (!root)
    {
        cout<<"空树!"<<endl;
        exit(1);
    }
    TreeNode<T>*p=root;
    bool begin=true;
    vector<bool> bIsEnd;
    bIsEnd.push_back(0);
    cout<<"Root:"<<root->data<<endl;
    for(int i=1;i<=floor[2];i++)
    {
        if(i==floor[2])
            bIsEnd[0]=1;
        if (begin)
        {
            p=p->first_child;
            begin=false;
        }
        else p=p->next_brother;
        PrintNode(p,1,bIsEnd);
    }
    cout<<endl;
}
template <class T>
void Tree<T>::PrintNode(TreeNode<T> *p, int c, vector<bool>& isend)
{
    for(int j=0;j<c;j++)
    {//─└├│
        if(isend[j]==0)
            if(j!=c-1)cout<<"│";
            else cout<<"├";
        else
            if(j!=c-1)cout<<"  ";
            else cout<<"└";
        if(j!=c-1)cout<<"  ";
        else cout<<"─";
    }
    if(p)cout<<" "<<p->data;
    cout<<endl;
    bool begin=true;
    int len=p->children_num;
    for(int i=1;i<=len;i++)
    {
        if(isend.size()==c)isend.push_back(0);

        else isend[c]=0;
        if(i==len)
            if(isend.size()==c)isend.push_back(1);
            else isend[c]=1;
        if (begin)
        {
            p=p->first_child;
            begin=false;
        }
        else p=p->next_brother;
        PrintNode(p,c+1,isend);
    }
}
//****************************************************************
//输出树的路径
template<class T>
void Tree<T>::ShowPath()
{
    cout<<"树的路径是:"<<endl;
    if(!root)
    {
        cout<<root->data<<endl;return;
    }
    Stack<T> mystack;
    mystack.Add(root->data);
    SearchPath(root->first_child,mystack);
}
template <class T>
void Tree<T>::SearchPath(TreeNode<T>*p,Stack<T>&mystack)
{
    if(p)mystack.Add(p->data);
    else return;
    if (!p->first_child)
    {
        mystack.OutPut();
    }
    SearchPath(p->first_child,mystack);
    T mid;
    mystack.Delete(mid);
    SearchPath(p->next_brother,mystack);
}

7 楼

hqin6 [专家分：140] 发布于 2006-12-05 00:49:00

//*********************************************************************
//输出二叉树
//***********************************************************************
template<class T>
void Tree<T>::Show_BinaryTree()
{
    cout<<"转化成二叉树是:"<<endl;
    if (!root)
    {
        cout<<"空树!"<<endl;
        exit(1);
    }
    TreeNode<T>*p=root;
    vector<bool> bIsEnd;
    bIsEnd.push_back(0);
    cout<<"Root:"<<root->data<<endl;
    bIsEnd[0]=1;
    {
        p=p->first_child;
    }
    Print_BNode(p,1,bIsEnd,false);
    cout<<endl;
}
template<class T>
void Tree<T>::Print_BNode(TreeNode<T> *p, int c, vector<bool>& isend,bool RorL)
{
    if (!p)
    {
        return;
    }
    for(int j=0;j<c;j++)
    {//─└├│
        if(isend[j]==0)
            if(j!=c-1)cout<<"│";
            else cout<<"├";
        else
            if(j!=c-1)cout<<"  ";
            else cout<<"└";
        if(j!=c-1)cout<<"  ";
        else cout<<"─";
    }
    cout<<" "<<p->data;
    if (RorL)
    {
        cout<<"R";
    }
    else cout<<"L";
    cout<<endl;
    int len;
    if (p->first_child&&p->next_brother)
    {
        len=2;
    }
    else if (!p->first_child&&!p->next_brother)
    {
        len=0;
    }
    else len=1;
    for(int i=1;i<=len;i++)
    {
        if(isend.size()==c)isend.push_back(0);

        else isend[c]=0;
        if(i==len)
            if(isend.size()==c)isend.push_back(1);
            else isend[c]=1;
            if (len==2)
            {
                if(i==1)
                {
                    Print_BNode(p->first_child,c+1,isend,false);
                    p=p->next_brother;
                }
                else Print_BNode(p,c+1,isend,true);
            }
            else if (len==1)
            {
                if(p->first_child)
                    Print_BNode(p->first_child,c+1,isend,false);
                if (p->next_brother)
                {
                    Print_BNode(p->next_brother,c+1,isend,true);
                }
            }
    }
}
//**************************************************************************
//输出二叉树路径
//********************************************************
template<class T>
void Tree<T>::Show_BPath()
{
    cout<<"二叉树的路径是:"<<endl;
    Stack<T>mystack;
    mystack.Add(root->data);
    Search_BPath(root->first_child,mystack);
}
template<class T>
void Tree<T>::Search_BPath(TreeNode<T>*p,Stack<T>&mystack)
{
    if (!p)
    {
        return;
    }
    mystack.Add(p->data);
    T mid;
    if (!p->first_child&&!p->next_brother)
    {
        mystack.OutPut();
    }
    SNode<T> *now=mystack.TopAddress();
    Search_BPath(p->first_child,mystack);
    while (mystack.TopAddress()!=now)
    {
        mystack.Delete(mid);
    }
    Search_BPath(p->next_brother,mystack);
}

//*******
treenode.h
template<class T> class Tree;
template<class T>
class TreeNode
{
    friend class Tree<T>;
public:
    TreeNode(){first_child=next_brother=0,children_num=0;}
    TreeNode(const T&e)
    {
        data=e;
        first_child=next_brother=0;
        children_num=0;
    }
protected:
private:
    T data;
    TreeNode<T> *first_child,*next_brother;
    int children_num;
};

8 楼

hqin6 [专家分：140] 发布于 2006-12-05 00:50:00

//***************
main.cpp
#include "tree.h"
void Pause()
{
    cout<<endl<<endl<<endl;
    system("pause");
    cout<<endl<<endl<<endl;
}
void main()
{
    try
    {
        Tree<char> myTree1;

        myTree1.InputTree();
        Pause();

        myTree1.ShowTree();
        Pause();

        myTree1.ShowPath();
        Pause();

        myTree1.Show_BinaryTree();
        Pause();

        myTree1.Show_BPath();
        Pause();

        myTree1.DeleteTree();
        Pause();
    }
    catch (OutOfBounds)
    {
        cout<<"输入有误!"<<endl;
    }

}

9 楼

ningwshyhm [专家分：0] 发布于 2006-12-05 12:34:00

非常感谢！！

10 楼

ningwshyhm [专家分：0] 发布于 2006-12-05 12:42:00

谢谢

我来回复

您尚未登录，请登录后再回复。点此登录或注册

主题：请高手帮忙树的创建为什么不能执行

回复列表（共11个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：请高手帮忙树的创建为什么不能执行

回复列表 （共11个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共11个回复）