文档章节

二叉树的层次遍历、深度遍历、遍历的非递归和递归的实现思路及源码

 剑阁
发布于 2015/09/28 16:19
字数 857
阅读 29
收藏 0
#include <STDIO.H>
#include <STACK>
#include <QUEUE>
using namespace std;



typedef char DataType;

typedef struct Node{
	DataType elem;
	Node * rChild;
	Node * lChild;
}*pNode;



bool creat(pNode &root){
	DataType data;
	scanf("%c",data);
	if (data==EOF)
	{
		return false;
	}
	if (data=='#')
	{
		root=NULL;
	}else{
		root=(pNode)malloc(sizeof(struct Node));
		root->elem=data;
		creat(root->lChild);
		creat(root->rChild);
	}
	return true;
}

// 前序遍历
void preOrder(pNode root){
	if (root)
	{
		printf("%c ",root->elem);
		if (root->lChild)
		{
			preOrder(root->lChild);
		}
		if (root->rChild)
		{
			preOrder(root->rChild);
		}
	}
}


// 前序遍历非递归实现
void preOrder2(pNode root){
	stack<pNode> S;
	pNode temp;
	temp=root;
	while(temp!=NULL || !S.empty()){
		while(temp!=NULL){
			printf("%c ",temp->elem);
			S.push(temp);
			temp=temp->lChild;
		}

		if (!S.empty())
		{
			temp = S.top();
			S.pop();
			temp=temp->rChild;
		}
	}
}


// 层次遍历
void levalTravel(pNode root){
	queue<pNode> Q;
	Q.push(root);
	while (!Q.empty())
	{
		pNode temp=Q.front();
		printf("%c ",temp->elem);
		Q.pop();

		if (temp->lChild)
		{
			Q.push(temp->lChild);
		}

		if (temp->rChild)
		{
			Q.push(temp->rChild);
		}
	}
}

// 中序遍历
void inOrder(pNode root){
	if (root)
	{
		if (root->lChild)
		{
			inOrder(root->lChild);
		}
		printf("%c ",root->elem);

		if (root->rChild)
		{
			inOrder(root->rChild);
		}
	}
}


// 对于任意节点P
// 1)若其左孩子不为空,则将P入栈并将P的左孩子赋值给当前的P,然后对当前
// 的P进行相同的处理
// 2)若其左孩子为空,则取栈顶元素并进行出栈操作,访问该栈顶结点,然后
// 将当前的P置为栈顶结点的右孩子
// 3)直到P为NULL且栈为空则遍历结束
// 中序遍历非递归实现
void inOrder2(pNode root){
	stack<pNode> S;
	pNode temp;
	temp=root;
	while( temp!=NULL || !S.empty()){
		while (temp !=NULL)
		{
			S.push(temp);//放入当前结点
			temp = temp->lChild;//依次放入左孩子
		}

		if (!S.empty())
		{
			temp = S.top();
			printf("%c ",temp->elem);
			S.pop();
			temp=temp->rChild;
		}
	}	
}

void postOrder(pNode root){
	if (root)
	{
		if (root->lChild)
		{
			postOrder(root->lChild);
		}

		if (root->rChild)
		{
			postOrder(root->rChild);
		}

		printf("%c ",root->elem);
	}
}

// 思路:要保证根节点在左孩子和右孩子访问之后才能访问,
// 因此对于任一节点P,先将其入栈。
// 条件一:如果P不存在左孩子和右孩子,则可以直接访问它;
// 条件二:或者P存在左孩子和右孩子都已被访问过,则同样可以直接访问该节点。
// 若非上述两种情况,则将P的右孩子和左孩子依次入栈,这样就保证了每次取栈
// 顶元素的时候,左孩子在右孩子前面访问,左孩子和右孩子都在根结点前面被访问。
void postOrder2(pNode root){
	stack<pNode> S;
// 	pNode temp;
// 	temp = root;
	pNode pre;//前次访问的节点
	pNode cur;//当前访问的节点
	S.push(root);
	
	pre=NULL;
	while (!S.empty())
	{
		cur=S.top();
		if ( (cur->lChild==NULL && cur->rChild==NULL) //条件一
				|| ((pre!=NULL)&&( (pre==cur->lChild) || (pre==cur->rChild))) )//条件二
		{
			printf("%c ",cur->elem);
			S.pop();
			pre=cur;//保存前一个节点
		}else{
			if (cur->rChild)
			{
				S.push(cur->rChild);
			}
			if (cur->lChild)
			{
				S.push(cur->lChild);
			}
				
		}
	}
}


void depthTravel(pNode root){
	stack<pNode> S;
	//printf("%c ",root->elem);
	S.push(root);
	while (!S.empty())
	{
		pNode temp = S.top();
		printf("%c ",temp->elem);
		S.pop();

		if (temp->rChild)
		{
			S.push(temp->rChild);
		}

		if (temp->lChild)
		{
			S.push(temp->lChild);
		}
	}
}


