用凹入法输出一个树（注意：不是二叉树）

树是以孩子兄弟表示法存储的，即以二叉树链表作为树的存储结构。链表中结点的两个指针分别指向该结点的第一个孩子结点和下一个兄弟结点
比如

R(a(b,c),d(e,f,g),h)

它的存储形式是：
R(a(b(c),d(e(f(g)),h)))

typedef struct treenode
{
...树是以孩子兄弟表示法存储的，即以二叉树链表作为树的存储结构。链表中结点的两个指针分别指向该结点的第一个孩子结点和下一个兄弟结点
比如

R(a(b,c),d(e,f,g),h)

它的存储形式是：
R(a(b(c),d(e(f(g)),h)))

typedef struct treenode
{
char data;
struct treenode *brother, *child;
}TreeNode;

这是结点的定义
child指向这个结点的第一个孩子结点，brother指向这个结点的下一个兄弟
设计是以第一个孩子作为链表的表头，所有的孩子形成一个兄弟链表

就是写这个void ShowTree(TreeNode *root）

不知道说明白了没，希望有高人帮助一下，谢谢，合适的分都给你了（再加255分）
谢谢展开

蜗牛爬阿爬 · 2018-4-30 01:12:57

#include
using namespace std;
typedef struct treenode
{
char data;
struct treenode *brother, *child;
}TreeNode;
void ShowTree(TreeNode *root)
{
int i;static int deep=0;
if(root==NULL) {printf("\n");return;}
for(i=0;idata);
++deep; ShowTree(root->child);
--deep; ShowTree(root->brother);
}
int main()
{
TreeNode *R,*a,*b,*c,*d,*e,*f,*g,*h;
R=new TreeNode;
a=new TreeNode;
b=new TreeNode;
c=new TreeNode;
d=new TreeNode;
e=new TreeNode;
f=new TreeNode;
g=new TreeNode;
h=new TreeNode;
//R
R->data='R';
R->child=a;
R->brother=NULL;
//a
a->data='a';
a->child=b;
a->brother=d;
//b
b->data='b';
b->child=NULL;
b->brother=c;
//c
c->data='c';
c->child=NULL;
c->brother=NULL;
//d
d->data='d';
d->child=e;
d->brother=h;
//e
e->data='e';
e->child=NULL;
e->brother=f;
//f
f->data='f';
f->child=NULL;
f->brother=g;
//g
g->data='g';
g->child=NULL;
g->brother=NULL;
//h
h->data='h';
h->child=NULL;
h->brother=NULL;
ShowTree(R);

return 0;
}

gbwzx · 2018-4-30 01:12:58

昂？这例子貌似有问题啊，按你的描述这棵树
R(a(b,c),d(e,f,g),h)
转化为二叉表示之后应该是这个样子的，附过程：
R(a)
R(a(b,d))
R(a(b(NULL,c),d(e,h))
R(a(b(NULL,c),d(e(NULL,f),h))
R(a(b(NULL,c),d(e(NULL,f(NULL,g)),h))

按我理解只需要所二叉表示的树还原为用凹入法表示，是这意思不？
是的话那就很简单了，就是一个前序遍历加一些输出判断。

只写ShowTree的话……活动活动筋骨~~
顺带写了个CreateTree，测试用吧~~
void CreateTree(TreeNode* &root, char sTree[])
{
static int iIndex=0;
bool bChNULL=true;
bool bBrNULL=true;
if(sTree[iIndex])
{
  root=(TreeNode*)malloc(sizeof(TreeNode));
  root->data = sTree[iIndex];
  iIndex++;
  if(sTree[iIndex]=='(')
  {
iIndex++;
CreateTree(root->child, sTree);
bChNULL=false;
  }
  if(sTree[iIndex]==',')
  {
iIndex++;
CreateTree(root->brother, sTree);
bBrNULL=false;
  }
  if(sTree[iIndex]==')')
iIndex++;
  if(bChNULL)
root->child=NULL;
  if(bBrNULL)
root->brother=NULL;
}
}

void ShowTree(TreeNode *root)
{
printf("%c",root->data);
if(root->child)
{
  printf("(");
  ShowTree(root->child);
  printf(")");
}
if(root->brother)
{
  printf(",");
  ShowTree(root->brother);
}
}

void main()
{
char sTree[]={"R(a(b,c),d(e,f,g),h)"};//随便改做测试，结构别写错了就行了……
TreeNode *root=NULL;
CreateTree(root, sTree);
printf("R(");ShowTree(root->child);printf(")");
//这里传参是按你要求里说的以第一个孩子为链表头，其实可以直接传root的
}

oonoway · 2018-4-30 01:12:59

数据结构题目啊复杂

pkxu__ · 2018-4-30 01:13:00

为什么匿名啊？
恐怕分不够吧。

用凹入法输出一个树（注意：不是二叉树）

4 个回复

浏览过的版块