二叉树的基础遍历

1：前序遍历：先访问根结点，然后再访问左子树，最后访问右子树；

2：中序遍历：先访问左子树，然后再访问根结点，最后访问右子树；

3：后序遍历：先访问左子树，然后再访问右子树，最后访问根结点；

示例如下：

前序遍历的API设计：

public Queue preErgodic():使用前序遍历，获取整个树中的所有键private void preErgodic(Node x,Queue keys):使用前序遍历，把指定树x中的所有键放入到keys队列中

实现步骤：

1. 把当前结点的key放入到队列中；
2. 找到当前结点的左子树，如果不为空，递归遍历左子树；
3. 找到当前结点的右子树，如果不为空，递归遍历右子树；

代码实现：

//使用前序遍历获取整个树中所有的键    public Queue preErgoidic(){         Queue keys = new Queue<>();        preErgoidic(root,keys);        return keys;    }    //使用前序遍历获取指定树x的所有键，并放到Keys队列中    private void preErgoidic(Node x, Queue keys){         if(x == null){             return;        }        //把x结点的key放入到keys中        keys.enQueue(x.key);        //递归遍历x结点的左子树        if(x.left != null){             preErgoidic(x.left,keys);        }        //递归遍历x结点的右子树        if(x.right != null){             preErgoidic(x.right,keys);        }    }

中序遍历的API设计：

public Queue midErgodic():使用中序遍历，获取整个树中的所有键private void midErgodic(Node x,Queue keys):使用中序遍历，把指定树x中的所有键放入到keys队列中

实现步骤：

1. 找到当前结点的左子树，如果不为空，递归遍历左子树；
2. 把当前结点的key放入到队列中；
3. 找到当前结点的右子树，如果不为空，递归遍历右子树；

代码实现：

//使用中序遍历获取整个树中所有的键    public Queue midErgoidic(){         Queue keys = new Queue<>();        midErgoidic(root,keys);        return keys;    }    //使用中序遍历获取指定树x的所有键，并放到Keys队列中    private void midErgoidic(Node x, Queue keys) {         if(x == null){             return;        }        //递归遍历x结点的左子树        if(x.left != null){             midErgoidic(x.left,keys);        }        //把x结点的key放入到keys中        keys.enQueue(x.key);        //递归遍历x结点的右子树        if(x.right != null){             midErgoidic(x.right,keys);        }    }

后序遍历的API设计：

public Queue afterErgodic():使用中序遍历，获取整个树中的所有键private void afterErgodic(Node x,Queue keys):使用中序遍历，把指定树x中的所有键放入到keys队列中

实现步骤：

1. 找到当前结点的左子树，如果不为空，递归遍历左子树；
2. 找到当前结点的右子树，如果不为空，递归遍历右子树；
3. 把当前结点的key放入到队列中；

代码实现：

//后续遍历    public Queue afterErgoidic(){         Queue keys = new Queue<>();        afterErgoidic(root,keys);        return keys;    }    //使用中序遍历获取指定树x的所有键，并放到Keys队列中    private void afterErgoidic(Node x, Queue keys) {         if(x == null){             return;        }        //递归遍历x结点的左子树        if(x.left != null){             afterErgoidic(x.left,keys);        }        //递归遍历x结点的右子树        if(x.right != null){             afterErgoidic(x.right,keys);        }        //把x结点的key放入到keys中        keys.enQueue(x.key);    }

原文链接：https://blog.csdn.net/qq_43751200/article/details/126110809