数据结构 二叉链表 C++ 实现
本文将详细介绍二叉链表的数据类型描述、链式存储结构的建立算法、基本运算的实现等知识点，并提供了 C++ 语言的实现代码。
数据类型描述
在计算机科学中，二叉树是一种特殊的树形结构，每个结点最多有两个孩子结点，分别称为左孩子和右孩子。二叉树可以用链式存储结构来实现，即每个结点用一个结构体来表示，结构体中包含数据域和两个指针域，分别指向左孩子和右孩子。
链式存储结构
链式存储结构是一种常用的二叉树存储方法，每个结点用一个结构体来表示，结构体中包含数据域和两个指针域，分别指向左孩子和右孩子。链式存储结构的建立算法可以分为以下步骤：
1. 定义一个队列来存放二叉链表中的结点。
2. 输入结点值时，必须按照完全二叉树的形式输入；如果非完全二叉树，则必须给定一些假象结点（虚结点），使之完全符合完全二叉树形式。
3. 当我们输入“，”时表示虚结点（结点不存在）；输入结点值时，存在的结点则输入它对应的字符；
4. 最后以一个特殊字符“#”作为输入的结束，表示二叉链表已经完成。
基本运算
二叉链表的基本运算包括层次遍历、先序遍历、中序遍历和后序遍历等。这些遍历算法可以用递归函数来实现，也可以用非递归函数来实现。
层次遍历
层次遍历是一种常用的二叉树遍历算法，它可以用队列来实现。算法的遍历结束条件为头指针下标大于尾指针下标。在遍历过程中，我们可以将每个结点的值输出出来，形成一个层次遍历的结果。
先序遍历
先序遍历是一种常用的二叉树遍历算法，它可以用递归函数来实现。在先序遍历中，我们首先访问当前结点，然后递归地访问左子树和右子树。
中序遍历
中序遍历是一种常用的二叉树遍历算法，它可以用递归函数来实现。在中序遍历中，我们首先递归地访问左子树，然后访问当前结点，最后递归地访问右子树。
后序遍历
后序遍历是一种常用的二叉树遍历算法，它可以用递归函数来实现。在后序遍历中，我们首先递归地访问左子树和右子树，然后访问当前结点。
左右子树交换
左右子树交换是一种常用的二叉树操作算法，它可以用递归函数来实现。在左右子树交换中，我们首先交换左子树的左子树和右子树，然后交换右子树的左子树和右子树，最后交换左子树和右子树的位置。
C++ 实现代码
下面是 C++ 语言的实现代码：
```cpp
#include <iostream.h>
typedef char elemtype;
struct bitree{
elemtype data;
bitree *lchild,*rchild;
};
bitree *create()
{
bitree *q[100];
bitree *s;
bitree *root;
int front=1,rear=0;
char ch;
root=NULL;
cout<<"请输入结点值（不存在的结点用‘，’表示，‘#’表示结束）"<<endl;
cin>>ch;
while(ch!='#')
{
s=NULL;
if(ch!=',')
{
s=new bitree;
s->data=ch;
s->lchild=NULL;
s->rchild=NULL;
}
rear++;
q[rear]=s;
if(rear==1)root=s;
else
{
if((s!=NULL)&&(q[front]!=NULL))
{
if(rear%2==0)
q[front]->lchild=s;
else
q[front]->rchild=s;
}
if(rear%2==1)front++;
}
cin>>ch;
}
return root;
}
void lorder(bitree *t)
{
bitree *q[100],*p;
int f,r;
q[1]=t;
f=r=1;
cout<<"按层次遍历二叉树的结果为：";
while (f<=r)
{
p=q[f];
f++;
cout<<p->data<<" ";
if(p->lchild!=NULL)
{
r++;
q[r]=p->lchild;
}
if(p->rchild!=NULL)
{
r++;
q[r]=p->rchild;
}
}
cout<<endl;
}
void main()
{
bitree *t;
t=create();
lorder(t);
}
```
在上面的代码中，我们首先定义了一个结构体 `bitree`，它包含数据域和两个指针域，分别指向左孩子和右孩子。然后，我们实现了建立二叉链表的函数 `create()`，它可以输入结点值并建立一个完全二叉树。我们实现了层次遍历的函数 `lorder()`，它可以输出二叉树的层次遍历结果。
