欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

二叉树的前序迭代遍历推出后序,中序以及层序的实现

程序员文章站 2022-03-05 15:00:48
题目:给你二叉树的根节点 root ,返回它节点值的 前序 遍历。示例 1:输入:root = [1,null,2,3]输出:[1,2,3]示例 2:输入:root = []输出:[]示例 3:输入:root = [1]输出:[1]示例 4:输入:root = [1,2]输出:[1,2]示例 5:输入:root = [1,null,2]输出:[1,2]提示:树中节点数目在范围 [0, 100] 内-100 <= Node.val <= 100进阶:递...

题目:

给你二叉树的根节点 root ,返回它节点值的 前序 遍历。

示例 1:

二叉树的前序迭代遍历推出后序,中序以及层序的实现

输入:root = [1,null,2,3]
输出:[1,2,3]
示例 2:

输入:root = []
输出:[]
示例 3:

输入:root = [1]
输出:[1]
示例 4:
二叉树的前序迭代遍历推出后序,中序以及层序的实现
输入:root = [1,2]
输出:[1,2]
示例 5:
二叉树的前序迭代遍历推出后序,中序以及层序的实现
输入:root = [1,null,2]
输出:[1,2]

提示:

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

进阶:递归算法很简单,你可以通过迭代算法完成吗?

题解:

方法一:递归
首先我们需要了解什么是二叉树的前序遍历:按照访问根节点——左子树——右子树的方式遍历这棵树,而在访问左子树或者右子树的时候,我们按照同样的方式遍历,直到遍历完整棵树。因此整个遍历过程天然具有递归的性质,我们可以直接用递归函数来模拟这一过程。

定义 preorder(root) 表示当前遍历到 root 节点的答案。按照定义,我们只要首先将 root 节点的值加入答案,然后递归调用 preorder(root.left) 来遍历 root 节点的左子树,最后递归调用 preorder(root.right) 来遍历 root 节点的右子树即可,递归终止的条件为碰到空节点。
代码:

	public int preorder(BiTreeNode p) {
		if (p == null) {
			return 0;
		}
		System.out.print(p.getData() + " ");
		preorder(p.lchild);
		preorder(p.rchild);
		return 1;
	}

方法二:迭代
我们也可以用迭代的方式实现方法一的递归函数,两种方式是等价的,区别在于递归的时候隐式地维护了一个栈,而我们在迭代的时候需要显式地将这个栈模拟出来,其余的实现与细节都相同,具体可以参考下面的代码。
在进行迭代时我们要考虑用栈来对结点的存放和丢弃,声明一个LinkedList,可保存结点数据,并进行头插和尾插。
我们需要一个循环去从根=》左=》右的顺序遍历,循环的条件为root是否为空和栈是否为空,这里判断栈是因为当遍历到第一次root为空时,如果还有未遍历的结点,能够保证继续遍历。
然后如果p!=null,入栈根,list尾插法填入p的数据,p=p.lchild让p变成左孩子,之后一直遍历和入栈左孩子,list尾插法addlast填入左孩子的数据,直到左孩子为空,将栈顶取出(栈顶为无左孩子的此结点设为q),取出栈顶结点当做p, p = p.rchild让p变成右孩子,判断是否有右孩子,如果没有,说明右孩子为空,再次出栈(出栈元素为q的父节点),p变成右孩子,再进行循环判断。整个流程思路就完成了。
下面是我的代码:

public void preorderTraversal(BiTreeNode root) {
        BiTreeNode p = root;
		Stack<BiTreeNode> myStack = new Stack<BiTreeNode>();
		LinkedList<Integer> list = new LinkedList<Integer>();
		while(p!=null || !myStack.isEmpty()) {
			if(p!=null) {
				myStack.push(p);
				list.addLast((int)p.getData());
				p = p.lchild;
			}
			else {
				p = myStack.pop();
				p = p.rchild;
			}
		}
		return list;
    }

后序遍历:

按照这种思路会发现后序遍历reverse后为根=》右=》左,而我们刚说的先序遍历为根=》左=》右,只是把p=p.lchild和p=p.rchild互换顺序而已;但此时list中的数据都是反过来的(由于reverse后为根=》右=》左的原因),我们只需要在插入数据时采用头插法addfirst即可
代码如下:

public LinkedList<Integer> postorder() {
		Stack<BiTreeNode> myStack = new Stack<BiTreeNode>();
		BiTreeNode p = root;
		LinkedList<Integer> list = new LinkedList<Integer>();
		while(p!=null || !myStack.isEmpty()) {
			if(p!=null) {
				myStack.push(p);
				list.addFirst((int)p.getData());
				p = p.rchild;
			}else {
				p=myStack.pop();
				p=p.lchild;
			}
		}
		return list;

	}

顺便把递归方法代码补充一下:

	public int postorder(BiTreeNode p) {
		if (p == null) {
			return 0;
		}
		postorder(p.lchild);
		postorder(p.rchild);
		System.out.print(p.getData() + " ");
		return 1;
	}

中序遍历:

而中序是左=》根=》右,没必要做反转(故使用尾插法),不过不能先遍历根了,即list不能从根开始添加元素了,我们需要先遍历左,(这里需要分清根并不是先遍历的,所以不能在遍历左孩子的过程中添加到list)左孩子为空之后,取栈顶元素,list添加该元素数据(即根数据),然后让p=p.rchild,使得p变成右孩子,判断右孩子是否存在,存在即入栈,在出栈的时候将数据添加到list中;不存在就继续出栈,判断右孩子是否存在。整个流程就结束了。
代码如下:与先序遍历相比,只改了list添加元素的位置。

public LinkedList<Integer> inorder() {
		BiTreeNode p = root;
		Stack<BiTreeNode> myStack = new Stack<BiTreeNode>();
		LinkedList<Integer> list = new LinkedList<Integer>();
		while(p!=null || !myStack.isEmpty()) {
			if(p!=null) {
			myStack.push(p);
			p=p.lchild;	
			}else {
				p = myStack.pop();
				list.addLast((int)p.getData());
				p = p.rchild;
			}
		}
		return list;
	}

递归代码如下:

public int inorder(BiTreeNode p) {
		if (p == null) {
			return 0;
		}
		inorder(p.lchild);
		System.out.print(p.getData() + " ");
		inorder(p.rchild);
		return 1;
	}

总结:

先序和后序遍历由于都可以看做从根开始遍历,所以在遍历的过程中添加元素;中序遍历是从左开始遍历,需要在出栈时候再将数据进行添加。

顺便写一下层序遍历吧
设二叉树的根节点所在层数为1,层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树根节点,然后从左到右访问第2层上的节点,接着是第三层的节点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历。

主要是使用队列进行操作,front++在while循环中是因为需要打印数据的。

public void levelOrder() {
		BiTreeNode []queue = new BiTreeNode[size()];
		int front = -1;
		int rear=0;
		queue[rear]=root;
		while(front!=rear) {
			front++;
			System.out.print(queue[front].getData()+" ");
			BiTreeNode parent=queue[front];
			
			if(parent.lchild!=null) {
				rear++;
				queue[rear]=parent.lchild;
			}
			if(parent.rchild!=null) {
				rear++;
				queue[rear]=parent.rchild;
			}
		}
	}

结束

本文地址:https://blog.csdn.net/a12355556/article/details/109888957