C++实现二叉列表存储结构和基本算法
时间: 2024-05-08 21:18:54 浏览: 26
二叉树的二叉链表存储结构定义如下:
```
typedef struct BiTNode {
int data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
```
其中,data表示节点的数据,lchild表示左子节点,rchild表示右子节点。
二叉树的遍历有三种基本算法:前序遍历、中序遍历和后序遍历。
前序遍历算法是:先访问当前节点,再遍历左子树,最后遍历右子树。
```
void PreOrderTraverse(BiTree T) {
if (T == NULL) {
return;
}
printf("%d ", T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
```
中序遍历算法是:先遍历左子树,再访问当前节点,最后遍历右子树。
```
void InOrderTraverse(BiTree T) {
if (T == NULL) {
return;
}
InOrderTraverse(T->lchild);
printf("%d ", T->data);
InOrderTraverse(T->rchild);
}
```
后序遍历算法是:先遍历左子树,再遍历右子树,最后访问当前节点。
```
void PostOrderTraverse(BiTree T) {
if (T == NULL) {
return;
}
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%d ", T->data);
}
```