Question

设计一个非递归算法，从一棵二叉树中查找出所有节点的最大值并返回。

不要复制，谢谢。

Answer 1

给个思路：

    找最大值的关键是树的遍历，而递归的遍历方式，就是利用函数调用，参数的入栈出栈，来达到回溯的目的，同理，不用递归调用，我们也可以采用这个思想

1. 创建一个栈式的数据结构

2. 将根节点指针压入栈中，访问其值，假如我们采用广度优先的遍历方式，就遍历其子节点

3. 在访问子节点的同时，依次将访问过的节点指针压入栈中，而最上面的节点就是最后访问的节点

4. 如最上面的节点是叶子节点，则弹栈，否则继续遍历其子节点，并如3步所说，依访问顺序压栈

5. 对于所有子节点都已遍历（压栈）的父节点，做标记，则当弹栈后，栈的最上面是一个带有标记的非叶子节点，亦将其弹出栈

6. 循环3-5步，直到栈空为止

深度优先搜索，也可以用类似的方式实现

追问

能写个程序吗？

追答

步骤很清楚了，有问题可以讨论，程序就算了

Answer 2

java实现 :

import java.util.Scanner;
import java.util.Vector;
/** BinaryTree .java
*
*/

public class BinaryTree{
public BinaryTree (Node root){
root.left=construct(root.left);
}
public Node construct(Node node){
System.out.println("input next node id(num):");
int id = Integer.parseInt(new Scanner(System.in).nextLine());
if(id!=-1) node=new Node(id);
else return null;
node.left=construct(node.left);
node.right=construct(node.right);
return node;
}
public int visitMax(Node root){
Vector<Node> tasks=new Vector<Node>();
Node tmp = root.left;
tasks.add(tmp);
int max=-1;
while(!tasks.isEmpty()){
while(tmp!=null){
if(max<tmp.visitMax())
max=tmp.visitMax();
tasks.add(tmp);
tmp=tmp.left;
}
tmp=tasks.lastElement();
tasks.remove(tmp);
tmp=tmp.right;
}
return max;
}
public static void main(String[] args) {
Node root=new Node(0);
BinaryTree bt=new BinaryTree(root);
System.out.println("max num is:"+bt.visitMax(root));
}
}
//BinaryTree .java

class Node{
int num;
Node left,right;
Node(int num){
this.num=num;
}
public int visitMax(){
System.out.println("visited:"+this.num);
return num;
}
};

Answer 3

直接for循环遍历？二叉树节点信息是装在数组里面的直接for遍历数组不就行了？当然如果不是数组，直接遍历类似的。