二叉树的遍历总结

快来打我* 2022-04-01 15:18 175阅读 0赞

#  二叉树的遍历总结 #

## 1. 前言 ##

总结了总结关于二叉树的遍历问题包括递归的和非递归的形式。后序遍历的非递归算法真的是。。。

有关树的节点的定义如下

typedef struct node
    {
        
    	int data;
    	struct node* lchild;
    	struct node* rchild;
    }node,*pnode;

## 2.递归形式 ##

递归形式的二叉树遍历算法相对而言，就很简单，只需要把相应的输出放在正确的位置上就可以了。直接上代码

void preorder1(pnode root)//递归形式
    {
    	if (root == NULL)
    		return;
    	printf("%d", root->data);
    	preorder1(root->lchild);
    	preorder1(root->rchild);
    }
    
    void in_order1(pnode root)//递归形式
    {
    	if (root == NULL)
    		return;
    	in_order1(root->lchild);
    	printf("%d", root->data);
    	in_order1(root->rchild);
    }
    
    void post_order(pnode root)
    {
    	if (root == NULL)
    		return;
    	post_order(root->lchild);
    	post_order(root->rchild);
    	printf("%d", root->data);
    }

以上就是递归形式的代码，不做过多的解释了

## 3.非递归形式 ##

### 3.1前序遍历 ###

前序遍历的思路

1.搜索当前节点的左孩子并输出压栈

2.当前节点无左孩子时开始弹栈，如果栈中节点没有右孩子，继续弹栈

3.以节点的右孩子作为当前节点重复1-3；

void preoder(pnode root)//非递归前序遍历
    {
        
    	const int maxn = 105;
    	pnode stack[maxn];//建栈
    	int top =-1;
    	pnode pnew = root;
    	top++;
    	stack[top] = root;
    	printf("%d", pnew->data);
    	pnew = pnew->lchild;
    	while(1)
    	{
        
    		while(pnew!=NULL)
    		{
        
    			printf("%d", pnew->data);
    			top++;
    			stack[top] = pnew;
    			pnew = pnew->lchild;
    		}
    		pnew = stack[top];
    		while (pnew->rchild == NULL&&top>=0)
    		{
        
    			top--;
    			if (top < 0)
    				break;
    			pnew = stack[top];
    		}
    		if (top>=0)
    		{
        
    			pnew = pnew->rchild;
    			top--;
    		}
    		else
    		break;
    	}
    }

### 3.2中序遍历 ###

其实中序遍历的思想与前序遍历的思想基本相同。

1.沿着当前节点的左节点一直向下搜索，并入栈，此时不输出

2.开始弹栈，弹栈的时候输出，如果弹出的节点没有右节点就一直弹栈

3.如果有右节点就以右节点作为当前节点从1-3重复进行

void in_order(pnode root)//中序遍历
    {
        
    	pnode stack[105];
    	int top = -1;
    	top++;
    	stack[top] = root;
    	pnode pnew = root;
    	pnew = pnew->lchild;
    	while(1)
    	{
        
    		while(pnew!=NULL)
    		{
        
    			top++;
    			stack[top] = pnew;
    			pnew = pnew->lchild;
    		}
    		pnew = stack[top];
    		printf("%d", pnew->data);
    		while(pnew->rchild==NULL)
    		{
        
    			top--;
    			if (top < 0)
    				break;
    			pnew = stack[top];
    			printf("%d", pnew->data);
    		}
    		if (top < 0)
    		break;
    		top--;
    		pnew = pnew->rchild;
    	}
    }

### 3.3后序遍历 ###

后序遍历的思路是

1.从当前节点开始每个节点都入栈两次

2.每一次弹栈的时候，判断栈顶元素是否与弹出的相同，如果相同那么证明这个节点还有左右孩子没有入栈（如果有左右孩子的话），将左右孩子入栈，此时先入右孩子后入左孩子（后序遍历的顺序）

3.如果不同那么就直接输出该节点的值

void post_order1(pnode root)
    {
        
    	stack<pnode> a;
    	a.push(root);
    	a.push(root);
    	while(!a.empty())
    	{
        
    		pnode pnew = a.top();
    		a.pop();
    		if(!a.empty()&&pnew==a.top())
    		{
        
    			if (pnew->rchild)
    			{
        
    				a.push(pnew->rchild);
    				a.push(pnew->rchild);
    			}
    			if(pnew->lchild)
    			{
        
    				a.push(pnew->lchild);
    				a.push(pnew->lchild);
    			}
    		}
    		else
    		{
        
    			printf("%d", pnew->data);
    		}
    	}
    
    }

## 4.小结 ##

前序遍历和中序遍历的思想大致相同，也算是比较好理解的。相对而言后序的就有点emmm。自己要多动手去实践，多动手去实现才能掌握的更好一点。?