提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  Java

当前栏目

数据结构 —— 二叉树的概念及Java实现

JAVA 数据结构
2023-03-14 22:47:01 时间

数据结构 —— 树的概念

树的基本概念

树是一种抽象数据类型，或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。如下图所示：

树形结构的价值：

  1. 空间利用率大；
  2. 可以非常快速的查找到值；

由于大部分对树的操作的时间复杂度可以被干到O(LogN)，所以常常被用于索引。树的应用十分广泛，操作系统的文件目录就是典型的树形结构。

树的定义

树是n（n >= 0）个结点组成的、具有层次关系的有限集合。当n=0时，称为空树。在任意一棵非空树中，应该满足：

1、有且仅有一个特定的结点可以被称为根结点。

2、每个结点有0个或者多个子结点。除根结点外，所有结点有且只有一个前驱。

3、当n>1时，其他结点可分为m（m>0）个互不交集的有限集T1,T2,...,TM，其中每个集合本身又是一棵树，并且成为根的子树。

可以看出，树是一种递归的数据结构。

基本术语

术语名

含义

结点的度

结点拥有的子树个数

叶子结点

度为0的结点

分支结点

度大于0的结点

父结点

衍生出其它结点的结点为这些结点的父结点

子结点

被某个结点衍生出来的结点为该结点的子结点

兄弟结点

具有同一个父节点的所有结点为兄弟结点

结点的层次

设定根结点所在层次为1，其它结点层次为其父节点层次+1

结点的深度

节点的深度是根节点到这个节点所经历的边的个数

结点的高度

节点的高度是该节点到叶子节点的最长路径（边数）树的高度 = 根节点的高度

路径

从某个结点沿着树的层级关系到达另一个结点之间的路线

路径长度

路径上的结点个数 -1

树的分类

树的存储结构

二叉树

二叉树是一种特别的树形结构，其特点是每个结点至多只有2棵树（不存在度大于2的结点），且两颗子树有左右区分，次序不能随意颠倒。

二叉树定义

二叉树也以递归的形式定义。二叉树是n (n≥0) 个结点的有限集合:

  1. 或者为空二叉树，即n=0。
  2. 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。

几个特殊的二叉树

  1. 斜树（左斜树、右斜树）
  2. 满二叉树：一棵高度为h，且含有2h − 1个结点的二叉树称为满二叉树，即树中的每层都含有最多的结点。满二叉树的叶子结点都集中在二叉树的最下一层，并且除叶子结点之外的每个结点度数均为2。
  3. 完全二叉树：高度为h、有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时，称为完全二叉树。
  4. 二叉排序树：左子树上所有结点的关键字均小于根结点的关键字，右子树上所有结点的关键字均大于根结点的关键字。左子树和右子树又各是一棵二叉排序树。
  5. 平衡二叉树：树上任一结点的左子树和右子树，深度之差不超过1。

二叉树存储结构

  1. 顺序存储 根据完全二叉树定义的结构，数组存储。0表示没有内容。 缺点：如果数据稀疏，非常浪费空间。
  1. 链式存储（常见） 二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域是比较自然的想法，我们称这样的链表叫做二叉链表。

二叉树的实现（Java，链式）

// 首先实现单个结点的数据结构
public class TreeNode {
    public int value;
    public TreeNode leftChild = null;
    public TreeNode rightChild = null;
    
