数据结构实训报告样本

吉林工业职业技术学院 数据结构实训

树（Tree）是n（n>=0）个结点的有限集。在任意一棵非空树中： 1) 有且仅有一个特定的称为根的结点；

2) 当n>1时，其余结点可分为m（m>0）个互不相交的有限集T1，T2......Tm，其中每一个集合又是一棵树，并且称为根的子树（SubTree）。

【例】如图1所示：

图1

图1是有8个结点的树，其中A是根，其余结点分成2个互不相交的子集：T1={B，D}，T2={C，E，F，G，H}；T1和T2都是根A的子树，且本身也是一棵树。

【设计方案】1．创建二叉树（可从键盘输入各结点的值） 2．按某种方式对二叉树进行遍历

3．树型结构是一种非常重要的非线性结构。树在客观世界是广泛存在的，在计算 机领域里也得到了广泛的应用。在编译程序里，也可用树来表示源程序的语法结构，在数据库系统中，数形结构也是信息的重要组织形式。

4．节点的有限集合（N大于等于0）。在一棵非空数里：（1）、有且仅有

一个特定的根节点；（2）、当N大于1时，其余结点可分为M（M大于0）个互不相交的子集，其中每一个集合又是一棵树，并且称为根的子树。树的定义是以递归形式给出的。

5．二叉树是另一种树形结构。它的特点是每个结点最多有两棵子树，并且，二叉 树的子树有左右之分，其次序不能颠倒。

4

吉林工业职业技术学院 数据结构实训

从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作： （1）访问结点本身(N)， （2）遍历该结点的左子树(L)， （3）遍历该结点的右子树(R)。 以上三种操作有六种执行次序：

NLR、LNR、LRN、NRL、RNL、RLN。 【详细设计】本程序源代码如下： /*源程序*/

/* Note:Your choice is C IDE */ #include \#include #include #include #define Max 20 typedef char DataType; #define MaxStackSize 50 using namespace std;

typedef struct Node { DataType data;

struct Node *leftChild;

struct Node *rightChild;

}BiTreeNode;

typedef BiTreeNode* DataType2; typedef struct

{ DataType2 stack[MaxStackSize]; int top; } SeqStack; typedef struct

{ DataType2 quene[MaxStackSize]; int front;

5

吉林工业职业技术学院 数据结构实训

int rear; }Quene;

void StackInitiate(SeqStack *S)

{ S->top = 0;

}

int StackNotEmpty(SeqStack S) { if (S.top <= 0) return 0; else return 1; }

int StackPush(SeqStack *S, DataType2 x) { if (S->top >= MaxStackSize)

{ printf(\堆栈已满无法插入! \\n\ return 0; } else

{ S->stack[S->top] = x; S->top ++; return 1; } }

int StackPop(SeqStack *S, DataType2 *d) { if (S->top <= 0)

{ printf(\堆栈已空无数据元素出栈! \\n\ return 0; } else

{ S->top --; *d = S->stack[S->top]; return 1; } }

int StackTop(SeqStack S, DataType2 *d) { if (S.top <= 0)

{ printf(\堆栈已空! \\n\

6

吉林工业职业技术学院 数据结构实训

return 0; } else

{ *d = S.stack[S.top - 1]; return 1; } }

typedef struct node{ char data; struct node *lchild;

struct node *rchild;

}BTNode;

typedef BTNode *BTree; int NodeNum,leaf; BTree CreatBTree(void) {BTree T; char ch;

if((ch=getchar())=='*') return(NULL); else{ T=(BTNode *)malloc(sizeof(BTNode)); T->data=ch;

T->lchild=CreatBTree();

T->rchild=CreatBTree(); return(T);

} }

void Preorder(BTree T) { if(T){ printf(\ Preorder(T->lchild); Preorder(T->rchild);

}

}

7