点击进入尚硅谷数据结构和算法Java代码导航
1.1 递归前序遍历
//递归前序遍历
public void preOrderRec(Node temp) {
if(temp == null) {
System.out.println("BinaryTree is empty.");
}else {
System.out.print(temp.data + " ");
if(temp.left != null) {
preOrderRec(temp.left);
}
if(temp.right != null) {
preOrderRec(temp.right);
}
}
}
1.2 非递归前序遍历算法一
算法思路：先遍历到二叉树的最左边的子节点，过程中同时打印数据被遍历的子节点并将其压栈，到末尾时依次出栈遍历右子节点。该方法将子二叉树的根节点压栈尚硅谷数据结构和Java算法代码导航1.1-上海怡健医学
，利用根节点寻找它的右子节点。
//非递归前序遍历算法一，压栈的是每个二叉子树的根节点，利用这个根节点来找右子节点
public void preOrderNotRec2() {
Node temp = root;
Stack stack = new Stack();
while(!stack.isEmpty() || temp != null) {
if(temp != null) {
System.out.print( temp.data + " ");
stack.push(temp);
temp = temp.left;
}else {
temp = stack.pop();
temp = temp.right;
}
}
}
1.3 非递归前序遍历算法二
算法思路：
1，将根节点压栈。
2，从栈顶弹出节点，记为temp，打印temp数据，然后再将temp的右子节点和左子节点分别入栈。
3，重复步骤2直至栈空。
该算法与算法一不同之处是栈里存储的是每个子二叉树的右子节点，而不是根节点。
//非递归前序遍历算法一，压栈的是右子节点，
public void preOrderNotRec1() {
Node temp = root;
Stack stack = new Stack();
stack.push(temp);
while(!stack.isEmpty()) {
temp = stack.pop();
System.out.print( temp.data + " ");
if(temp.right != null) {
stack.push(temp.right);
}
if(temp.left != null) {
stack.push(temp.left);
}
}
}
2.1 递归中序遍历
//递归中序遍历
public void inOrderRec(Node temp) {
if(temp == null) {
System.out.println("BinaryTree is empty.");
}else {
if(temp.left != null) {
inOrderRec(temp.left);
}
System.out.print(temp.data + " ");
if(temp.right != null) {
inOrderRec(temp.right);
}
}
}
2.2 非递归中序遍历
和非递归前序遍历算法一类似，只是输出数据的位置不同。
//非递归中序遍历
public void inOrderNotRec() {
Stack stack = new Stack();
Node temp = root;
while(!stack.isEmpty() || temp != null) {
if(temp != null) {
stack.push(temp);
temp = temp.left;
}else {
temp = stack.pop();
System.out.print(temp.data + " ");
temp = temp.right;
}
}
}
3.1 递归后序遍历
//递归后序遍历
public void postOrderRec(Node temp) {
if(temp == null) {
System.out.println("BinaryTree is empty.");
}else {
if(temp.left != null) {
postOrderRec(temp.left);
}
if(temp.right != null) {
postOrderRec(temp.right);
}
System.out.print(temp.data + " ");
}
}
3.2 非递归后序遍历算法一
算法思路：后序遍历的难点在于需要判断是从左子树返回还是从右子树返回。若从左子树返回则先遍历右子树java二叉树遍历算法，若从右子树返回直接输出。因此我们用里一个栈记录是从左子树返回还是从右子树返回。
具体思路参考：
//非递归后序遍历算法一
public void postOrderNotRec2() {
Stack s1 = new Stack();
//用另一个栈记录是从左子树返回还是从右子树返回
Stack s2 = new Stack();
Node temp = root;
boolean flag;
while(!s1.isEmpty() || temp != null) {
if(temp != null) {
s1.push(temp);
s2.push(false);
temp = temp.left;
}else {
temp = s1.pop();
flag = s2.pop();
//false代表从左子树返回，此时需要先到右子树，并将tag改为true
if(!flag) {
s1.push(temp);
s2.push(true);
temp = temp.right;
}else {//从右子树返回说明该节点的左右子树的遍历过了，直接输出
System.out.print(temp.data + " ");
//此时temp位于子二叉树的根节点，不为空，将其手动置空，否则出现死循环
temp = null;
}
}
}
}
3.3 非递归后序遍历算法二
非常巧妙，也是用两个栈。
算法思路：
1，将根节点压入栈s1。
2，从s1中弹出节点记为temp，并将temp压入栈s2。然后将temp的左子节点和右子节点分别入栈。
3java二叉树遍历算法，重复步骤2直至栈s1为空。
4，从栈s2中取出数据并打印，打印的顺序就是后序遍历的顺序。
//非递归后序遍历算法二
public void postOrderNotRec1() {
Stack s1 = new Stack();
Stack s2 = new Stack();
Node temp = root;
s1.push(temp);
while(!s1.isEmpty()) {
temp = s1.pop();
s2.push(temp);
if(temp.left != null) {
s1.push(temp.left);
}
if(temp.right != null) {
s1.push(temp.right);
}
}
while(!s2.isEmpty()) {
System.out.print(s2.pop().data + " ");
}
}
4 层次遍历
//层次遍历
public void levelOrder() {
ArrayDeque quene = new ArrayDeque();
Node temp = this.root;
quene.add(temp);
while(!quene.isEmpty()) {
temp = quene.poll();
System.out.print(temp.data + " ");
if(temp.left != null) {
quene.add(temp.left);
}
if(temp.right != null) {
quene.add(temp.right);
}
}
}
文章来源:https://blog.csdn.net/weixin_44963741/article/details/104852308