C++树（兄弟孩子结构实现）
树转换为二叉树，森林转换为二叉树，都是基于树的兄弟孩子结构实现的。
树有三种遍历：先根遍历，后根遍历，层次遍历。前两种分别对应于二叉树的前序遍历和中序遍历。层次遍历和二叉树的层次遍历也很相似。
下面是代码：
文件"tree.h"
#include<iostream>
#include<stack>
using namespace std;
//循环队列模版
template<class T>
class My_queue;
template<class T>
class Node
{
private:
T data;
Node<T> *next;
public:
Node()
{
next=0;
}
Node(T d)
{
data=d;
next=0;
}
friend My_queue<T>;
};
template<class T>
class My_queue
{
private:
Node<T> *tail;
public:
My_queue()
{
tail=new Node<T>();
tail->next=tail;
}
bool empty()
{
return (tail->next==tail);
}
void push(T d)
{
Node<T> *p=new Node<T>(d);
p->next=tail->next;
tail->next=p;
tail=p;
}
T front()
{
if(empty())
{
cout<<"queue is empty!"<<endl;
exit(0);
}
Node<T> *p=tail->next;
T data=p->next->data;
return data;
}
void pop()
{
Node<T> *p=tail->next;
Node<T> *q=p->next;
p->next=q->next;
if(q==tail)
tail=p;
delete q;
}
};
class CStree;
class CSnode
{
private:
char data;
CSnode *firstchild;
CSnode *nextsibling;
friend CStree;
};
class CStree
{
public:
void Create_Tree(CSnode *&T) //创建树
{
//按照从上到下，从左往右的顺序输入“双亲——孩子”的有序对，建立树的孩子兄弟存储结构
//输入时，以('#','#')为结束标志，根结点双亲为空，也是以'#'来表示
T=NULL;
My_queue<CSnode *> q;
char parent,child;
cout<<"输入双亲，孩子有序对，以'#','#'作为输入结束标志"<<endl;
for(cin>>parent>>child;child!='#';cin>>parent>>child)
{
CSnode *p=new CSnode;
p->data=child;
p->firstchild=p->nextsibling=NULL; //暂时现将它们置空
q.push(p);
if(parent=='#')
T=p;
else
{
CSnode *r;
CSnode *s=q.front();
while(s->data!=parent)
{
q.pop();
s=q.front();
}
if(!s->firstchild) //链接第一个孩子结点
{
s->firstchild=p;
r=p;
}
else
{
r->nextsibling=p;
r=p;
}
}
}//end_for
}//end_void
void Get_Children(CSnode *T) //找结点孩子
{
//在T的还在兄弟表示法中，求输入结点的孩子
cout<<"输入你要找的结点的值：";
char x;
cin>>x;
My_queue<CSnode *> q;
if(!T)
{
cout<<"这是一棵空树！"<<endl;
return ;
}
q.push(T);
CSnode *r=NULL;
if(T->data==x)
r=T;
else
{
do
{
CSnode *p=q.front();
q.pop();
if(p->firstchild && p->firstchild->data==x)
{
r=p->firstchild;
break;
}
if(p->firstchild && p->firstchild->data!=x)
q.push(p->firstchild);
if(p->nextsibling && p->nextsibling->data==x)
{
r=p->nextsibling;
break;
}
if(p->nextsibling && p->nextsibling->data!=x)
q.push(p->nextsibling);
}while(!q.empty());
}
if(r==NULL)
{
cout<<"树T中没有结点"<<x<<endl;
return;
}
else
Print_children(r);
}
void Print_children(CSnode *p)
{
CSnode *q=p->firstchild;
if(!q)
{
cout<<"结点"<<p->data<<"没有孩子"<<endl;
return ;
}
cout<<"结点"<<p->data<<"的所有孩子是：";
while(q)
{
cout<<q->data<<" ";
q=q->nextsibling;
}
cout<<endl;
}
void OutPath(CSnode *T,stack<char> &s) //求路径
{
//输出树T中从根节点到所有叶子结点的路径，用栈暂存路径
while(T)
{
s.push(T->data); //将当前层访问的结点记入路径
if(!T->firstchild)
Print_stack(s); //输出从栈底到栈顶的元素
else
OutPath(T->firstchild,s); //继续遍历左子树
s.pop(); //将当前层访问的结点从路径中删除
T=T->nextsibling; //继续访问右子树
}
}
void Print_stack(stack<char> s)
{
char temp[100];
int i=0;
while(!s.empty())
{
temp[i]=s.top();
s.pop();
i++;
}
cout<<"从根节点到叶子结点的一条路径：";
for(int j=i-1;j>0;j--)
cout<<temp[j]<<"->";
cout<<temp[0]<<endl;
}
void PreRoot_Traverse(CSnode *T) //先根遍历
{
if(T)
{
cout<<T->data<<" ";
PreRoot_Traverse(T->firstchild);
PreRoot_Traverse(T->nextsibling);
}
}
void PostRoot_Traverse(CSnode *T) //后根遍历
{
if(T)
{
PostRoot_Traverse(T->firstchild);
cout<<T->data<<" ";
PostRoot_Traverse(T->nextsibling);
}
}
void LevelOrder_Traverse(CSnode *T) //层次遍历
{
My_queue<CSnode *> q;
CSnode *t;
q.push(T);
do
{
t=q.front();
do
{
cout<<t->data<<" ";
if(t->firstchild)
q.push(t->firstchild);
t=t->nextsibling;
}while(t);
q.pop();
}while(!q.empty());
}
};
测试文件"main.cpp"
#include"tree.h"
int main()
{
CStree tree;
CSnode *T;
tree.Create_Tree(T);
tree.Get_Children(T);
stack<char> s;
tree.OutPath(T,s);
cout<<"树的先根遍历为：";
tree.PreRoot_Traverse(T);
cout<<endl;
cout<<"树的后根遍历为：";
tree.PostRoot_Traverse(T);
cout<<endl;
cout<<"层次遍历树为：";
tree.LevelOrder_Traverse(T);
cout<<endl;
return 0;
}
输入 # A A B A C A D C E C F C G C H E I E J G K # # 后生成的树和转换为二叉树后就是下面这种效果：
输出结果为：输入双亲，孩子有序对，以'#','#'作为输入结束标志
# A
A B
A C
A D
C E
C F
C G
C H
E I
E J
G K
# #
输入你要找的结点的值：C
结点C的所有孩子是：E F G H
从根节点到叶子结点的一条路径：A->B
从根节点到叶子结点的一条路径：A->C->E->I
从根节点到叶子结点的一条路径：A->C->E->J
从根节点到叶子结点的一条路径：A->C->F
从根节点到叶子结点的一条路径：A->C->G->K
从根节点到叶子结点的一条路径：A->C->H
从根节点到叶子结点的一条路径：A->D
树的先根遍历为：A B C E I J F G K H D
树的后根遍历为：B I J E F K G H C D A
层次遍历树为：A B C D E F G H I J K
Press any key to continue