《数据结构》二叉树的存储结构，遍历以及建立2019/10/16

存储结构

二叉树的顺序存储结构一般只用于完全二叉树（其他的二叉树结构会造成存储空间的浪费），因为对于一般二叉树，层序编号不能反应其逻辑关系，需要把不存在的结点设置成“#”，如果该二叉树为深度为K的右斜树，那么空间会有很大的浪费。所以链式存储结构适用面更广。

二叉链表

一个数据域，两个指针域：左孩子域和右孩子域。
代码如下：

typedef struct BinTNode
{
	TElemType data;
	struct BinTNode *lchild,*rchild;
} BinTNode,*BinTree;

或者：

typedef struct TNode * Position;
typedef Position BinTree;
struct TNode{
	TElemType data;
	BinTree lchild;
	BinTree rchild;
};	

二叉树的遍历

其实二叉树的遍历思想主要就在于其访问结点的次序。遍历一棵树，不管是哪种遍历方法，都是按如下顺序走完一遍：

其中前序遍历方法为：第一次遇见该结点时就访问之。如上图前序遍历就是按标号为1的顺序访问：ABDGHCEIF
而中序遍历为：第二次遇见该结点时访问之。上图标号为2的顺序：GDHBAIECF
同样后序遍历就很简单了：最后遇见时访问即可，标号为3：GHDBIEFCA

还有一种：层序遍历：从上而下逐层遍历即可：ABCDEFGHI

这几种遍历方法都是把树中的结点变成某种意义上的线性序列，方便计算机处理。

遍历算法

1）前序
代码如下：

void PreOrderTraverse(BinTree T)
{
	if(T==NULL)
		return;
	printf("%c",T->lchild);
	PreOrderTraverse(T->lchild);
	PreOrderTraverse(T->rchild);
}

2）中序
只需要调整一下访问语句（本处设为打印操作）
代码如下：

void InOrderTraverse(BinTree T)
{
	 if(T==NULL)
  		return;
	 InOrderTraverse(T->lchild);
	 printf("%c",T->lchild);
 	 InOrderTraverse(T->rchild);
}

3)后序
同样的：

void PostOrderTraverse(BinTree T)
{
  	if(T==NULL)
    		return;
  	PostOrderTraverse(T->lchild);
 	 PostOrderTraverse(T->rchild);
  	printf("%c",T->lchild);
}

二叉树的建立

如果我们单纯的输入一串字符：ABCDEF，我们无法确定这棵树的逻辑结构。但是如果我们对它进行扩展：将二叉树中的每一个结点的空指针引出一个虚结点，它的值是一个特定值，可以设为“#”，这样处理过的二叉树被称为扩展二叉树，他可以做到一个遍历序列就可以确定一颗二叉树，比如：AB#D##C##（前序序列）。
这样，我们就可以来建立一个二叉树了：

void CreateBinTree(BinTree *T)
{    TElementTyp ch;
     scanf ("%c",&ch);
     if(ch=='#')
             *T=NULL;    
     else    
     {        
     	*T=(BinTree)malloc(sizeof(BinTNode));        
     	if(!*T)            
    		exit(OVERFLOW);        
     	(*T)->data=ch;       
      	CreateBinTree(&(*T)->lchild);        
      	CreateBinTree(&(*T)->rchild);    
     }
}

可以发现，创建二叉树的过程同样利用到了递归。与二叉树的遍历相比较的话，相当于把打印操作替换成了生成结点空间和给结点赋值的操作。