二叉树的创建与遍历

### 二叉树的创建与遍历 #### 一、二叉树简介 二叉树是一种常见的非线性数据结构，它是由一个或多个节点组成的一种具有层次关系的数据集合。每个节点最多有两个子节点，分别称为左子节点和右子节点。在二叉树中，根节点位于最顶层，其他节点依次向下延伸。 #### 二、二叉树的创建 在给定文件中，通过递归方式创建了一个二叉树。下面详细介绍这一过程： 1. **定义节点结构**： ```c typedef struct BiTNode { char data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; ``` - `data`：用于存储节点中的数据。 - `lchild` 和 `rchild`：分别指向左子节点和右子节点。 2. **创建二叉树函数**： ```c BiTree CreateBiTree() { charch; scanf("%c", &ch); fflush(stdin); if (ch == '#') { return NULL; } else { struct BiTNode *BT; BT = (BiTree)malloc(sizeof(BiTNode)); BT->data = ch; BT->lchild = CreateBiTree(); BT->rchild = CreateBiTree(); return BT; } } ``` - 用户通过输入字符来构建二叉树。当输入为 '#' 时，表示该位置为空节点，返回 `NULL`。 - 否则，创建一个新的节点，并递归地创建左右子树。 #### 三、二叉树的遍历 二叉树的遍历是指按照一定的顺序访问二叉树中的所有节点，确保每个节点被访问一次。主要有三种遍历方式：前序遍历、中序遍历和后序遍历。而本文件中实现的是按层次遍历。 1. **定义队列结构**： ```c typedef struct Qnode { struct BiTNode *data; struct Qnode *next; } Qnode, *QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; } LinkQueue; ``` - `Qnode` 定义了队列中元素的结构，包含指向节点的指针和下一个元素的指针。 - `LinkQueue` 定义了队列的整体结构，包括队头和队尾指针。 2. **初始化队列**： ```c int InitQueue(LinkQueue &Q) { Q.front = Q.rear = (Qnode *)malloc(sizeof(Qnode)); if (!Q.front) return 0; Q.front->next = NULL; return 1; } ``` - 初始化队列，设置队头队尾指针，并将队列初始化为空。 3. **入队操作**： ```c int EnQueue(LinkQueue &Q, struct BiTNode *e) { QueuePtr p; p = (Qnode *)malloc(sizeof(Qnode)); if (!p) return 0; p->data = e; p->next = NULL; Q.rear->next = p; Q.rear = p; return 1; } ``` - 将新的元素加入到队列的末尾。 4. **出队操作**： ```c int DeQueue(LinkQueue &Q, struct BiTNode *&e) { if (QueueEmpty(Q)) return 0; else { QueuePtr s; e = Q.front->next->data; s = Q.front->next; Q.front->next = s->next; if (Q.front->next == NULL) Q.rear = Q.front; free(s); } } ``` - 从队列头部取出元素。 5. **判断队列是否为空**： ```c int QueueEmpty(LinkQueue &Q) { if (Q.front == Q.rear) return 1; else return 0; } ``` 6. **层次遍历**： ```c int LevelOrder(BiTree &BT) { LinkQueue Q; BiTree p; if (!BT) return 0; InitQueue(Q); EnQueue(Q, BT); while (!QueueEmpty(Q)) { DeQueue(Q, p); printf("%c", p->data); if (p->lchild) EnQueue(Q, p->lchild); if (p->rchild) EnQueue(Q, p->rchild); } } ``` - 层次遍历首先将根节点入队，然后不断从队列中取出节点并打印其值，同时将其左右子节点（如果存在）入队。 #### 四、总结 本篇文章介绍了如何使用 C 语言创建一个二叉树以及如何对该二叉树进行层次遍历。通过递归的方式创建二叉树可以方便地根据用户输入构建出任意形状的二叉树。此外，利用队列结构实现的层次遍历能够有效地按照从上到下、从左到右的顺序访问二叉树中的所有节点。这种方式不仅直观而且易于理解，是学习二叉树数据结构的一个很好的起点。