树其实就是一个有n个节点的有限集合,二叉树是树的一种特殊形式,通过树结构可以让我们去解决查找及其排序的一些问题。有关树结构,最主要的就是二叉树的遍历与排序了。
其中二叉树的遍历又分为三种操作,先序遍历,中序遍历和后序遍历,但是其实只是把需要进行的操作顺序改变一下,原理基本没有变化,还有第四种操作就是层序遍历。以下是先序遍历创建二叉树的代码:
<code lang="c++">
void CreateBiTree(BiTree *T)
{
    char ch;
    cin >> ch;
    if (ch == '#')
        *T = NULL;  //保证是叶结点
    else
    {
        *T = (BiTree)malloc(sizeof(BiTNode));
        //if (!*T)
        //exit(OVERFLOW); //内存分配失败则退出。
        (*T)->data = ch;//生成结点
        CreateBiTree(&(*T)->lchild);//构造左子树
        CreateBiTree(&(*T)->rchild);//构造右子树
    }
}
</code>
再接下来是二叉树遍历的代码:
<code lang="c++">
void PreOrderTraverse(BiTree T, int level)
{
    if (T == NULL)
        return;
    /*此处表示对遍历的树结点进行的操作,根据你自己的要求进行操作,这里只是输出了结点的数据*/
    //operation1(T->data);
    operation2(T->data, level); //输出了层数
    PreOrderTraverse(T->lchild, level + 1);
    PreOrderTraverse(T->rchild, level + 1);
}
</code>
其中,operation是指当访问结点时,对结点的操作。
二叉树是的先序遍历是用递归函数去实现对二叉树的遍历与创建。
接下来是二叉树的层序遍历,二叉树的层序遍历需要借助一个队列来进行节点暂时的存储,这个队列需要是BiTree类型的队列,可以借助二叉树的结构体。
二叉树节点结构体如下:
<code lang="c++">
struct BiTree
{
    char data;
    BiTree *lchild,*rchild;
};
</code>
二叉树层序遍历的函数如下:
<code lang="c++">
void LevelOrder(BiTree root)
{
    BiTree Q[100],q;
    int front,rear;
    if(root==NULL) return;
    Q[++rear]=root; //将根节点入队
    while(front!=rear){ //利用循环进行遍历
      q=Q[++front]; //将队首元素出队
      visit(q->data); //访问节点
      if(q->lchild!=NULL) Q[++rear]=q->lchild; //将左孩入队
      if(q->rchild!=NULL) Q[++rear]=q->rchild; //将右孩入队
}
</code>
还有一个线索二叉树,可以说是二叉树的升级版,主要是因为一般二叉树遍历易于查找孩子而不易查找双亲,而且二叉树如果只有n个节点,则会浪费n+1个指针域空间,为此,增加了两个线索参数,ltag,rtag,特意用来判断指针域指示节点是否还有孩子,如果有则ltag/rtag = 0 ,否则为1,若为1,则把节点相应的指针域指向节点的前驱,表示如下:
ltag = 0  lch域指示节点的左孩子
ltag = 1  lch域指示节点的前驱
对于树,有些树不知有两个孩子,要将其转化成二叉树更方便理解与计算,于是就有了孩子兄弟表示法,即左子树为孩子,右子树为兄弟。