    public TreeNode(int value) {
        this.value = value;
    }
}
// 实现抽象类, 定义树的接口
public abstract class AbstractTree {
    int count = 0;
    public abstract TreeNode find(int value);
    public abstract boolean insert(int value);
    public abstract boolean delete(int value);
    public int count(){
        return this.count;
    }
}
// 实现抽象类
public class BinaryTree extends AbstractTree {
    public TreeNode root;
​
    public BinaryTree() {}
​
    public BinaryTree(TreeNode root) {
        this.root = root;
    }
​
    @Override
    public TreeNode find(int value) {
        TreeNode current = root;
        while (current != null) {
            if (current.value < value) {
                current = current.rightChild;
            } else if (current.value > value) {
                current = current.leftChild;
            } else {
                return current;
            }
        }
        return null;
    }
​
    @Override
    public boolean insert(int value) {
        TreeNode newNode = new TreeNode(value);
        if (root == null) {
            root = newNode;
            return true;
        }
​
        TreeNode current = root;
        while (current != null) {
            if (current.value < value) {
                if (current.rightChild == null) {
                    current.rightChild = newNode;
                    count++;
                    return true;
                } else {
                    current = current.rightChild;
                }
​
            } else if (current.value > value) {
                if (current.leftChild == null) {
                    current.leftChild = newNode;
                    count++;
                    return true;
                } else {
                    current = current.leftChild;
                }
            }
        }
​
        return false;
    }
​
    @Override
    public boolean delete(int value) {
​
        TreeNode node = root;
        TreeNode parent = null;
        String childFlag = "";
        while (node != null && node.value != value) {
            if (node.value < value) {
                parent = node;
                childFlag = "right";
                node = node.rightChild;
            } else if (node.value > value) {
                parent = node;
                childFlag = "left";
                node = node.leftChild;
            }
        }
​
        if (node != null) {
            // 1. 待删除结点的左右节点均为空
            if (node.leftChild == null && node.rightChild == null) {
                switch (childFlag) {
                    case "right": parent.rightChild = null;break;
                    case "left": parent.leftChild = null;break;
                }
            }
​
            // 2. 待删除结点的左右节点有一个不为空
            if (node.leftChild != null && node.rightChild == null) {
                switch (childFlag) {
                    case "right": parent.rightChild = node.leftChild; break;
                    case "left": parent.leftChild = node.leftChild; break;
                }
            } else if (node.leftChild == null && node.rightChild != null) {
                switch (childFlag) {
                    case "right": parent.rightChild = node.rightChild; break;
                    case "left": parent.leftChild = node.rightChild; break;
                }
            }
            // 3. 待删除结点左右结点均不为空, 右边结点成为新结点, 左边结点挂到右边结点的左分支下
            if(node.leftChild != null && node.rightChild != null) {
                TreeNode nodeToInsertLeft = node.rightChild;
                while(nodeToInsertLeft.leftChild != null) {
                    nodeToInsertLeft = nodeToInsertLeft.leftChild;
                }
                switch (childFlag) {
                    case "right": parent.rightChild = node.rightChild; break;
                    case "left": parent.leftChild = node.rightChild; break;
                }
                nodeToInsertLeft.leftChild = node.leftChild;
            }
            node = null;
            count--;
            return true;
        }
        return false;
    }
}

二叉树的遍历

先(根)序遍历（根左右）：A B D H E I C F J K G

中(根)序遍历（左根右） : D H B E I A J F K C G

后(根)序遍历（左右根） : H D I E B J K F G C A

先序遍历

/** "根左右"
 * 先访问根结点；
 * 先序遍历左子树；
 * 先序遍历右子树；
*/
void preOrder(TreeNode node) {
    if(node != null) {
        System.out.print(node.value + " ");
        preOrder(node.leftChild);
        preOrder(node.rightChild);
    }
}

中序遍历

/** "左根右"
 * 先序遍历左子树；
 * 访问根结点；
 * 先序遍历右子树；
*/
void inOrder(TreeNode node) {
    if(node != null) {
        inOrder(node.leftChild);
        System.out.print(node.value + " ");
        inOrder(node.rightChild);
    }
}

后序遍历

/** "左右根"
 * 先序遍历左子树；
 * 先序遍历右子树；
 * 访问根结点；
*/
void postOrder(TreeNode node) {
    if(node != null) {
        postOrder(node.leftChild);
        postOrder(node.rightChild);
        System.out.print(node.value + " ");
    }
}

层递遍历

层次遍历：即按照箭头所指方向，按照1,2,3, 4的层次顺序，对二叉树中的各个结点进行访问。

相关文章