IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 二叉树先序、中序和后序的递归玉非递归实现 -> 正文阅读

[数据结构与算法]二叉树先序、中序和后序的递归玉非递归实现

目录标题

递归

//无论是哪种递归,每个节点都可以回到自己三次。先序遍历就是i遇到节点的第一次打印
//,中序遍历就是遇到节点的第二次打印,....
public void f(Node head){
	if(head==null)return;	
	f(head.left);
	f(head.right);
}

//递归实现–无论是哪种递归,每个节点都可以回到自己三次。先序遍历就是i遇到节点的第一次打印

//递归实现--无论是哪种递归,每个节点都可以回到自己三次。先序遍历就是i遇到节点的第一次打印
,中序遍历就是遇到节点的第二次打印....

//先序遍历
public void pre(Node head){
	if(head==null)return;
	System.out.println(head.value);
	pre(head.left);
	pre(head.right);
}
//中序遍历
public void in(Node head){
	if(head==null)return;
	in(head.left);
	System.out.println(head.value);
	in(head.right);
}
//后序遍历
public void pre(Node head){
	if(head==null)return;
	pos(head.left);
	pos(head.right);
	System.out.println(head.value);
	
}

非递归

//非递归实现
//任何递归都可以改成非递归,压栈实现
//先序遍历:头-左-右
//先头结点放入栈里,1弹出即打印,2有右孩子压右孩子,3如有左孩子压左孩子
public void pre(Node head){
	System.out.println("先序遍历");
	Stack<Node> stack=new Stack<>();
	stack.push(head);
	while(!stack.isEmpty()){
		Node node=stack.pop();
		System.out.println(node.value+" ");
		if(head.right!=null)stack.push(head.right);
		if(head.left!=null)stack.push(head.left);
	}
	System.out.println();
}

//后序遍历:左-右-头
//先头结点放入栈里,1弹出即打印,2有左孩子压左孩子,3如有右孩子压右孩子
//此时和先序遍历比较像,只不过是头-右-左,===》倒过来就是后序遍历
//倒过来,只需要弹出的时候不打印,而是将值再存到一个栈里面,最后再打印即可
public void pos(Node head){
	Stack<Node> stack1=new Stack<>();//栈1存放树节点
	Stack<Node> stack2=new Stack<>();//栈2专门存放弹出时候的值
	stack.push(head);
	while(!stack.isEmpty()){
		Node node=stack.pop();
		stack2.push(node.value);
		if(head.left!=null)stack1.push(head.left);
		if(head.right!=null)stack1.push(head.right);
		
	}
	while(!stack2.isEmpty()){
		System.out.println(stack2.pop().value+" ");
	}
}
//当然也可以用一个栈实现
public void pos2(Node h){
	if(h!=null){
		Stack<Node> stack=new Stack<>();
		stack.push(h);
		Node c=null;		
		while(!stack.isEmpty()){
			c=stack.peek();
			//没处理过左子树和右子树
			if(c.left!=null&&h!=c.left&&h!=c.right){
				stack.push(c.left);
				//没处理过右子树
			}else if(c.right!=null&&h!=c.right){
				stack.push(c.right);
				//已经处理过两个子树
			}else{
				System.out.println(stack.pop().value+" ");
				//h记录访问过的节点,只有在第一次赋值的时候才有这个意义
				h=c;
			}
			
		}
	}
}
//中序遍历
//1整条左边界依次进栈2.1无法继续弹出节点就打印,然后来到弹出节点的右数继续执行1
public void in(Node head){	
		Stack<Node> stack=new Stack<Node>();
		while(!stack.isEmpty()||head!=null){
			if(head!=null){
				stack.push(head);
				head=head.left;
			}else{
				Node node=stack.pop();
				System.out.println(node.value+" ");
				head=node.right;
			}
		}	
}
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-08-18 12:56:50  更:2021-08-18 12:57:35 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/25 20:42:26-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码