您的位置: 首页  >  文章  >  二叉树及其遍历

二叉树及其遍历

分类: 文章 • 2025-04-14 15:57:10

二叉树是每个节点最多只有两个分支的树结构，两个分支一般称为左子数和右子树。二叉树的分支具有左右次序，不能颠倒。
二叉树通常作为数据结构应用，应用于高效率的搜索和排序，红黑树、B树等都属于它的变体。红黑树（Red-Black Tree）的实际应用非常广泛，比如Linux内核中的ext3文件系统、Java的HashMap、TreeMap和TreeSet，C++ STL的map。

满足一定条件的二叉树人们给它起了一个新名字，如满二叉树、完全二叉树、平衡二叉树（AVL与红黑树都属于平衡二叉树）。B树不属于二叉树，它可以有大于两个子节点。（二叉树的相关类型术语并不是严格统一和规范的，不同的文献描述略有不同）

二叉树及其遍历

  • 满二叉树（Full Binary Tree）：所有的非叶子结点都有两个孩子，所有的叶子结点都在同一层。即每层结点都完全填满。
  • 完全二叉树(Complete Binary Tree)： 每层结点都完全填满，在最后一层上如果不是满的，则只缺少右边的若干结点。
二叉树及其遍历
二叉查找树

二叉查找树(Binary Search Tree)，也称二叉搜索树、有序二叉树(ordered binary tree)、排序二叉树(sorted binary tree)，是指一棵空树或者具有下列性质的二叉树：

  1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
  2. 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
  3. 任意节点的左、右子树也分别为二叉查找树；
  4. 没有键值相等的节点。(上面的三条可以推出第四条）

一般情况下，最好不要在树中再追加一个重复结点，而是在重复节点的附加域中进行”+1“操作。

二叉树及其遍历

AVL树：最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。AVL树的前提是二叉排序树。

二叉树遍历

二叉树的遍历有深度优先遍历、广度优先遍历两种方式，深度优先可进一步按照根节点相对于左右子节点的访问先后来划分。

  • 先序遍历：根节点 --> 先序遍历左节点 --> 先序遍历右节点
  • 中序遍历：中序遍历左节点 --> 根节点 --> 中序遍历右节点
  • 后序遍历：后序遍历左节点 --> 根节点 --> 后序遍历右节点

对广度优先而言，遍历没有前序中序后序之分。本文讨论二叉树的先序、中序、后序遍历。 如何在程序中构造一个二叉树呢？我们知道，二叉树无非就是由两部分组成，一是节点，二是节点间的边。 首先构造一个节点，因为是二叉树，所以有左孩子（left）、右孩子（right）以及本身的值（value）三个属性。

class Node {
    private int value;
    private Node left;
    private Node right;
    
    public Node() {}    
    public Node(int value) {
    	this.value = value;
    }    
    public int getValue() {
    	return value;
    }    
    public void setValue(int value) {
    	this.value = value;
    }    
    public Node getLeft() {
    	return left;
    }    
    public void setLeft(Node left) {
    	this.left = left;
    }    
    public Node getRight() {
    	return right;
    }    
    public void setRight(Node right) {
    	this.right = right;
    }
}

下面是用递归算法完成的先序、中序、后序遍历

​
public class TreeNode {
    public Node create() {
        // 初始化节点
        Node node0 = new Node(0);
        Node node01 = new Node(1);
        Node node02 = new Node(2);
        Node node11 = new Node(3);
        Node node12 = new Node(4);
        Node node21 = new Node(5);
        // 为node节点赋予左右孩子
        node0.setLeft(node01);
        node0.setRight(node02);
        node01.setLeft(node11);
        node01.setRight(node12);
        node02.setLeft(node21);
        // 返回根节点
        return node0;
    }    
    /**
     * 先序遍历
     * @param node
     */
    public void preOrder(Node node) {
    	if (node == null) {
    		return;
    	}
    	System.out.print(node.getValue() + " ");
    	preOrder(node.getLeft());
    	preOrder(node.getRight());
    }
    
    /**
     * 中序遍历
     * @param node
     */
    public void inOrder(Node node) {
    	if (node == null) {
    		return;
    	}
    	inOrder(node.getLeft());
    	System.out.print(node.getValue() + " ");
    	inOrder(node.getRight());
    }
    
    /**
     * 后序遍历
     * @param node
     */
    public void postOrder(Node node) {
    	if(node == null) {
    		return;
    	}
    	postOrder(node.getLeft());
    	postOrder(node.getRight());
    	System.out.print(node.getValue() + " ");
    }
    
    public static void main(String[] args) {
    	TreeNode tree = new TreeNode();
    	Node node = tree.create();
    	System.out.print("先序遍历： ");
    	tree.preOrder(node);
    	System.out.println();
    	System.out.print("中序遍历： ");
    	tree.inOrder(node);
    	System.out.println();
    	System.out.print("后序遍历： ");
    	tree.postOrder(node);
    }
}

​

输出结果：

先序遍历： 0 1 3 4 2 5 
中序遍历： 3 1 4 0 5 2 
后序遍历： 3 4 1 5 2 0

 

相关推荐