发布时间 : 星期六 文章数据结构实训报告样本更新完毕开始阅读
吉林工业职业技术学院 数据结构实训
树（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
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