二叉樹的遍歷

1、定義

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

2、遍歷算法

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

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

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

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

? ? ? ? ? ??

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

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

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

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

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

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

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

--4）層序遍歷

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

的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問。上圖所示二叉樹的層序遍歷結(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);
	}
}
//二叉樹的葉子節(jié)點(diǎn)數(shù)
int?leaf(BNode?*?root)
{
	if(root==NULL)??//空樹
		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ù)
	R?=?leaf(root->rchild);?//統(tǒng)計(jì)右子樹的葉子數(shù)
	return?L+R;
}