《数据结构与算法》——树与二叉树之遍历总结

不念不忘少年蓝@ 2021-11-01 12:34 340阅读 0赞

# 《数据结构与算法》——树与二叉树之遍历总结 #

树与二叉树部分计划分为三次进行复习总结，第一次为**基本概念和二叉树的遍历**，第二次内容为**线索二叉树以及树和森林，**第三次为**树与二叉树的应用**。

树的基本概念

二叉树的基本概念

二叉树的存储结构

二叉树的遍历

方法声明

先序遍历·递归（PreOrder）

中序遍历.递归（InOrder）

后续遍历.递归（PostOrder）

层次遍历·递归（LevelOrder）

先序遍历·非递归（PreOrder2）

中序遍历.非递归（InOrder2）

☆后续遍历.非递归（PostOrder2）（较难）

层次遍历·非递归（LevelOrder2）

测试代码

参考文献

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

## 树的基本概念 ##

**树**：N个结点的有限集合。（N≥0）

**空树**：没有结点的集合即N=0。

在任何一个非空树中应满足以下条件：

1.有且仅有一个特定的被称为**根**的结点。

2.当N>1时，其余节点可分为m(m>0)个互不相交的有限集合T1,T2,T3……,Tm，其中每个集合均为一棵树，称为根结点的**子树**。

**结点的度：**一个结点的子结点的个数被称为该结点的度，最大的度被称为**树的度**。

**结点的高度**：从叶结点开始自底向上逐层累加。

**结点的深度**：从根节点开始自顶向下逐层累加。

**结点的层次**：树根为第一层，依次向下。

**树的高度（深度）**：树中结点的最大层数。

**有序树和无序树**：有序树中一个结点的子节点是依次从左向右排列，并且之间有某种关联存在，交换顺序则发生改变；无序树中结点的子结点无谓排列顺序，之间的关联度不大。

**路径**：两个结点之间的结点序列，不包括两个端点。

**路径长度**：两个节点之间的边数。

**森林**：多棵树的集合。

**树的性质：**

1.结点数=所有结点的度数+1；

2.度为m的树中最多有m^(i-1)个结点；

3.**高度为h****的m****叉树中最多有(m^h-1)/(m-1)****个结点；**

4.**具有n****个结点的m****叉树的最小高度为\{Logm\[n\*(m-1)+1\]\}****向上取整。**

## 二叉树的基本概念 ##

**二叉树**：树形结构，每个结点最多有两个子结点，并且有左右之分，次序不可颠倒。

**二叉树与度为2****的树的区别**：度为2的树至少有3个结点（根左右），二叉树可以为空；度为2的有序树某一结点如果只有一个子结点那么其无谓左右顺序，而二叉树无论有无结点，或一个结点其均有序。

**满二叉树**：一棵高度为h，结点个数为2^h-1的树被称为满二叉树。

**完全二叉树**：一棵高度为h，结点个数为n的树，当且仅当结点从左至右，从上至下排列时被称为完全二叉树。

**二叉排序树：**一棵空二叉树或者具有以下性质的二叉树：对于每一个节点，左.key<中.key <右.key。

**平衡二叉树**：任一结点的左子树和右子树的深度之差不超过1。

**二叉树的性质**：易。

## 二叉树的存储结构 ##

二叉树的存储结构分为顺序存储结构和链式存储结构。

**顺序存储结构**：从**下标为****1**的数组中开始按层存储，例如：1 23 4567 891011 ……存取方便，但空间利用率低，遇到无值的左右节点仍需补0填充。

**链式存储结构**：每个树结点利用链表中的一个链结点来存储。

typedef struct BiTNode{
    Elemtype data;
    struct BiTNode *lchild,*rchild;
    } BiTNode,* BiTree;

**//****这种写法在c++11****标准里可以用，意思是BiTNode ==** struct BiTNode ，**\* BiTree ==** struct BiTNode\* ，即可以直接用BiTNode,\* BiTree来声明变量。

不难发现，每个结点都会有两个指针和一个数据，但并不是每个结点都会有一个或两个子结点，那么这些空节点就会白白浪费掉，对此我们有了一个新的结构概念——线索链表。

## 二叉树的遍历 ##

