一,四种遍历二叉树的方式
1.根据访问结点操作发生位置命名**(前中后)序**
NLR: 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。(简洁记法"根左右") ** LNR:** 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中(间)。(简洁记法"左根右") LRN: 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。(简洁记法"左右根")
由于被访问的结点必是某子树的根,所以N(Node)、L(Left subtree)和R(Right subtree)又可解释为根、根 的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
示例: 如图是一颗二叉树, 1.首先我们来求它的前序遍历结果
ABDEC
2,中序遍历结果
DBEAC
3,后序遍历:
语言 |
方法 |
5928 |
AvB1l46q4J |
mu2QG |
抖音直播带货怎么做 |
1417 |
2011-02-01 06:30:37 |
DEBCA
2.二叉树的层序遍历
设二叉树的根节点所在层数为1,层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树根节点,然后从 左到右访问第2层上的节点,接着是第三层的节点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是 层序遍历
如上图:
层序遍历结果为: ABCDE
二,接着我们用代码来实现一颗树并且求他的遍历结果
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
class Node{ //写一个节点类
public char val;
public Node left;
public Node right;
public Node(char val) {
this.val = val;
}
}
public class TestTree {
public static Node buildTree(){ //构造出一棵树
Node a = new Node('A'); //创建树的结点
Node b = new Node('B');
Node c = new Node('C');
Node d = new Node('D');
Node e = new Node('E');
a.left = b; //把各个结点按照树的结构链接起来
a.right = c;
b.left = d;
b.right = e;
return a; //返回树的根节点
}
public static void preOrder(Node root){ //树的先序遍历
if(root == null){ //如果是空树就返回
return;
}
System.out.print(root.val + " "); //访问当前根结点的值
preOrder(root.left); //递归访问访问左子树
preOrder(root.right); //递归访问右子树
}
public static void inOrder(Node root){
if(root == null){
return;
}
inOrder(root.left);
System.out.print(root.val + " ");
inOrder(root.right);
}
public static void postOrder(Node root){
if(root == null){
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val + " " );
}
public static List<List<Character>> levelOrder(Node root) {
if(root == null) {
return new ArrayList<>();
}
List<List<Character>> res = new ArrayList<>(); //创建一个二维List内部List用来存储每层的数据
Queue<Node> queue = new LinkedList<Node>();
queue.add(root);
while(!queue.isEmpty()){
int count = queue.size(); //每次循环获取到的size为上次循环新进入的结点
List<Character> list = new ArrayList<>();
while(count > 0){
Node node = queue.poll();
list.add(node.val);
if(node.left != null)
queue.add(node.left);
if(node.right != null)
queue.add(node.right);
count--;
}
res.add(list);
}
return res;
}
public static void main(String[] args) {
Node tree = buildTree();//调用构造树方法
System.out.println("先序遍历:");
preOrder(tree);
System.out.println();
System.out.println("中序遍历:");
inOrder(tree);
System.out.println();
System.out.println("后序遍历:");
postOrder(tree);
System.out.println();
System.out.println("层序遍历:");
List<List<Character>> list = levelOrder(tree) ;
System.out.println(list);
}
}
结果展示:
|