二叉树（binary tree）

作者: kylinxiang | 来源:发表于2017-07-04 20:56 被阅读86次

二叉树的定义####

二叉树是n(n>=0)个具有相同类型的元素的有限集合，当n=0时称为空二叉树，当n>0时，数据元素被分为一个称为根（Root）的数据元素及两棵分别为左子树和右子树的数据元素的集合，左、右子树互不相交，且左、右子树都为二叉树。在二叉树中，一个元素也称为一个节点。

二叉树的子树是有序的，即若将其左、右子树颠倒，就将成为另一棵不同的二叉树。即使树中的节点只有一棵子树，也要明确指出其是左子树还是右子树。由于左、右子树的有序以及二叉树可以为空，因此，二叉树具有以下五种基本形态，即空二叉树、仅有根节点的二叉树、右子树为空的二叉树、左子树为空的二叉树、左右子树均为非空的二叉树，如下图所示：

二叉树的五种基本情形

二叉树的基本概念####

节点的度：节点所拥有子树的个数称为该节点的度。
叶子：度为0的节点称为叶子。
孩子：节点子树的根，称为该节点的孩子。二叉树中，孩子有左右之分，分别为左孩子和右孩子。
双亲：孩子节点的上层节点都称为该节点的双亲。
以某节点的根的子树中的除根节点之外的任意一个节点都称为该节点的子孙。
祖先：节点的祖先是从根到该节点所经分支上的所有节点。
节点的层次：从根节点起，跟为第一层，他的孩子为第二层，孩子的孩子为第三层，依次类推，即某个节点的层次为L层，那么他的孩子节点的层数为L+1层。
兄弟：同一双亲的孩子互为兄弟。
堂兄弟：其双亲在同一层的节点互为堂兄弟。
二叉树的度：二叉树中最大的节点度称为二叉树的度。
二叉树的深度：二叉树中节点的最大层次书被称为二叉树的深度。
满二叉树：在一棵二叉树中，所有分支节点都存在左子树和右子树，并且所有叶子节点都在同一层上，这样的二叉树被称为满二叉树。
完全二叉树：对深度为k的满二叉树中的节点从上至下、从左至右从1开始编号。对一棵具有n个节点、深度为k的二叉树，采用的同样的办法对树中的节点从上至下，从左至右从1开始连续编号，如果编号为i（i<=n）的节点与满二叉树中编号为i的节点在同一位置，则称此二叉树为完全二叉树。对于一棵完全二叉树，其叶子节点只可能出现在最下层和倒数第二层，而最下层的叶子集中在树的最左部。

满二叉树和完全二叉树

二叉树的性质####

一棵非空二叉树的第i层最多有2^(i-1)个节点。
深度为k的二叉树至多有2^k-1个节点。
对任何一棵二叉树T，如果叶子节点数为n0，度为2的节点数为n2，那么n0=n2+1。
具有n个节点的安全二叉树的深度k=log2N+1（简书不支持公式。。。这里解释一下，k=以2为底N的对数向下取整+1）。
对一棵具有n个节点的完全二叉树的从上至下，从左至右从1开始连续编号，那么对任意一个节点i有：
如果i=1,则节点i是二叉树的根，无双亲；如果i>1，则其双亲是i/2向下取整。
如果2i>n，则节点无左孩子，为叶子节点；如果2i<n，则其左孩子是2i。
如果2i+1>n，则节点i无右孩子；如果2i+1<=n，则其右孩子为2i+1。

性质5

二叉树的存储结构####

顺序存储######

完全二叉树的顺序存储
我们先看以下完全二叉树的顺序存储。要存储一棵完全二叉树，不仅需要二叉树的节点数据，还需要存储它的结构信息，即双亲和孩子关系信息。从上面的性质5可以看出，完全二叉树中节点i的左孩子为2i，右孩子为2i+1，双亲为i/2向下取整。因此，如果将完全二叉树从上至下，从左至右从1开始编号，把编号为i的节点放在线性存储单元的第i个位子，那么其左孩子存储在2i位子，右孩子存储在2i+1位子，则孩子和双亲的关系就体现出来了。

完全二叉树的顺序存储
一般二叉树的顺序存储
对于一般二叉树而言，如果把它的节点按照从上至下、从左至右从1开始连续编号存储在一维的存储单元，那么无法反应其节点间的双亲孩子关系，即不能反映二叉树的结构关系，怎么办呢?可以把一般的二叉树补成一棵完全二叉树，这样，它就可以按照完全二叉树的顺序存储方式存储了，只是新补上去的节点只占位子，不存放节点数据。如下图所示：