二叉树在存储上是一种很方便的结构，所以对于它遍历算法的学习是很有必要的，它对于后面的学习起着一定的基础作用，譬如后面学习的图的遍历等。

二叉树在遍历上分为前中后序、层次四种遍历，在实现上分为递归和非递归两种。即本小节总共会有八个遍历算法出现。在此我们使用的是：普通的二叉树（任意一棵二叉树）、链式存储结构。

### 方法声明 ###

BiTree creatBiTree(Elemtype tree[] , int n , int num );//使用顺序存储结构建立链式存储结构二叉树 
    
    void visit(BiTree b);//访问结点
    
    void PreOrder(BiTree T);//先序遍历·递归（PreOrder）
    
    void InOrder(BiTree T);//中序遍历.递归（InOrder）
    
    void PostOrder(BiTree T);//后序遍历.递归（PostOrder）
    
    void LevelOrder(queue<BiTree> qt);//层次遍历.递归（LevelOrder）
    
    void PreOrder2(BiTree T);//先序遍历·非递归（PreOrder2）
    
    void InOrder2(BiTree T);//中序遍历.非递归（InOrder2）
    
    void PostOrder2(BiTree T);//后序遍历.非递归（PostOrder2）
    
    void LevelOrder2(BiTree T);//层次遍历.非递归（LevelOrder2）

### 先序遍历·递归（PreOrder） ###

void PreOrder(BiTree T){//先序遍历·递归（PreOrder）
    	//cout<<(T==0)<<endl;
    	if(T){
    		visit(T);
    		//cout<<555<<endl;
    		PreOrder(T->lchild);
    		PreOrder(T->rchild);
    	}
    }

### 中序遍历.递归（InOrder） ###

void InOrder(BiTree T){//中序遍历.递归（InOrder）
    	if(T){
    		InOrder(T->lchild);
    		visit(T);
    		InOrder(T->rchild);
    	}
    }

### 后续遍历.递归（PostOrder） ###

void PostOrder(BiTree T){//后序遍历.递归（PostOrder）
    	if(T){
    		PostOrder(T->lchild);
    		PostOrder(T->rchild);
    		visit(T);
    	}
    }

### 层次遍历·递归（LevelOrder） ###

void LevelOrder(queue<BiTree> qt){//层次遍历.递归（LevelOrder）
    	if(!qt.empty()){
    		BiTree T = qt.front();
    		visit(T);
    		qt.pop();
    		if(T->lchild)
    			qt.push(T->lchild);
    		if(T->rchild)
    			qt.push(T->rchild);	
    		LevelOrder(qt);	
    	} 
    }

### 先序遍历·非递归 ###

void PreOrder2(BiTree T){//先序遍历·非递归（PreOrder2）
    	stack<BiTree> st;
    	BiTree temp = T;
    	while(temp||!st.empty()){//栈不空或者指针不空时 
    		if(temp){
    			visit(temp);
    			st.push(temp);
    			temp = temp->lchild;
    		}else{
    			temp = st.top()->rchild;
    			st.pop();
    		}
    	}
    }

### 中序遍历.非递归 ###

void InOrder2(BiTree T){//中序遍历.非递归（InOrder2）
    	stack<BiTree> st;
    	BiTree temp = T;
    	while(temp||!st.empty()){
    		if(temp){
    			st.push(temp);
    			temp = temp->lchild;
    		}else{
    			temp = st.top();
    			st.pop();
    			visit(temp);
    			temp = temp->rchild;
    		}
    	}
    }

### ☆后续遍历.非递归（较难） ###

void PostOrder2(BiTree T){//后序遍历.非递归（PostOrder2）
    	stack<BiTree> st;
    	stack<int> stemp;//用来记录相对应当前节点的访问次数 
    	BiTree temp = T;
    	int tt=0;
    	while(temp||!st.empty()){
    		while(temp&&tt==0){//一直向左,直至无左子树存在 
    			st.push(temp);
    			stemp.push(tt+1);
    			temp = temp->lchild;
    			tt = 0;
    		}
    		if(!st.empty()){//访问或压右结点 
    			temp = st.top();
    			st.pop();
    			tt = stemp.top();
    			stemp.pop();
    			if(tt==1){//已经访问了左子树但未访问右子树 
    				stemp.push(tt+1);
    				st.push(temp);
    				temp = temp->rchild;
    				tt = 0;
    			}else{//两个子结点全部访问完，访问当前节点 
    				visit(temp);
    				if(!st.empty()){//防止读取出错，最后结束标志 
    					temp = st.top();
    					tt = stemp.top(); 	
    				}else{
    					temp =NULL;
    				}
    			}
    		}
    	}
    }

