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

题目：

给你二叉树的根节点 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