二叉树的遍历及深度的计算_二叉树深度计算

目录

前言

一、后续遍历的简单版本

二、层序遍历

三、计算树的深度

1.什么是树的深度

2.递归

3.非递归

总结

---

---

前言

我们上一篇已经介绍了大量的二叉树知识，这下我们介绍一下其他的知识，接下来我们会了解到二叉树非递归后序遍历的简单版本，还有层序遍历，以及后面的二叉树的深度查找递归，非递归两种版本。这些都会帮助我们在以后的问题中解决很多的事的，所以接下来就要慢慢思考，它里面把好的整体思想。

---

一、后续遍历的简单版本

之前我们已经了解到后序遍历的两种算法，但是他的非递归算法的难度还是比较大的，所以接下来了解一个easy版本，我们首先按照 跟->右->左 先把所有的节点数据存储到数组里面，然后把我们的数组里面的数组反转一下输出，这样就达到了我们的目的。在这里我们需要用到数组存储，其他的很多思想都是比较容易理解的。

void Nrelasteasy(Tree* tree)//非递归 后序遍历（easy) 
{
    //定义栈，为了操作树的存储
	Tree* stack[MAX],*node;
    //定义数组，方便后续进行的输出
    int array[MAX]={0};
    //初始化对列，count用来记录一共有多少个数
	int top=0,count=0,i;
	//判断仅从遍历的树是否为空，如果为空的话，就返回
	if(tree==NULL){
		printf("该树为空\n");
        return;
	}else{
        //为了方便，在栈的第一位不存数据
		top++;
        //将树的根节点赋值给栈的第一位
		stack[top]=tree;
        //如果栈为为空，我们就退出整个循环
		while(top>0){
            //取出栈顶元素
			node=stack[top];
            //对栈的指针进行操作
			top--;
            //将该节点的数据存到数组里面，同时我们要把数组的索引进行操作
			array[count++]=node->data;
            //因为栈是先进后出的，所以我们先把该节点的左孩子入栈，再把该节点的右孩子入栈
			if(node->l_child!=NULL){
				top++;
				stack[top]=node->l_child;
			}
			if(node->r_child!=NULL){
				top++;
				stack[top]=node->r_child;
			}
		}
        //最后就是要反着把所有的数组数据输出
		for(i=count-1;i>=0;i--){
			printf("%d\n",array[i]);
		}
	}
}

二、层序遍历

二叉树的层序遍历是什么呢，他就是按照一层层的顺序把我们的所有节点都进行输出，不如上图中的结构，我们输出的顺序就是3—2，8—2，3，6—5—4，这样的顺序把说有的节点输出，按照这个顺序，我们很容易的想到队列这种数据结构，因为它可以把每层的数据依次存到队尾，然后利用队头输出之前存的节点，这样下来，就达到了我们的目的。

代码如下（示例）：

void levertraversal(Tree* tree)
{
    //如果数组为空，那么我们就返回
	if(tree==NULL){
		printf("该树为空\n");
		return;
	} 
    //定义队列，为了存储树的数据
	Tree *queue[MAX],*node;
    //初始化队列的指针
	int front=0,rear=0;
    //将树的根节点赋值给队列，同时将尾指针向后移动
	queue[rear++]=tree;
    //如果队列为空，我们就退出整个循环
	while(front!=rear){
        //取出队头元素
		node=queue[front++];
        //输出该节点的数据
		printf("%d\n",node->data);
        //如果该节点的左右有孩子，就将孩子入队，先将左孩子入队，再将右孩子入队，因为队列是先进先出的数据结构
		if(node->l_child != NULL){
			queue[rear++] = node->l_child;
		}
		if(node->r_child != NULL){
			queue[rear++] = node->r_child;
		}
	}
}

三、计算树的深度

1.什么是树的深度

二叉树的根结点所在的层数为1，根结点的孩子结点所在的层数为2，以此下去。深度是指所有结点中最深的结点。 

从图中我们就很容易的看到该二叉树的深度为3，这个看起来很容易，但是算法中还是有一定的困难的，因为，我们不知道它里面哪一个是最深的，所以要遍历所有的节点，看到它的最深的，它里面含有很多的问题，所以，我们就要了解到具体的算法问题。接下里，就了解一下递归和非递归的算法。

2.递归