int main(){

// 	pNode root;
// 	creat(root);

	pNode root1=(pNode)malloc(sizeof(Node));
	root1->lChild=NULL;
	root1->rChild=NULL;
	pNode root2=(pNode)malloc(sizeof(Node));
	root2->lChild=NULL;
	root2->rChild=NULL;
	pNode root3=(pNode)malloc(sizeof(Node));
	root3->lChild=NULL;
	root3->rChild=NULL;
	pNode root4=(pNode)malloc(sizeof(Node));
	root4->lChild=NULL;
	root4->rChild=NULL;
	pNode root5=(pNode)malloc(sizeof(Node));
	root5->lChild=NULL;
	root5->rChild=NULL;
	pNode root6=(pNode)malloc(sizeof(Node));
	root6->lChild=NULL;
	root6->rChild=NULL;

	root1->elem='1';
	root2->elem='2';
	root3->elem='3';
	root4->elem='4';
	root5->elem='5';
	root6->elem='6';
	

	root1->lChild=root2;
	root1->rChild=root3;

	root2->lChild=root4;

	root3->lChild=root5;
	root3->rChild=root6;

	printf("preOrder(root1):");
	preOrder(root1);
	printf("\n");

	printf("preOrder2(root1):");
	preOrder2(root1);
	printf("\n");

	printf("inOrder(root1):");
	inOrder(root1);
	printf("\n");


	printf("levalTravel(root1):");
	levalTravel(root1);
	printf("\n");

	printf("depthTravel(root1):");
	depthTravel(root1);
	printf("\n");


	printf("inOrder2(root1):");
	inOrder2(root1);
	printf("\n");

	printf("postOrder(root1):");
	postOrder(root1);
	printf("\n");


	printf("postOrder2(root1):");
	postOrder2(root1);
	printf("\n");
	return 0;
}


© 著作权归作者所有

粉丝 0
博文 1
码字总数 857
作品 0
呼和浩特
私信 提问
python实现二叉树的遍历以及基本操作

主要内容: 二叉树遍历(先序、中序、后序、宽度优先遍历)的迭代实现和递归实现; 二叉树的深度,二叉树到叶子节点的所有路径; 首先,先定义二叉树类(python3),代码如下:

pandaWaKaKa
06/25
0
0
Leetcode#104. Maximum Depth of Binary Tree(二叉树的最大深度)

题目描述 给定一个二叉树,找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。 示例: 给定二叉树 [3,9,20,null,null,15,7...

武培轩
2018/09/12
0
0
PHP实现二叉树的深度优先遍历(前序、中序、后序)和广度优先遍历(层次)

http://blog.csdn.net/baidu_30000217/article/details/52953127 前言: 深度优先遍历:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次。要特别注意的是,二叉树的深...

陈小龙哈
2018/06/26
0
0
二叉树的最大深度

原题   Given a binary tree, find its maximum depth.   The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. 题目......

一贱书生
2016/12/20
40
0
学习笔记——二叉树相关算法的实现(Java语言版)

二叉树遍历概念和算法 遍历(Traverse):   所谓遍历(Traversal)是指沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问。   从二叉树的递归定义可知,一棵非空的二叉树由根结...

殇灬央
03/14
0
0

没有更多内容

加载失败,请刷新页面

加载更多

规则引擎

解决问题 版本迭代速度更不上业务变化,但是若多个业务同时变化,除了为每个业务设计专属配置项也不利于操作。就想服务接口单纯化,将复杂多变的业务逻辑交给规则引擎,让用户在web端或cs端自...

无极之岚
32分钟前
4
0
OSChina 周三乱弹 —— 欢迎你来做产品经理

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @巴拉迪维 :10多次劲歌金曲获奖,更多叱咤歌坛排名,黎明才应该是四大天王之首,只可惜拍的电影太少。单曲循环一个多月的歌,力荐 《无名份的...

小小编辑
今天
249
9
500行代码,教你用python写个微信飞机大战

这几天在重温微信小游戏的飞机大战,玩着玩着就在思考人生了,这飞机大战怎么就可以做的那么好,操作简单,简单上手。 帮助蹲厕族、YP族、饭圈女孩在无聊之余可以有一样东西让他们振作起来!...

上海小胖
今天
10
0
关于AsyncTask的onPostExcute方法是否会在Activity重建过程中调用的问题

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接:https://blog.csdn.net/XG1057415595/article/details/86774575 假设下面一种情况...

shzwork
今天
7
0
object 类中有哪些方法?

getClass(): 获取运行时类的对象 equals():判断其他对象是否与此对象相等 hashcode():返回该对象的哈希码值 toString():返回该对象的字符串表示 clone(): 创建并返此对象的一个副本 wait...

happywe
今天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部