假设树的存储结构采用孩子兄弟表示法,写出树的先序遍历算法。该算法的函数头为:

Question

voidPreOrderTree(TNode*root,void (*Visit)()),树的孩子兄弟表示法数据类型定义为:typedefstructtnode{DataTypedata;structtnode*firstchild,*nextsibling;}TNode,*Tree;

Answer 1

以下两种描述形式之一均可：

void PreOrderTree(TNode *root, void (*Visit)())

{ p= root; if(p）{Visit(p-> data);

PreOrderTree(p- > firstchild);

PreOrderTree(p-> nextsibling) ；}}

或者:

void PreOrderTree(TNode *root, void ( * Visit)())

{ p= root;

while(p | | ! StackEmpty(s)){

while(p) {Visit(p- > data) ;Push(s,p) ;p=p- > firstchild;}

p= Pop(s);p= p-> nextsibling;}}

扩展资料

孩子兄弟表示法，采用的是链式存储结构，其存储树的实现思想是：从树的根节点开始，依次用链表存储各个节点的孩子节点和兄弟节点。

因此，该链表中的节点应包含以下 3 部分内容：

1、节点的值；

2、指向孩子节点的指针；

3、指向兄弟节点的指针；

用 C 语言代码表示节点结构为：

#define ElemType char

typedef struct CSNode{

    ElemType data;

    struct CSNode * firstchild,*nextsibling;

}CSNode,*CSTree;