遍历二叉树（数据结构，递归）

偏执的太偏执、 2022-06-09 06:56 196阅读 0赞

在二叉树的应用中，常常要求在树中查找具有某种特征的结点，或者对全部结点逐一进行某种处理。这就是二叉树的遍历问题。所谓二叉树的遍历是指按一定的规律和次序访问树中的各个结点，而且每个结点仅被访问一次。“访问”的含义很广，可以是对结点作各种处理，如输出结点的信息等。遍历一般按照从左到右的顺序，共有3种遍历方法，先（根）序遍历，中（根）序遍历，后（根）序遍历。

先序：根、左、右；

中序：左、根、右；

后序：左、右、根。

# 1. 先序遍历的操作定义如下： #

若二叉树为空，则空操作，否则

①访问根结点

②先序遍历左子树

③先序遍历右子树

void preorder(tree bt)//先序遍历根节点为bt的二叉树算法
    {
    	if(bt)
    	{
    		cout<<bt->data;
    		preorder(bt->lchild);
    		preorder(bt->rchild);
    	}
    }

栈：先进后出

void preorder(tree bt)//先序遍历bt所指的二叉树 
    {
    	tree stack[n];//栈 
    	int top=-1;//栈顶指针
    	tree P;
    	while(bt||top)
    	{
    		while(bt)//非叶节点
    		{
    			cout<<bt->data;
    			stack[++top]=bt->rchild;//右子树压栈
    			bt=bt->lchild;//遍历左子树 
    		} 
    		if(top)//栈中所有元素出栈 
    		{
    			bt=stack[top--];
    		} 
    	} 
    	 
    }

![20170830154634163][]

先序遍历此图的结果为：124753689

# 2. 中序遍历的操作定义如下： #

若二叉树为空，则空操作，否则

①中序遍历左子树

②访问根结点

③中序遍历右子树

void inorder(tree bt)//中序遍历根节点为bt的二叉树的递归算法
    {
    	if(bt)
    	{
    		inorder(bt->lchild);
    		cout<<bt->data;
    		inorder(bt->rchild);
    	}
    }

![20170830154911901][]

中序遍历此图的结果为：742513869

# 3. 后序遍历的操作定义如下： #

若二叉树为空，则空操作，否则

①后序遍历左子树

②后序遍历右子树

③访问根结点

void posorder(tree bt)//后序遍历根节点为bt的二叉树的递归算法
    {
    	if(bt)
    	{
    		posorder(bt->lchild);
    		posorder(bt->rchild);
    		cout<<bt->data; 
    	}
    }

![20170830154911901][]

后序遍历此图的结果为：745289631

[20170830154634163]: /images/20220609/1d58a197947743789320df098375e354.png
[20170830154911901]: /images/20220609/c82fe9d890b4478596238d7eff47b02f.png