二叉樹的遍歷

1、定義

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

2、遍歷算法

---- 限定先左結點后右結點后，主要的遍歷算法分為四種：

--1）前序遍歷（根結點--左子樹--右子樹）

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

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

? ? ? ? ? ??

--2）中序遍歷（左子樹--根結點--右子樹）

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

根結點，最后中序遍歷右子樹。

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

--3）后序遍歷（左子樹--右子樹--根結點）

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

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

--4）層序遍歷

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

的順序對結點逐個訪問。上圖所示二叉樹的層序遍歷結果是：ABCDEF

具體算法如下：

#includeusing?namespace?std;

typedef?int?TElemType;
typedef?struct?BTNode?//結點結構
{
	TElemType?data;//結點數(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é)點數(shù)
int?leaf(BNode?*?root)
{
	if(root==NULL)??//空樹
		return?0;
	int?L,R;
	if(root->lchild==NULL?&&?root->rchild==NULL)??//葉子結點
		return?1;
	L?=?leaf(root->lchild);?//統(tǒng)計左子樹的葉子數(shù)
	R?=?leaf(root->rchild);?//統(tǒng)計右子樹的葉子數(shù)
	return?L+R;
}