利用递归的算法，就是我们把树按照一遍遍历完，然后比较同一层中他们左右孩子的子孙深度多，然后返回深度多的，我们在返回的时候要进行加一操作，这样就表示该层是存在数据的，如果没有存在数据的话，那么返回的就是0.

代码如下（示例）：

int treedepth(Tree *tree)//树的深度 
{
    //定义两个数据，用来记录树的深度
	int depth1 = 0,depth2 = 0;
    //如果树为空，那么我们返回的数值就为0
	if(tree == NULL){
		return 0;
	}else{
        //对左右孩子进行继续的遍历
		depth1=treedepth(tree->l_child);
		depth2=treedepth(tree->r_child);
        //判断出左右孩子那个最大，然后要反回他的深度+1，如果没有的话会返回0，他的深度也不会增加
		return depth1>depth2?depth1+1:depth2+1;
	}
}

3.非递归

在非递归中我们要引用队列进行操作，队列的操作会让我们在很多问题上比较方便，在这里需要注意的是，我们要用到一个数一直指向最后的索引，为什么要这样呢，因为这个索引是为了让我们只得知道他的这一层是否遍历过去，如果遍历过去，那么我们的头指针就会遇到这个索引，这个时候我们的层数就是达到了所有。也记录完了所有的深度。接着就是要让该索引指向新的尾指针。

如果大家不理解这个过程，可以画图尝试。

int Nretreedepth(Tree *tree)//非递归 树的深度 
{
    //定义队列
	Tree *queue[MAX],*node;
    //为了方便操作，用node来操作
	node=tree;
    //初始化队列，depth用来记录他的深度，我们用level指向队列的队尾元素
	int front = 0,rear = 0,depth = 0,level;
    //如果树不为空，我们就把树的根节点赋值给队列的尾
	if(tree != NULL){
		queue[++rear] = node;
	}
    //让level指向队尾指针
	level=rear;
    //如果队为空的话，我们就退出整个循环
	while(front<rear){
        //取出队头元素，同时将队头指针向后移动
		node=queue[++front];
        //将该节点的左右孩子先入队，因为队列是先进先出，所以先将左孩子入队，再将右孩子入队
		if(node->l_child != NULL){
			queue[++rear] = node->l_child;
		}
		if(node->r_child != NULL){
			queue[++rear] = node->r_child;
		}
        //如果头指针等于之前标记的尾节点，那么说明这个层已经全部被遍历，所以这个深度需要加加
		if(front == level){
			depth++;
            //接着需要把这个让level指向当前的尾节点，方便后面的查找
			level = rear;
		}
	}
    //返回这个深度
	return depth;
}

---

总结

今天看到的这些是比较重要的几个树的操作，里面有很多的细节，数组索引的移动方式，队列，栈的数据结构，都是我们需要注意的地方，这让我们有很大的帮助，通过这些，在尽头的有些问题上可以很好地解决。

接下来就是附上今天的所有代码。

