数据结构导论作业三

“以二叉链表作为存储结构，定义二叉树类型 bitree ；建立 create( ) 输入二叉树的结点元素，建立二叉链表；选择一种遍历方式（先序、中序、后序）遍历这棵二叉树。”

二叉树有不同的链式存储结构，最常用的就是二叉链表与三叉链表，本需求中采用二叉链表存储实现建树与遍历树的基本算法。

本方案给出的算法是使用的树的逻辑表示方法中的嵌套括号表示法。

嵌套括号表示法：每棵树对应一个由根作为名字的表，表名放在表的左边，表是由在一个括号里的各子树对应的表组成的，之间用逗号分开。用这种方法表示的树中，结点之间的关系是通过括号的嵌套表示的，如A(B(E,F),C(G(J)),D(H,I(K,L,M))),A为根节点，B,C,D是兄弟，E是B的孩子。

1.创建二叉树

使用一个栈stack保存当前二叉树的根节点，top为其栈指针，k指定其后处理的结点是双亲结点、左孩子（k=1）还是右孩子（k=2）,ch为当前处理的str中的字符，若ch=“（”，则将创建的结点作为双亲结点进栈，并置k=1，其后创建的结点为左孩子；若ch=“）”，表示左右结点处理完毕，退栈；若ch=“，”，表示其后创建的结点为右孩子；其他情况，表示要创建一个结点，并根据k值建立它与栈中结点之间的联系，如此循环直到str处理完毕。

2.二叉树遍历算法的实现采用递归的思想

1.void creatree(Btree *b,char *str)

{

btree *stack[Maxsize],*p=null;

int top=-1,k,j=0;

char ch;

b=null;

ch=str[j]

while (ch!=’\\0’){

switch (ch){

case ’(’:top++;stack[top]=p;k=1;break;     //为左结点

case ’)’:top--;break;

case ’,’:k=2;break;                     //为右结点

default:p=(Btree *)malloc(sizeof(BTree));

p->data=ch;p->lchild=p->rchild=null;

if (b==null)                          //为根结点

b=p;

else  (

switch(k) {

case 1:stack[top]->lchild=p;break;

case 2:stack[top]->rchild=p;break;

}

)

}

j++;

ch=str[j];

}

}

2.先序遍历、中序遍历和后序遍历的递归算法，以先序遍历为例

Void preorder(Bintree bt)

{

if (bt!=null) {

visit(bt);                 //访问根节点bt

preorder(bt->lchild);

preorder(bt->rchild);

}

}

TurboC 2.0 

1.启动TC：在我的电脑中找到TC2.0所在文件夹（c:\c），双击TC.EXE。

2.右键单击标题栏，选“属性”，显示选项?“全屏显示”。

3.新建文件：ALT+F，选“NEW”，编辑源程序。

4.保存文件：按F2键 或者ALT+F，选“SAVE”，命名文件，扩展名必须为 .C 。

5.编译和连接文件：按F9键

6.如果有错误，重新修改源程序，再按F9键，无错误下一步。

7.运行程序：按CTRL+F9键

8.查看运行结果：ALT+F5

9.退出编辑环境：ALT+X

本设计中主要先解决二叉树的逻辑存储结构，以嵌套括号表示法表示一棵二叉树，引入栈来实现物理存储，通过对符号的判断来实现对二叉树结构的构建.

二叉树的遍历采用递归的方式实现，因为要对每个节点访问一次，所以时间复杂性为O（n）