二叉树遍历 - 数据结构

黄规速

发布于 2022-04-14 20:53:04

2740

发布于 2022-04-14 20:53:04

文章被收录于专栏：架构师成长之路架构师成长之路

1. 二叉树遍历

1.1 遍历算法：

1．先序遍历的递归算法定义：(也叫做先根遍历、前序遍历 ) . 若二叉树非空，则依次执行如下操作：

(1) 访问根结点； (2) 遍历左子树； (3) 遍历右子树。

上图所示二叉树的遍历结果是：ABDECF

2．中序遍历的递归算法定义：若二叉树非空，则依次执行如下操作：

(1)遍历左子树； (2)访问根结点； (3)遍历右子树。

上图所示二叉树的遍历结果是：DBEAFC

3．后序遍历得递归算法定义：若二叉树非空，则依次执行如下操作：

(1)遍历左子树；(2)遍历右子树；(3)访问根结点。

上图所示二叉树的遍历结果是：DEBFCA

4．层次遍历：层序遍历（level traversal）二叉树的操作定义为：

若二叉树为空，则退出，否则，

按照树的结构，从根开始自上而下，自左而右访问每一个结点，从而实现对每一个结点的遍历

例子：表达式a + b × (c- d)- e/ f

先序遍历：- + a * b - c d / e f

中序遍历：a + b * c - d- e / f

后续遍历：a b c d - × + e f /-

1.2遍历算法实现：

基本操作实现 stdafx.h：

// stdafx.h : include file for standard system include files,
// or project specific include files that are used frequently, but
// are changed infrequently
//

#pragma once

#include <stdio.h>  
#include "stdlib.h"
#include <iostream>
using namespace std;


//宏定义    
#define TRUE   1    
#define FALSE   0    
#define OK    1    
#define ERROR   0  
#define INFEASIBLE -1    
#define OVERFLOW -2  
#define STACKEMPTY -3 
#define QUEUEEMPTY  -3    

#define MAX 10 // MAXIMUM STACK CONTENT  
#define MAX_QUEUE 10 // MAXIMUM QUEUE CONTENT  

typedef int Status;    
typedef char ElemType;  


//而二叉树
typedef struct BitNode{
	ElemType data;
	Status visited;
	struct BitNode *lchild, *rchild; //左右孩子指针
}BitNode, *BiTree;

typedef BiTree StackElemType;  
typedef BiTree QueueElemType;  

class stack     
{     
private:     
	StackElemType arr[MAX];   
	int top;   
public:     
	stack()   
	{     
		inItStack();   
	}  
	/************************************************************************/  
	/* 初始化栈                                                                     */  
	/************************************************************************/  
	void inItStack()   
	{   
		top=-1;   
	}   
	/************************************************************************/  
	/* 入栈                                                                     */  
	/************************************************************************/  
	void push(StackElemType a)   
	{     
		top++;  
		if(top < MAX)  {     
			arr[top] = a;   
		}   else   {     
			cout<<"STACK FULL!!"<<top;     
		}     
	}     
	/************************************************************************/  
	/* 出栈                                                                     */  
	/************************************************************************/  
	StackElemType pop()  
	{      
		if(isEmpty())   {     
			cout<<"STACK IS EMPTY ";  
			return NULL;     
		} else {     
			StackElemType data=arr[top];   
			arr[top] = NULL;   
			top--;  
			return data;   
		}     
	}     

	/************************************************************************/  
	/* 出栈                                                                     */  
	/************************************************************************/  
	StackElemType getTop()  
	{      
		if(isEmpty())   {     
			cout<<"STACK IS EMPTY ";  
			return NULL;     
		} else {     
			return arr[top];   
		}    
	}     
	/************************************************************************/  
	/* 是否为空                                                                     */  
	/************************************************************************/  
	bool isEmpty()  
	{  
		if(top == -1) return true;  
		else return false;  
	}  
};     


class queue {
private:
	QueueElemType   elem[MAX_QUEUE] ;     ///假设当数组只剩下一个单元时认为队满            
	int front;      //队头指针  
	int rear;       //队尾指针    
public:     
	/************************************************************************/  
	/*  
	  初始化 
	  直接使用结构体指针变量，必须先分配内存地址，即地址的指针 
	*/  
	/************************************************************************/  
	void InitQueue()   
	{  
		front = rear = -1;  
	  
	}  
	/************************************************************************/  
	/*     入队                                                               
	*/  
	/************************************************************************/  
	   
