#include <stdio.h> #include <stdlib.h> typedef struct BitNode{ char data; struct BitNode *lchild; struct BitNode *rchild; }BitNode, *BinTree; void CreateBinTree(BinTree *bt){ char ch; if ((ch = getchar()) == '#') { *bt = NULL; }else{ *bt = (BitNode *)malloc(sizeof(BitNode)); (*bt)->data = ch; CreateBinTree(&(*bt)->lchild); CreateBinTree(&(*bt)->rchild); } } void PreOrderTraversal(BinTree *bt){ if (*bt != NULL){ printf("%c", ((*bt)->data)); PreOrderTraversal(&(*bt)->lchild); PreOrderTraversal(&(*bt)->rchild); } } void InOrderTraversal(BinTree *bt){ if (*bt != NULL){ InOrderTraversal(&(*bt)->lchild); printf("%c", (*bt)->data); InOrderTraversal(&(*bt)->rchild); } } void PostOrderTraversal(BinTree *bt){ if (*bt != NULL){ PostOrderTraversal(&(*bt)->lchild); PostOrderTraversal(&(*bt)->rchild); printf("%c", (*bt)->data); } } int main(){ BinTree T; printf("创建一颗二叉树(以#为虚结点):\n"); CreateBinTree(&T); printf("二叉树创建完成。\n"); printf("前序遍历:\n"); PreOrderTraversal(&T); printf("\n中序遍历:\n"); InOrderTraversal(&T); printf("\n后序遍历:\n"); PostOrderTraversal(&T); return 0; }解释这段代码
时间: 2023-06-16 21:08:25 浏览: 115
SeqList.h #include <stdio.h> //包含标准输入输出流的头文件 #include <assert.h
这段代码是实现了二叉树的创建和三种遍历方式(前序遍历、中序遍历和后序遍历)。
首先定义了二叉树结点的结构体BitNode,其中包括一个字符数据和指向左右子树的指针。然后定义了二叉树的类型别名BinTree,实际上就是指向BitNode结构体的指针。
接下来是创建二叉树的函数CreateBinTree,它通过递归的方式,先读入一个字符,如果是“#”表示这是一个虚结点,返回空指针,否则就动态分配一个BitNode结构体,将读入的字符存储到data中,然后递归调用CreateBinTree函数创建左右子树。
然后是三种遍历方式的函数:PreOrderTraversal、InOrderTraversal和PostOrderTraversal。它们都是递归实现的,先输出当前结点的data,然后递归遍历左右子树,只是遍历顺序不同。
最后在main函数中,先调用CreateBinTree函数创建一颗二叉树,然后分别调用三种遍历方式的函数输出遍历结果。
阅读全文