Skip to content

Latest commit

 

History

History
189 lines (156 loc) · 4.95 KB

树.md

File metadata and controls

189 lines (156 loc) · 4.95 KB
Raw

树

概述

  • 树是一个或多个结点的有限集合，且其中：

    1. 存在一个称为根的特定结点；

    2. 其余的结点被分成n >= 0 个不相交的集合T1，T2，...，Tn，其中的每个集合都是一棵树。T1，T2，...，Tn称为根节点的子树。

  • 一个结点的度是指该结点的子树个数

  • 树的度是树中所有结点的度的最大值

二叉树

二叉树的主要特点是：任意给定结点的度都不会超过二。另外，二叉树可以没有任何结点，因此，二叉树和树实际上是两个完全不同的概念。

定义： 二叉树是有限多个结点的集合，这个集合或者是空集，或者由一个根结点和两颗互不相交的、分别称为左子树和右子树的二叉树组成。

二叉树的性质

  1. [结点数的最大值]：
  • 在二叉树中，第i层的结点数最多为2^(i - 1)，i >= 1。
  • 在深度为k的二叉树中，结点总数最多为2^k - 1，k >= 1。
  1. [叶子结点的个数与度为2的结点个数之间的关系]：对任何非空的二叉树T，如果叶结点的个数为n0，而度为2的结点数为n2，则n0 = n2 + 1。

前序遍历

private void preOrder(Node<T> node, Action<T> action) {
    if (node != null) {
        action.onAction(node.getValue());
        preOrder(node.getLeftChild(), action);
        preOrder(node.getRightChild(), action);
    }
}

中序遍历

private void inOrder(Node<T> node, Action<T> action) {
    if (node != null) {
        inOrder(node.getLeftChild(), action);
        action.onAction(node.getValue());
        inOrder(node.getRightChild(), action);
    }
}

后序遍历

private void postOrder(Node<T> node, Action<T> action) {
    if (node != null) {
        postOrder(node.getLeftChild(), action);
        postOrder(node.getRightChild(), action);
        action.onAction(node.getValue());
    }
}

层序遍历

private void levelOrder(Node<T> root, Action<T> action) {
    Queue<Node<T>> queue = new LinkedList<>();
    queue.offer(root);    //把根结点放入
    while (true) {
        Node<T> node = queue.poll();
        if (node != null) {
            action.onAction(node.getValue());   //获取该结点的值
            if (node.getLeftChild() != null) {
                queue.offer(node.getLeftChild());  //左结点插入
            }
            if (node.getRightChild() != null) {
                queue.offer(node.getRightChild());  //右结点插入
            }
        } else {
            break;
        }
    }
}

线索二叉树

二叉树的链式存储中，空链的数目大于非空链的数目。再总共2n个链中，有n+1个是空链。

二叉树添加了直接指向结点的前驱和后继的指针的二叉树称为线索二叉树。

线索二叉树能线性地遍历二叉树，从而比递归中的中序遍历更快。

定义

一个二叉树通过如下的方法“穿起来”：所有应该为空的右孩子指针指向该结点在中序序列中的后继，所有应该为空的左孩子指向该结点的中序序列的前驱。

中序遍历

/**
 * 找到本结点的中序后继结点
 *
 * @return
 */
ThreadedNode<T> insucc() {
    ThreadedNode<T> temp;
    temp = rightChild;
    if (!rightThread) { //右子树不是线索
        while (!temp.leftThread) {   //当左子树不是线索时一直沿着左子树链向下寻找
            temp = leftChild;
        }
    }
    return temp;
}

/**
 * 中序遍历
 * O(n)
 *
 * @param action
 */
public void inOrder(Action<T> action) {
    ThreadedNode<T> temp = root;
    while (true) {
        temp = temp.insucc();
        if (temp == root) break;
        action.onAction(temp.value);
    }
}

插入子结点

/**
 * 为本结点插入子节点
 *
 * @param child
 * @param isLeftChild
 */
public void insert(ThreadedNode<T> child, boolean isLeftChild) {
    ThreadedNode<T> temp;
    if (isLeftChild) {  //作为左结点
        child.leftThread = leftThread;
        child.leftChild = leftChild;
        child.rightChild = this;
        child.rightThread = true;
        leftChild = child;
        leftThread = false;
        if (!child.leftThread) {
            temp = child.inpre();
            temp.rightChild = child;
        }

    } else {    //作为右结点
        child.rightChild = rightChild;
        child.rightThread = rightThread;
        child.leftChild = this;
        child.leftThread = true;
        rightChild = child;
        rightThread = false;
        if (!child.rightThread) {    //如果子结点的右字数不是线索，即父节点原来的右子树不是线索
            temp = child.insucc();
            temp.leftChild = child;
        }
    }
}

/**
 * 找到本结点的中序前驱结点
 *
 * @return
 */
ThreadedNode<T> inpre() {
    ThreadedNode<T> temp;
    temp = leftChild;
    if (!leftThread) {
        while (!temp.rightThread) {
            temp = rightChild;
        }
    }
    return temp;
}