### 层次遍历·非递归（LevelOrder2） ###

void LevelOrder2(BiTree T){//层次遍历.非递归（LevelOrder2）
    	queue<BiTree>  qt;
    	BiTree temp;
    	qt.push(T);
    	//cout<<qt.front()->data<<endl;
    	while(!qt.empty()){
    		temp = qt.front();
    		visit(temp);
    	//	cout<<temp->data<<endl;
    		qt.pop();
    		if(temp->lchild)
    			qt.push(temp->lchild);
    		if(temp->rchild)
    			qt.push(temp->rchild);	
    	} 
    }

### 测试代码 ###

/\*编译环境：

win10专业版

DEV C++ 5.11

TDM-GCC 4.9.2 64bit

\*/

\#include<iostream>

\#include "malloc.h"

\#include<queue>

\#include<stack>

using namespace std;

typedef char Elemtype ;

/*编译环境：
    win10专业版
    DEV C++ 5.11
    TDM-GCC 4.9.2 64bit
    */
    #include<iostream>
    #include "malloc.h"
    #include<queue>
    #include<stack>
    using namespace std;
    
    typedef char Elemtype ; 
    
    typedef struct BiTNode{//定义二叉树结构 
    	Elemtype data;
    	BiTNode *lchild,*rchild;
    } BiTNode,*BiTree;
    
    BiTree creatBiTree(Elemtype tree[] , int n , int num ){//使用顺序存储结构建立链式存储结构二叉树 
    	//cout<<num<<endl;
    	if(n<num||tree[num]==0)//超过结点个数限制或该点是空结点
    		return NULL;
    	//该点不是空结点 
    	BiTree T = (BiTree)malloc(sizeof(BiTNode));
    	T->data = tree[num];
    	T->lchild =  creatBiTree (tree,n,num*2);
    	T->rchild =  creatBiTree (tree,n,num*2+1);
    	return T;	
    }
    
    void visit(BiTree b){//访问结点
    	cout<<b->data<<"\t";
    }
    
    int main(){
    	BiTree T = (BiTree)malloc(sizeof(BiTNode));
    	Elemtype A[30]= {0,'A',
    					 'B','D',
    					 0,'C','E','F',
    					 0,0,0,0,0,0,'G','I',
    					 0,0,0,0,0,0,0,0,0,0,0,0,0,'H'};
    	T = creatBiTree(A,29,1);
    
    	cout<<endl<<"先序遍历·递归（PreOrder）:\t";PreOrder(T);//先序遍历·递归（PreOrder）
    
    	cout<<endl<<"中序遍历.递归（InOrder）:\t";InOrder(T);//中序遍历.递归（InOrder）
    
    	cout<<endl<<"后序遍历.递归（PostOrder）:\t";PostOrder(T);//后序遍历.递归（PostOrder）
    	
    	queue<BiTree> qt;
    	qt.push(T);
    	cout<<endl<<"层次遍历.递归（LevelOrder）:\t";LevelOrder(qt);//层次遍历.递归（LevelOrder）
    
    	cout<<endl<<"先序遍历·非递归（PreOrder2）:\t";PreOrder2(T);//先序遍历·非递归（PreOrder2）
    
    	cout<<endl<<"中序遍历.非递归（InOrder2）:\t";InOrder2(T);//中序遍历.非递归（InOrder2）
    
    	cout<<endl<<"后序遍历.非递归（PostOrder2）:\t";PostOrder2(T);//后顺序遍历.非递归（PostOrder2）
    
    	cout<<endl<<"层次遍历.非递归（LevelOrder2）:\t";LevelOrder2(T);//层次遍历.非递归（LevelOrder2）
    	
    	return 0; 
    }

## 参考文献 ##

严蔚敏，吴伟民. 数据结构（C语言版）\[M\]. 北京： 清华大学出版社，2013.

**如有错误，还请朋友不吝指正。**