	void EnQueue(QueueElemType e)  
	{  
		if((rear+1)% MAX_QUEUE == front) exit(OVERFLOW);  
		rear = (rear + 1)% MAX_QUEUE;  
		elem[rear] = e;   
	}  
	/************************************************************************/  
	/*     出队                                                                
	*/  
	/************************************************************************/  
	QueueElemType DeQueue()  
	{  
		if (QueueEmpty())  exit(QUEUEEMPTY);  
		front =  (front+1) % MAX_QUEUE;  
		return elem[front];  
	}  
	/************************************************************************/  
	/*    获取队头元素内容                                                             
	*/  
	/************************************************************************/  
	  
	QueueElemType GetFront()   
	{  
		if ( QueueEmpty() )  exit(QUEUEEMPTY);  
		return elem[ (front+1) % MAX_QUEUE ];  
	}  
	/************************************************************************/  
	/*    判断队列Q是否为空                                                              
	*/  
	/************************************************************************/  
	int QueueEmpty()  
	{  
		if( front==rear) return TRUE;  
		else return FALSE;  
	}  

};

二叉树遍历

/ Test.cpp : Defines the entry point for the console application.  
//  
#include "stdafx.h"  



/************************************************************************/
/* 算法：
*/
/************************************************************************/

Status CreateBiTree(BiTree &T);
Status PreOrderTraverse(BiTree &T) ;
Status visit(BiTree &T);

/************************************************************************/
/* 先序生成二叉树:
   由于使用递归，要想退出函数，输入#的个数跟树的深度有关系
*/
/************************************************************************/
Status CreateBiTree(BiTree &T) {

	char data ;
	//scanf("%d", &data);
	cin>> data;
	if ( '#' == data )  T = NULL; //空格没法读入，所以使用#
	else{
		T = (BiTree) malloc(sizeof(BitNode));
		if (!T) exit(OVERFLOW);
		T->data =  data;
		CreateBiTree(T->lchild);
		CreateBiTree(T->rchild);
	}
	return OK;
}

/************************************************************************/
/* 先序递归遍历二叉树:
*/
/************************************************************************/
Status PreOrderTraverse(BiTree &T) {
	if(T) {
		if(visit(T) )
		if(PreOrderTraverse(T->lchild) )
		if(PreOrderTraverse(T->lchild) ) return OK;
		return ERROR;
	}
	return OK;
}
/************************************************************************/
/* 先序序循环遍历二叉树:
*/
/************************************************************************/
Status PreOrderTraverse_for(BiTree &T) {
	BiTree root;
	stack s;
	s.inItStack();
	root = T;
	while(root || !s.isEmpty()) {
		if(root) {
			visit(root);
			s.push(root);
			root = root->lchild;
		} else {
			root = s.getTop();
			s.pop();
			root = root->rchild;
		}
	}
	return OK;
}

/************************************************************************/
/*  层序遍历二叉树:
*/
/************************************************************************/

void LevelOrderTraverse(BiTree T)
{
	BiTree root,TNode;
	queue q;
	root = T;
	if(!root) exit(ERROR);
	q.EnQueue(root);
	while (!q.QueueEmpty())
	{
		TNode = q.DeQueue();
		visit(TNode);
		if (TNode->lchild) q.EnQueue(TNode->lchild);    
		if (TNode->rchild) q.EnQueue(TNode->rchild);    

	}
}



Status visit(BiTree &T){
	if(T->visited != TRUE) {
		T->visited = TRUE;
		cout<<T->data;
		return TRUE;
	}
	return FALSE;
}


void main(){
	int pos =1 ;
	BiTree T;
	cout<<"- + a * b - c d / e f\n";
	CreateBiTree( T);
	//PreOrderTraverse(T);
	//PreOrderTraverse_for(T);
	LevelOrderTraverse(T);
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2012-06-21 ，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

二叉树

编程算法

登录后参与评论

0 条评论

热度