一般二叉树的顺序存储

对于一般二叉树，需要增加一些节点才能存储此二叉树的节点数据和结构关系，这样可能会造成存储空间的浪费，例如，对于深度为3的右偏斜二叉树，需要额外增加4个存储单位。当二叉树的深度更深时，则需要更多的节点，例如当深度为100的右偏斜二叉树，需要2^100-101个额外空间，为了采用顺序存储方式来存储此二叉树，把全世界所有计算机的存储空间加起来也不够！因此很有必要采用其他形式的存储方式。

右偏斜二叉树的顺序存储

链式存储######

链表可以用来表示一维的线性结构，也可以用来表示非线性的二叉树结构。二叉树的链式存储结构常有二叉链表存储、三叉链表存储及线索链表。二叉链表中有两个指针域，分别指向其左、右孩子；三叉链表中除了指向其左、右孩子的指针域外，还有指向其双亲的指针域；线索链表是为了反映节点的前驱、后继而将二叉链表中空指针指向其前驱或后继而形成的链式存储结构。

二叉链表和三叉链表的结构

二叉链表存储
链表中每一个节点包含3个域：数据域、左孩子指针域、右孩子指针域。左、右孩子指针域分别指向左孩子和右孩子的存储地址。

二叉链表存储

二叉链表存储代码实现######

public class BinaryTreeNode<T> {
    private T data;
    private BinaryTreeNode<T> leftChild;
    private BinaryTreeNode<T> rightChild;

    public BinaryTreeNode(T data) {
        this(data, null, null);
    }

    public BinaryTreeNode(T data, BinaryTreeNode<T> leftChild, BinaryTreeNode<T> rightChild) {
        this.leftChild = leftChild;
        this.rightChild = rightChild;
        this.data = data;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public BinaryTreeNode<T> getLeftChild() {
        return leftChild;
    }

    public void setLeftChild(BinaryTreeNode<T> leftChild) {
        this.leftChild = leftChild;
    }

    public BinaryTreeNode<T> getRightChild() {
        return rightChild;
    }

    public void setRightChild(BinaryTreeNode<T> rightChild) {
        this.rightChild = rightChild;
    }

}

三叉链表存储
在三叉链表中，除根节点的parent域为空外，其余节点的parent域都不为空，指向其双亲。因此在三叉链表中，查找孩子和双亲都是很快捷的，但是增加了一些额外空间开销。

三叉链表存储结构

三叉链表存储实现#####

public class BinaryTreeNode3<T> {
    private T data;
    private BinaryTreeNode3<T> leftChild;
    private BinaryTreeNode3<T> parent;
    private BinaryTreeNode3<T> rightChild;

    // 叶子节点构造器
    public BinaryTreeNode3(T data, BinaryTreeNode3<T> parent) {
        this(data, null, parent, null);
    }

    // 一般节点构造器
    public BinaryTreeNode3(T data, BinaryTreeNode3<T> leftChild, BinaryTreeNode3<T> parent,
            BinaryTreeNode3<T> rightChild) {
        this.leftChild = leftChild;
        this.parent = parent;
        this.rightChild = rightChild;
        this.data = data;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public BinaryTreeNode3<T> getLeftChild() {
        return leftChild;
    }

    public void setLeftChild(BinaryTreeNode3<T> leftChild) {
        this.leftChild = leftChild;
    }

    public BinaryTreeNode3<T> getParent() {
        return parent;
    }

    public void setParent(BinaryTreeNode3<T> parent) {
        this.parent = parent;
    }

    public BinaryTreeNode3<T> getRightChild() {
        return rightChild;
    }

    public void setRightChild(BinaryTreeNode3<T> rightChild) {
        this.rightChild = rightChild;
    }

}

二叉树的遍历####

先序、中序、后续的递归遍历######

例子

遍历的二叉树

代码

public class BinaryTree<T> {

    public BinaryTree() {
        // ...
    }

    // 访问数据
    public void visitData(BinaryTreeNode<T> node) {
        System.out.print(node.getData() + " ");
    }

    // 前序遍历
    public void preOrder(BinaryTreeNode<T> node) {
        if (null != node) {
            visitData(node);
            preOrder(node.getLeftChild());
            preOrder(node.getRightChild());
        }
    }

