1、定義

---- 二叉樹(shù)的遍歷（traversing binary tree）是指從根結(jié)點(diǎn)出發(fā)，按照某種次序依次訪問(wèn)二叉樹(shù)中所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)被訪問(wèn)一次且僅被訪問(wèn)一次。

2、遍歷算法

---- 限定先左結(jié)點(diǎn)后右結(jié)點(diǎn)后，主要的遍歷算法分為四種：

--1）前序遍歷（根結(jié)點(diǎn)--左子樹(shù)--右子樹(shù)）

規(guī)則是若二叉樹(shù)為空，則空操作返回，否則先訪問(wèn)根結(jié)點(diǎn)，然后前序遍歷左子樹(shù)，再前序遍歷右子樹(shù)。

如下圖所示的二叉樹(shù)，前序遍歷結(jié)果是：ABDECF

? ? ? ? ? ??

--2）中序遍歷（左子樹(shù)--根結(jié)點(diǎn)--右子樹(shù)）

規(guī)則是若樹(shù)為空，則空操作返回，否則從根結(jié)點(diǎn)開(kāi)始（注意并不是先訪問(wèn)根結(jié)點(diǎn)），中序遍歷根結(jié)點(diǎn)的左子樹(shù)，然后是訪問(wèn)

根結(jié)點(diǎn)，最后中序遍歷右子樹(shù)。

上圖所示二叉樹(shù)的中序遍歷結(jié)果是：DBEAFC

--3）后序遍歷（左子樹(shù)--右子樹(shù)--根結(jié)點(diǎn)）

規(guī)則是若樹(shù)為空，則空操作返回，否則從左到右先遍歷左子樹(shù)，再遍歷左子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)。

上圖所示二叉樹(shù)的后序遍歷結(jié)果是：DEBFCA

--4）層序遍歷

規(guī)則是若樹(shù)為空，則空操作返回，否則從樹(shù)的第一層，也就是根結(jié)點(diǎn)開(kāi)始訪問(wèn)，從上而下逐層遍歷，在同一層中，按從左到右

的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問(wèn)。上圖所示二叉樹(shù)的層序遍歷結(jié)果是：ABCDEF

具體算法如下：

#includeusing?namespace?std;

typedef?int?TElemType;
typedef?struct?BTNode?//結(jié)點(diǎn)結(jié)構(gòu)
{
	TElemType?data;//結(jié)點(diǎn)數(shù)據(jù)
	struct?BTNode?*lchild,*rchild;?//左右孩子指針
}BNode,*BTree;
//前序遍歷
void?preorder(BNode?*?root)
{
	if(root!=NULL)
	{
		printf("%d",root->data);
		preorder(root->lchild);
		preorder(root->rchild);
	}
}
//中序遍歷
void?inorder(BNode?*?root)
{
	if(root!=NULL)
	{
		inorder(root->lchild);
		printf("%d",root->data);
		inorder(root->rchild);
	}
}
//后序遍歷
void?postorder(BNode?*?root)
{
	if(root!=NULL)
	{
		postorder(root->lchild);
		postorder(root->rchild);
		printf("%d",root->data);
	}
}
//二叉樹(shù)的葉子節(jié)點(diǎn)數(shù)
int?leaf(BNode?*?root)
{
	if(root==NULL)??//空樹(shù)
		return?0;
	int?L,R;
	if(root->lchild==NULL?&&?root->rchild==NULL)??//葉子結(jié)點(diǎn)
		return?1;
	L?=?leaf(root->lchild);?//統(tǒng)計(jì)左子樹(shù)的葉子數(shù)
	R?=?leaf(root->rchild);?//統(tǒng)計(jì)右子樹(shù)的葉子數(shù)
	return?L+R;
}