树与二叉树

树其实就是一个有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域指示节点的前驱
对于树，有些树不知有两个孩子，要将其转化成二叉树更方便理解与计算，于是就有了孩子兄弟表示法，即左子树为孩子，右子树为兄弟。