    // 中序遍历
    public void inOrder(BinaryTreeNode<T> node) {
        if (null != node) {
            inOrder(node.getLeftChild());
            visitData(node);
            inOrder(node.getRightChild());
        }
    }

    // 后续遍历
    public void postOrder(BinaryTreeNode<T> node) {
        if (null != node) {
            postOrder(node.getLeftChild());
            postOrder(node.getRightChild());
            visitData(node);
        }
    }

    public static void main(String[] args) {
        BinaryTreeNode<String> g = new BinaryTreeNode<String>("g");
        BinaryTreeNode<String> c = new BinaryTreeNode<String>("c");
        BinaryTreeNode<String> d = new BinaryTreeNode<String>("d");
        BinaryTreeNode<String> b = new BinaryTreeNode<String>("b", c, d);
        BinaryTreeNode<String> f = new BinaryTreeNode<String>("f", g, null);
        BinaryTreeNode<String> e = new BinaryTreeNode<String>("e", null, f);
        BinaryTreeNode<String> a = new BinaryTreeNode<String>("a", b, e);

        BinaryTree<String> binaryTree = new BinaryTree<String>();

        System.out.print("preOder:");
        binaryTree.preOrder(a);
        System.out.println();

        System.out.print("inOder:");
        binaryTree.inOrder(a);
        System.out.println();

        System.out.print("postOder:");
        binaryTree.postOrder(a);
        System.out.println();

    }
}

执行结果

递归遍历的结果

非递归遍历的思想######

当非递归遍历时，我们需要从根节点开始，从左到右深入到每一个叶子。当深入到一个叶子节点时，需要返回到其父节点，然后去深入其他分支。可以看出深入和返回是一对相反的操作，所以可以用到数据结构栈来保存深入节点时树的结构关系。至于该遍历是先序、中序或是后序，这只取决于其访问

非递归的中序遍历######

沿左子树深入时，深入一个节点入栈一个节点，沿左分支无法继续深入时（某个节点无左孩子），出栈，出站时同时访问节点数据，然后从该节点的右子树继续沿左子树深入，这样一直下去，最后从根节点的右子树返回时结束。

    // 非递归的中序遍历
    public void nrInOrder(BinaryTreeNode<T> root) {
        // 声明一个栈
        Stack<BinaryTreeNode<T>> stack = new Stack<BinaryTreeNode<T>>();
        // 当前节点
        BinaryTreeNode<T> p = root;
        // 当节点和栈不同时为空时
        while (!(p == null && stack.isEmpty())) {
            // 遍历p节点下的所有左孩子
            while (p != null) {
                // 将左孩子压栈
                stack.push(p);
                p = p.getLeftChild();
            }
            if (stack.isEmpty()) {
                return;
            } else {
                p = stack.pop();// 出栈
                visitData(p);// 出栈时访问数据
                p = p.getRightChild();// 指向右孩子
            }

        }
    }

非递归的层次遍历######

从根节点开始，根节点入队，访问其数据，然后根节点的左右孩子入队，根节点出队。此时相当于第一层遍历完毕。第二层数据已经入队。然后当前队首元素出队，访问数据，加入当前元素的左右孩子，依次类推直到队列为空。

public void levelOrder(BinaryTreeNode<T> root) {
        // 声明一个队列
        Queue<BinaryTreeNode<T>> queue = new LinkedList<BinaryTreeNode<T>>();
        // 如果二叉树为空，直接返回
        if (null == root) {
            return;
        }
        // 根节点入队
        queue.add(root);
        // 临时变量，用来保存上一次出队的元素
        BinaryTreeNode<T> temp;
        // 遍历队列，直到队列为空
        while (!queue.isEmpty()) {
            // 出队
            temp = queue.remove();
            // 访问刚才出队元素的数据
            visitData(temp);
            // 若刚才出队的元素（节点）有左孩子，则左孩子入队
            if (null != temp.getLeftChild()) {
                queue.add(temp.getLeftChild());
            }
            // 若刚才出队的元素（节点）有左孩子，则左孩子入队
            if (null != temp.getRightChild()) {
                queue.add(temp.getRightChild());
            }
        }
    }

二叉树（binary tree）

二叉树的定义####

二叉树的基本概念####

二叉树的性质####

二叉树的存储结构####

顺序存储######

链式存储######

二叉链表存储代码实现######

三叉链表存储实现#####

二叉树的遍历####

先序、中序、后续的递归遍历######

非递归遍历的思想######

非递归的中序遍历######

非递归的层次遍历######

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

数据结构