DS05.1:树与二叉树

树

基本名词

1、度

节点拥有的子树的数目称为度

4、层次与深度

从根开始定义，根为第一层，根的孩子为第二层，以此类推

树中结点的最大层次数称为树的深度或高度

二叉树

基本性质

基本特点

1、每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点。

2、左子树和右子树是有顺序的，次序不能任意颠倒。

3、即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

特殊的树

1、满二叉树：如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

2、完全二叉树：对一颗具有n个结点的二叉树按层编号，如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。

完全二叉树有以下特性（按层编号作为索引），可以用来构建堆结构:

（1）父节点的编号为i/2。i为孩子节点的编号

（2）左子节点编号为2*i+1。i为父节点编号

数学性质

1、在二叉树的第i层上最多有2i-1个节点 （i>=1）

2、二叉树中如果深度为k，那么最多有2k-1个节点(k>=1）

基础实现

二叉树的节点，与之前提到的链表的节点很相似，只不过有两个引用，在Java中可以作为一个类中类。

class Node {
	E e;
	Node left;
	Node right;
}

二叉树所需要的基础方法如下，该基础实现与之后要讲的二叉搜索树是一致的，因此此处类名直接采用BST。

public class BST<E extends Comparable<E>> {
    private class Node {
        public E e;
        public Node left, right;

        public Node(E e) {
            this.e = e;
            left = null;
            right = null;
        }
    }

    private Node root;
    private int size;

    public BST() {
        root = null;
        size = 0;
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size==0;
    }
}

遍历操作

遍历操作就是把所有节点都访问一遍，由于树的定义天生就带有递归特性，因此使用递归进行遍历是最简单的，但也可以使用普通的迭代方法。

二叉树中的几种遍历

PreOrder Traversal （前序遍历）
InOrder Traversal （中序遍历）
PostOrder Traversal （后序遍历）
LevelOrder Traversal （层序遍历）

规律：显然，中序遍历可以与其余三种遍历方法的任何一种完成对二叉树的重建（唯一），而其余三种遍历方法任何一种两两结合都无法构建唯一的二叉树。
这很好理解，其余三种遍历方法告知了我们根节点的位置，而根据这一点我们可以由中序遍历确定左右子树，然后根据二叉树的递归定义完成重建

前三种遍历方法可以依靠递归轻松实现，其不同之处仅在于递归语句中用于遍历当前节点的语句所处的位置，如下。

// 前序遍历处理当前节点位置
递归（左子树）;
// 中序遍历处理当前节点位置
递归（右子树）;
// 后续遍历处理当前节点位置

其中具体代码可见迭代实现中所示。

前三种遍历都可以依靠递归进行简单的实现，可以简单理解为深度优先，而最后一种层序遍历则为广度优先，依靠队列即可进行实现，其实现方法如下：

public void levelOrder() {
    Queue<Node> q = new LinkedList<>();
    q.add(root);
    while (!q.isEmpty()) {
        Node cur = q.remove();
        System.out.println(cur.e);
        if(cur.left != null) q.add(cur.left);
        if(cur.right != null) q.add(cur.right);
    }
}

递归实现

具体可见（写的很详细）：https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution/leetcodesuan-fa-xiu-lian-dong-hua-yan-shi-xbian-2/

1、前序遍历

private void preOrder(Node node) {
    if(node == null) return;
    System.out.println(node.e);
    preOrder(node.left);
    preOrder(node.right);
}

中序遍历和后序遍历如上所述，只是改变操作位置

迭代实现

前序遍历

public void preOrderNR() {
    Stack<Node> stack = new Stack<>();
    stack.push(root);
    while(!stack.isEmpty()) {
        Node cur = stack.pop();
        System.out.println(cur.e);
        if(cur.right != null) stack.push(cur.right);
        if(cur.left != null) stack.push(cur.left);
    }
}

参考链接：

https://www.jianshu.com/p/bf73c8d50dc2

Donate