二叉树的遍历

                                                 

目录

 

3.后序遍历(左-右-根)

2.中序遍历(左-根-右)

1.先序遍历(根-左-右)


 

 

 

二叉树如图:    

 

                                                 二叉树的遍历_第1张图片

 

 

 

无论我们用哪种顺序遍历二叉树,都要明确下面几点:

  1. 什么时候入栈
  2. 什么时候出栈
  3. 什么时候打印

由于先序遍历和中序遍历比较简单,就没详细说明,主要说下后序遍历

3.后序遍历(左-右-根)

先遍历左子节点,后遍历右子节点,最后是根节点,但右子节点不能直接获取所以需要在栈中 保存根节点。那么根节点什么时候出栈呢?根节点的右子节点全部遍历完即可出栈。再看看具体思路。

  1. 根节点1入栈,然后把1的左子节点入栈,重复该过程。这时栈内数据1,2,4
  2. 4没有左子节点,然后看没有右子节点,所以4出栈打印,这时栈内数据1,2
  3. 2出栈,2的左子树处理完毕,开始处理右子树。2的右子节点存在,所以2这时不能出栈,把2放回去。这时栈内数据,1,2。然后继续按一样的方法处理2的右子树。最终栈内数据1,2,5,7。
  4. 但这样做有个问题,2再次出栈时,右子树已经遍历过了,那我怎么避免再次遍历右子树?看出栈顺序,2的右子节点5比2先出栈,所以我们只要记下lastNode就行,2出栈后和lastNode比较,一样则说明2的右子节点已经遍历过,只打印出栈节点值就行。

BinaryTreeNode currentNode = tree;

System.out.println();

System.out.print("非递归中序遍历:");

Stack stack = new Stack<>();

BinaryTreeNode lastNode = null;

while (null != currentNode || stack.isEmpty()) {

while (null != currentNode) {

stack.push(currentNode);

currentNode = currentNode.getLeftNode();

}

currentNode = stack.pop();

if (null == currentNode.getRightNode() || lastNode == currentNode.getRightNode()) {

System.out.println(currentNode.getData() + ", ");

currentNode = null;

lastNode = currentNode;

} else {

// 这时候节点有右子节点,应先遍历完子节点后再遍历根节点,所以要重新入栈。

// 但这样会引入问题,该节点只要有右子节点就会重复出栈入栈,所以要对比,发现右子节点打印过,取出该节点后直接打印,不用入栈

stack.push(currentNode);

currentNode = currentNode.getRightNode();

}

}

 

2.中序遍历(左-根-右)

根节点入栈,有左子节点入栈,无左子节点打印该节点。然后出栈,打印出栈元素值。出栈左节点按最开始操作。

public void printMiddleOrder(BinaryTreeNode tree) {

BinaryTreeNode currentNode = tree;

System.out.println();

System.out.print("非递归中序遍历:");

Stack stack = new Stack<>();

while (null != currentNode || !stack.isEmpty()) {

while (null != currentNode) {

stack.push(currentNode);

currentNode = currentNode.getLeftNode();

}

currentNode = stack.pop();

System.out.print(currentNode.getData() + ", ");

currentNode = currentNode.getRightNode();

}

}

 

1.先序遍历(根-左-右)

先打印1,如果leftSon存在,则打印leftSon。如果leftSon 2存在子节点则先打印2,然后处理2的leftSon节点,如果2的leftSon不存在则处理2的rightSon。该过程需要保存根节点以便找到rightSon节点。

根节点打印完,进栈,然后指向左节点,左节点打印,进栈。

没有左子节点了,这时候需要打印右子节点。但根节点已进栈,所以出栈(由于根节点打印过,直接处理右子节点)。打印右子节点。

 

public void printFirstOrder(BinaryTreeNode tree) {

BinaryTreeNode currentNode = tree;

System.out.println();

System.out.print("非递归先序遍历:");

Stack stack = new Stack<>();

while (null != currentNode || !stack.isEmpty()) {

while (null != currentNode) {

System.out.print(currentNode.getData() + ", ");

stack.push(currentNode);

currentNode = currentNode.getLeftNode();

}

currentNode = stack.pop();

currentNode = currentNode.getRightNode();

}

}

 

你可能感兴趣的