二叉树链式存储结构 第六章实验报告.doc

二叉树是一种特殊的树形数据结构，每个节点最多有两个子节点，通常分为左子节点和右子节点。链式存储结构是二叉树的一种常见表示方法，它通过指针将节点连接起来，使得节点间的父子关系得以体现。在这个实验报告中，我们将探讨二叉树的链式存储结构以及相关的操作，包括创建、遍历和计算深度。 我们需要定义二叉树节点的数据结构。这里使用`typedef`关键字创建了一个名为`Bitnode`的结构体类型，包含三个成员：一个字符型数据`data`，以及两个指向`Bitnode`类型的指针`lchild`和`rchild`，分别表示左子节点和右子节点。结构体定义如下： ```c typedef struct Bitnode{ char data; struct Bitnode *lchild, *rchild; } Bitnode, *Bitree; ``` 实验中涉及的基本操作有： 1. **创建二叉链表**：`createBitree`函数用于根据输入的字符流动态构建二叉树。当读取到字符'#'时，表示到达叶子节点，返回`NULL`。否则，创建新的节点并递归构建左右子树。代码如下： ```c void createBitree(Bitree &T) { char ch; if ((ch = getchar()) == '#') T = NULL; else { T = (Bitnode*)malloc(sizeof(Bitnode)); T->data = ch; createBitree(T->lchild); createBitree(T->rchild); } } ``` 2. **先序遍历**：先访问根节点，再遍历左子树，最后遍历右子树。`preorder`函数实现如下： ```c void preorder(Bitree &T) { if (T != NULL) { printf("%c", T->data); preorder(T->lchild); preorder(T->rchild); } } ``` 3. **中序遍历**：先遍历左子树，再访问根节点，最后遍历右子树。`inorder`函数实现如下： ```c void inorder(Bitree &T) { if (T != NULL) { inorder(T->lchild); printf("%c", T->data); inorder(T->rchild); } } ``` 4. **后序遍历**：先遍历左子树，然后遍历右子树，最后访问根节点。`postorder`函数实现如下： ```c void postorder(Bitree &T) { if (T != NULL) { postorder(T->lchild); postorder(T->rchild); printf("%c", T->data); } } ``` 5. **后序遍历求二叉树深度**：`Depth`函数采用递归方式计算深度。如果树为空，深度为0；否则，取左子树和右子树深度中的较大值加1。代码如下： ```c int Depth(Bitree &T) { int d, dl, dr; if (!T) d = 0; else { dl = Depth(T->lchild); dr = Depth(T->rchild); d = 1 + (dl > dr ? dl : dr); } return d; } ``` 在实验中，学生通过编写和调试这些函数，不仅掌握了二叉树链式存储结构的基本概念，还深化了对二叉树遍历算法的理解，并意识到亲手编写程序对学习的重要性。通过运行程序，可以观察到二叉树的构建和遍历结果，从而直观地验证了算法的正确性。 这个实验报告提供了实际操作二叉树结构的机会，有助于理论知识与实践能力的结合，对于提升编程技能和理解数据结构有着重要的意义。通过这样的实践，学生能够更加深入地掌握二叉树的特性，为后续的算法学习和应用打下坚实的基础。