- 一个空节点是二叉树(即什么都没有)
- 一棵二叉树有一个根节点,可以有左、右子树,而子树本身也是二叉树
左右子树高度差不超过1的二叉树
遍历 前序遍历先遍历根节点,再遍历左子树,再遍历右子树即:
A-B-D-F-G-H-I-E-C
先遍左子树,再遍历根节点,再遍历右子树:
A-B-D-F-G-H-I-E-C
先遍左子树,再遍历右子树,再遍历根节点:
F-H-I-G-D-E-B-C-A
一层一层的遍历:
A-B-C-D-E-F-G-H-I
public class Node {
private String data;
private Node leftNode;
private Node rightNode;
public Node(String data,Node leftNode,Node rightNode){
this.data = data;
this.leftNode = leftNode;
this.rightNode = rightNode;
}
public String getData(){
return this.data;
}
public Node getLeftNode(){
return this.leftNode;
}
public Node getRightNode(){
return this.rightNode;
}
}
import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;
public class TraverseTool {
//前序遍历
public void preTraverse(Node node){
System.out.print(node.getData());
if(node.getLeftNode() != null){
preTraverse(node.getLeftNode());
}
if(node.getRightNode() != null){
preTraverse(node.getRightNode());
}
}
//中序遍历
public void midTraverse(Node node){
if(node.getLeftNode() != null){
midTraverse(node.getLeftNode());
}
System.out.print(node.getData());
if(node.getRightNode() != null){
midTraverse(node.getRightNode());
}
}
//后续遍历
public void postTraverse(Node node){
if(node.getLeftNode() != null){
postTraverse(node.getLeftNode());
}
if(node.getRightNode() != null){
postTraverse(node.getRightNode());
}
System.out.print(node.getData());
}
//层序遍历,利用队列先进先出的功能,每一次都先遍历上一层的子节点
public void seqTraverse(Node node){
Queue queue = new LinkedBlockingQueue<>();
queue.add(node);
Node nextNode;
while (!queue.isEmpty()){
nextNode = queue.remove();
if(nextNode.getLeftNode() !=null){
queue.add(nextNode.getLeftNode());
}
if(nextNode.getRightNode() !=null){
queue.add(nextNode.getRightNode());
}
System.out.print(nextNode.getData());
}
}
}
把任意树转化为二叉树
用以下方法可以将任意树转化成二叉树,且可以恢复到之前的树
- 对每一个节点,将其的第一棵子树变为左子树,如图中的B
- 将上述产生的左子树节点右边的兄弟树变为该左子树节点的右子树如C,D