#include<stdio.h>
#include<stdlib.h>
#define MAX 10
typedef struct node{
	int data;
	struct node *l_child;
	struct node *r_child;
}Tree;
Tree *Create_Tree();//创建二叉树 
void Nrelasteasy(Tree* tree);//非递归 后序遍历（easy) 
void levertraversal(Tree* tree);//层次遍历 
int treedepth(Tree *tree);//树的深度 
int Nretreedepth(Tree *tree);//非递归 树的深度 
int main()
{
	Tree*tree;
	tree=Create_Tree();
    printf("非递归后序遍历,简单版本\n");
	Nrelasteasy(tree);
	printf("层次遍历\n");
	levertraversal(tree);
	printf("递归计算树的深度%d\n",treedepth(tree));
	printf("非递归计算树的深度%d\n",Nretreedepth(tree));
}
Tree *Create_Tree()
{
    //先申明一个空指针
	Tree *root=NULL;
	int data;
	scanf("%d", &data);//通过输入的ch是否为特殊符号来判断该节点是否有孩子节点
    //这里可以用任何的特殊字符，根据自己来定义
	if(data == -1){	//不存在孩子节点
		root=NULL;
	}else{
        //当这个数据需要存储的时候要，我们就需要离开开辟空间
		root = (Tree *)malloc(sizeof(Tree));
        //如果开辟失败，就返回
		if(NULL == root){
			printf("创建失败\n");
			return NULL;
		}	
        //将数据存储到根节点里面
		root->data = data;
		root->l_child = Create_Tree();//存在左孩子节点，递归调用本函数，使得左孩子节点先被赋值
		root->r_child = Create_Tree();//存在右孩子节点，递归调用本函数，使得右孩子节点后被赋值
	}
    //最后将该节点返回
	return root;
}
void Nrelasteasy(Tree* tree)//非递归 后序遍历（easy) 
{
    //定义栈，为了操作树的存储
	Tree* stack[MAX],*node;
    //定义数组，方便后续进行的输出
    int array[MAX]={0};
    //初始化对列，count用来记录一共有多少个数
	int top=0,count=0,i;
	//判断仅从遍历的树是否为空，如果为空的话，就返回
	if(tree==NULL){
		printf("该树为空\n");
        return;
	}else{
        //为了方便，在栈的第一位不存数据
		top++;
        //将树的根节点赋值给栈的第一位
		stack[top]=tree;
        //如果栈为为空，我们就退出整个循环
		while(top>0){
            //取出栈顶元素
			node=stack[top];
            //对栈的指针进行操作
			top--;
            //将该节点的数据存到数组里面，同时我们要把数组的索引进行操作
			array[count++]=node->data;
            //因为栈是先进后出的，所以我们先把该节点的左孩子入栈，再把该节点的右孩子入栈
			if(node->l_child!=NULL){
				top++;
				stack[top]=node->l_child;
			}
			if(node->r_child!=NULL){
				top++;
				stack[top]=node->r_child;
			}
		}
        //最后就是要反着把所有的数组数据输出
		for(i=count-1;i>=0;i--){
			printf("%d\n",array[i]);
		}
	}
}
void levertraversal(Tree* tree)
{
    //如果数组为空，那么我们就返回
	if(tree==NULL){
		printf("该树为空\n");
		return;
	} 
    //定义队列，为了存储树的数据
	Tree *queue[MAX],*node;
    //初始化队列的指针
	int front=0,rear=0;
    //将树的根节点赋值给队列，同时将尾指针向后移动
	queue[rear++]=tree;
    //如果队列为空，我们就退出整个循环
	while(front!=rear){
        //取出队头元素
		node=queue[front++];
        //输出该节点的数据
		printf("%d\n",node->data);
        //如果该节点的左右有孩子，就将孩子入队，先将左孩子入队，再将右孩子入队，因为队列是先进先出的数据结构
		if(node->l_child != NULL){
			queue[rear++] = node->l_child;
		}
		if(node->r_child != NULL){
			queue[rear++] = node->r_child;
		}
	}
}
int treedepth(Tree *tree)//树的深度 
{
    //定义两个数据，用来记录树的深度
	int depth1 = 0,depth2 = 0;
    //如果树为空，那么我们返回的数值就为0
	if(tree == NULL){
		return 0;
	}else{
        //对左右孩子进行继续的遍历
		depth1=treedepth(tree->l_child);
		depth2=treedepth(tree->r_child);
        //判断出左右孩子那个最大，然后要反回他的深度+1，如果没有的话会返回0，他的深度也不会增加
		return depth1>depth2?depth1+1:depth2+1;
	}
}
int Nretreedepth(Tree *tree)//非递归 树的深度 
{
    //定义队列
	Tree *queue[MAX],*node;
    //为了方便操作，用node来操作
	node=tree;
    //初始化队列，depth用来记录他的深度，我们用level指向队列的队尾元素
	int front = 0,rear = 0,depth = 0,level;
    //如果树不为空，我们就把树的根节点赋值给队列的尾
	if(tree != NULL){
		queue[++rear] = node;
	}
    //让level指向队尾指针
	level=rear;
    //如果队为空的话，我们就退出整个循环
	while(front<rear){
        //取出队头元素，同时将队头指针向后移动
		node=queue[++front];
        //将该节点的左右孩子先入队，因为队列是先进先出，所以先将左孩子入队，再将右孩子入队
		if(node->l_child != NULL){
			queue[++rear] = node->l_child;
		}
		if(node->r_child != NULL){
			queue[++rear] = node->r_child;
		}
        //如果头指针等于之前标记的尾节点，那么说明这个层已经全部被遍历，所以这个深度需要加加
		if(front == level){
			depth++;
            //接着需要把这个让level指向当前的尾节点，方便后面的查找
			level = rear;
		}
	}
    //返回这个深度
	return depth;
}