二叉树遍历 - 数据结构

川长思鸟来 2022-06-10 01:13 188阅读 0赞

## 1. 二叉树遍历 ##

--------------------

### 1.1 遍历算法： ###

![20191129184030632.png][]

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

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

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

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

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

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

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

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

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

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

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

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

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

![20191129183909575.png][]

先序遍历：**-** \+ 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);
    }

[20191129184030632.png]: /images/20220610/29f1a24106af4a2d8bd8daa6d369450c.png
[20191129183909575.png]: /images/20220610/d19450d69ab04642bfee7368edb881ee.png