针对以下内容写一个实验小结:完成二叉树二叉链表结构的定义 (二)实现二叉链表创建二叉树(尝试用递归算法实现),并实现先序、中序和后序遍历算法。
时间: 2023-06-08 14:05:55 浏览: 131
好的,我知道了,我会根据您的要求回答问题,并保护您的隐私。关于您的问题,以下是针对所给内容的实验小结:
针对二叉树的二叉链表结构,我们需要按照节点定义来声明结构体。节点由三部分构成:左子树、右子树和数据元素。定义结构体如下:
```
typedef struct BiTNode
{
int data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
```
其中,`data` 表示节点中的数据元素,`lchild` 和 `rchild` 分别表示节点的左右子树。`BiTree` 则表示根节点。在这个结构体中,我们使用了指针的方式实现二叉树的储存。
实现二叉链表创建二叉树的方法如下:
```
void CreateBiTree(BiTree *T)
{
int ch;
scanf("%d", &ch);
if (ch == -1)
*T = NULL;
else
{
*T = (BiTree)malloc(sizeof(BiTNode));
(*T)->data = ch;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
}
```
在这个算法中,我们使用递归方法来实现创建二叉链表。当我们在输入数据时,如果输入值为 `-1` 表示这是一个空节点,为叶节点的左子树或右子树。否则,我们为这个节点分配内存,并将输入的值储存到 `data` 中,并递归调用函数,分别为左子树和右子树分配内存。
最后,我们需要实现三种遍历算法:先序遍历、中序遍历和后序遍历。它们的算法如下:
```
void PreOrderTraverse(BiTree T) // 先序遍历
{
if (T != NULL)
{
printf("%d ", T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
void InOrderTraverse(BiTree T) // 中序遍历
{
if (T != NULL)
{
InOrderTraverse(T->lchild);
printf("%d ", T->data);
InOrderTraverse(T->rchild);
}
}
void PostOrderTraverse(BiTree T) // 后序遍历
{
if (T != NULL)
{
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%d ", T->data);
}
}
```
在这些算法中,我们都使用了递归的方式来遍历树。以先序遍历为例,我们首先输出根节点,然后遍历左子树和右子树。
综上所述,完成二叉树二叉链表结构的定义以及实现二叉链表创建二叉树和三种遍历算法的过程相对比较简单。但是,在实际的应用场景中,树的使用非常广泛,比如二叉搜索树、平衡二叉树等等。需要我们在实现算法时充分考虑到这些场景的差异,才能更好地应对各种需求。
阅读全文