博客

二叉树遍历基本定义

是指从根节点出发，按照某种次序依次访问二叉树中所有节点，使得每个节 点被访问一次且仅被访问一次。

访问：简单的说就是输出节点的数据信息

节点：树的节点之间不存在唯一的前驱和后继关系，选择方式不同，遍历次序不同。

遍历方法

前序遍历

先访问根节点，再前序访问左子树，再前序访问右子树

中序遍历

先中序访问左子树，再访问根节点，再中序访问右子树

后序遍历

先后续访问左子树，再后续访问右子树，再访问根节点

层序遍历

从根节点访问，从上而下逐层遍历，从左到右对每层节点逐个访问

遍历目的

树是非线性结构，而计算机存储是线性序列，遍历就是把树中的节点变成某种意义上的线性序列。

遍历算法

前序遍历

/*二叉树的前序遍历递归算法*/
void PreOrderTraverse(BiTree t)
{
	if(NULL == T)
		return;
	printf("%c",T->data);		//先访问根节点
	PreOrderTree(T->lchild);	//再前序访问左子树
	PreOrderTree(T->rchild);	//再前序访问右子树
}

中序遍历

/*二叉树的中序遍历递归算法*/
void InOrderTraverse(BiTree T)
{
	if(NULL == T)
		return;
	InOrderTree(T->lchild);		//先中序访问左子树
	printf("%c",T->data);		//再访问根节点
	InOrdertree(T->rchild);		//再中序访问右子树
}

后序遍历

/*二叉树的后序遍历递归算法*/
 void PostOrderTraverse(BiTree T)
 {
 	if(NULL == T)
 		return;
 	PostOrederTree(T->lchild);		//先后序访问左子树
 	PostOrederTree(T->rchild);		//再后序访问右子树
 	printf("%c",T->data);			//再访问根节点
 }
 

推导遍历结果

结论：

已知前序遍历和中序遍历，可以唯一确定一颗二叉树

已知后序遍历和中序遍历，可以唯一确定一颗二叉树

但是已知前序遍历和后序遍历是无法唯一确定一颗二叉树的

二叉树的建立

二叉树的建立也是利用了递归的原理，只不过在原来打印的地方改成了生成节点、给节点赋值的操作而已。

/*按前序输入二叉树中节点的值*/
/*#表示空树，构造二叉链表表示二叉树T*/
void CreateBiTree(BiTree *T)
{
	char ch;
	scanf("%c",&ch);
	if('#'==ch)
		*T = NULL;
	else
	{
		BiTree *T = (BiTree)malloc(sizeof(BiTNode));
		if(!*T)
			exit(-1);
		{
			(*T)->data = ch;		//先生成根节点
			CreateBiTree(&(*T)->lchild));	//在生成左子树
			CreateBiTree(&(*T)->rchild));	//再生成右子树
		}
	}
}

运行结果：