请说一说二叉树遍历步骤?
这道题想考察什么?
1、二叉树的基本原理和遍历的方法?
考察的知识点
二叉树遍历的基本流量、二叉树的基本原理
考生如何回答
二叉树的基本概念
简单地理解,满足以下两个条件的树就是二叉树:
- 本身是有序树;
- 树中包含的各个节点的度不能超过 2,即只能是 0、1 或者 2; 3.
二叉树的性质
二叉树具有以下几个性质:
- 二叉树中,第 i 层最多有 2i-1 个结点。
- 如果二叉树的深度为 K,那么此二叉树最多有 2K-1 个结点。
- 二叉树中,终端结点数(叶子结点数)为 n0,度为 2 的结点数为 n2,则 n0=n2+1。
二叉树的遍历
二叉树的遍历方式主要有:先序遍历、中序遍历、后序遍历、层次遍历。先序、中序、后序其实指的是父节点被访问的次序。若在遍历过程中,父节点先于它的子节点被访问,就是先序遍历;父节点被访问的次序位于左右孩子节点之间,就是中序遍历;访问完左右孩子节点之后再访问父节点,就是后序遍历。不论是先序遍历、中序遍历还是后序遍历,左右孩子节点的相对访问次序是不变的,总是先访问左孩子节点,再访问右孩子节点。而层次遍历,就是按照从上到下、从左向右的顺序访问二叉树的每个节点。
先序遍历
代码如下:
//filename: BinTreeNode.h
template <typename T>
void travPre_R(BinTreeNode<T> * root) {//二叉树先序遍历算法(递归版)
if (!root) return;
cout << root->data;
travPre_R(root->LeftChild);
travPre_R(root->RightChild);
}
中序遍历
代码如下:
template <typename T>
void travIn_R(BinTreeNode<T> * root) {//二叉树先序遍历算法(递归版)
if (!root)
return;
travPre_R(root->LeftChild);
cout << root->data;
travPre_R(root->RightChild);
}
1.8采用递归和非递归对二叉树进行遍历?
这道题想考察什么?
1、二叉树的基本原理和遍历的方法?
考察的知识点
二叉树遍历的基本概念、二叉树的基本原理
考生如何回答
二叉树的基本概念
简单地理解,满足以下两个条件的树就是二叉树:
- 本身是有序树;
- 树中包含的各个节点的度不能超过 2,即只能是 0、1 或者 2;
二叉树的遍历
- 前序遍历:每个树的遍历顺序为:根节点→左节点→右节点。上图的前序遍历输出为:FCADBEHGM
- 中序遍历:每个树的遍历顺序为:左节点→根节点→右节点。上图的前序遍历输出为:ACBDFHEMG
- 后序遍历:每个树的遍历顺序为:左节点→右节点→根节点。上图的前序遍历输出为:ABDCHMGEF
前序遍历
递归法:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private List<Integer> res = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
//中 ——> 左 ——> 右
preorder(root);
return res;
}
private void preorder(TreeNode node){
if(node == null) return;
res.add(node.val);
preorder(node.left);
preorder(node.right);
}
}
非递归法:
===基本的算法思想===
创建一个栈,用来储存遍历的轨迹:
1.如果栈不为空则储存当前栈顶元素的值,并弹栈;
2.如果栈顶元素存在右儿子,将右儿子压入;
3.如果栈顶元素有左儿子,将左儿子压入
4.重复1直至栈为空
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while(cur != null || !stack.isEmpty()){
if(cur != null){
res.add(cur.val);
stack.push(cur);
cur = cur.left;
}else{
cur = stack.pop();
cur = cur.right;
}
}
return res;
}
}
中序遍历
递归法:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private List<Integer> res = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
inorder(root);
return res;
}
public void inorder(TreeNode node){
if(node == null) return;
inorder(node.left);
res.add(node.val);
inorder(node.right);
}
}
非递归法:
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while(cur != null || !stack.isEmpty()){
//压栈
if(cur != null){
stack.push(cur);
cur = cur.left;
}else{
//左边已经存完,弹栈
cur = stack.pop();
res.add(cur.val);
cur = cur.right;
}
}
return res;
}
}
后序遍历
递归法:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private List<Integer> res = new ArrayList<>();
public List<Integer> postorderTraversal(TreeNode root) {
//左右中
postorder(root);
return res;
}
private void postorder(TreeNode node){
if(node == null) return;
postorder(node.left);
postorder(node.right);
res.add(node.val);
}
}
非递归法:
基本的算法思想:
使用栈来记录遍历轨迹,并使用一个变量来储存上一次方法的元素,当当前元素左右儿子为空或当前元素已经在上一轮访问过(即上一次方法访问的元素为当前访问元素的节点),则栈顶元素出栈。
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if(root == null) return res;
Stack<TreeNode> stack = new Stack<>();
TreeNode pre = null;
stack.push(root);
while(!stack.isEmpty()){
TreeNode cur = stack.peek();
if((cur.left == null && cur.right == null)
|| (pre != null && (cur.right == pre || cur.left == pre))){
res.add(cur.val);
pre = cur;
stack.pop();
}else{
if(cur.right != null) stack.add(cur.right);
if(cur.left != null) stack.add(cur.left);
}
}
return res;
}
}