数据结构（三）

大家好，欢迎来到IT知识分享网。

树

树型结构是一类非常重要的非线性数据结构，其中以二叉树最为常用。直观来看，树是以分支关系定义的层次结构。

树的术语

根（Root）：树的最顶端的结点（A），一个树仅有一个根节点，根节点无父节点。

子树（SubTree）：当树中的结点数大于一个时，根结点下面的子结点又可以做为根结点与其下面的结点组成一棵树，称为根结点的子树。（以B，C，D为根结点的树都是A的子树）

结点的度（Degree）：该结点拥有的子树个数。（如A的度为3，B的度为2，C的度为0，D的度为1）

叶子（Leaf）或终端节点：度为0（无子结点）的结点。（树A的叶节点为E，F，C，G）

非终端节点或分支节点：度不为0（非叶子结点）的结点。（树A的非终端节点为B，D）

孩子（Child）：结点的子树的根节点。（A的孩子为B，C，D）
双亲（Parent）：结点包含子结点，那么该结点就称为其子结点的双亲（父结点）。（B，C，D的双亲为A结点）

兄弟（Sibling）：同一个双亲的孩子结点之间互称为兄弟。（E，F为兄弟）
祖先：结点的祖先是从根结点到该结点所经分支上的所有结点。（E的祖先为B，A）

子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。（除A以外的结点都是A的子孙）

层次（Level）：从根节点开始定义，根为第一层，根节点的孩子为第二层。

堂兄弟：双亲在同一层的结点互称为堂兄弟。（E和G，F和G互为堂兄弟）

树的深度：树中结点的最大层次称为树的深度。（树A的深度为3）

有序树：如果将树中结点的各子树看成从左至右是有次序的（即不能互换顺序）。

无序树：如果树中的节点各子树可以互换次序，则称为无序树。

森林（Forest）：互不相交的树的集合。对树中的每个结点而言，其子树的集合称为森林。

二叉树

二叉树（Binary Tree）`是一种树形结构，特点是每个结点至多只有两颗子树（即二叉树中不存在度大于2的结点），并且二叉树的子树有左右之分，其次序不能任意颠倒。

满二叉树：一棵深度为k且有2^k-1个结点的二叉树称为满二叉树。满二叉树中每一层中的结点都是最大结点数，只包含饱和度为0和2的节点，且度为0的结点只能出现在最后一层。

完全二叉树：对于满二叉树，约定编号从根节点起，自上而下，自左至右。深度为k的，有n个结点的二叉树，当且仅当每一个结点都与深度为k的满二叉树中编号从1至n的节点一一对应时，称为完全二叉树。完全二叉树所有的叶结点都出现在最下面两层上，最下面一层的结点都集中在该层最左边的若干个位置。

二叉树的性质：

1.在二叉树的第i层上至多有2^i-1个节点（i>=1）。

2.深度为k的二叉树至多有2^k-1个节点（k>=1）。

3.对任意一颗二叉树T，如果其终端节点为n₀，度为2的结点数为n₂，则n₀=n₂+1。

4.具有n个结点的完全二叉树的深度为$ \lfloor log_2 n \rfloor + 1$。

5.如果对一棵有n个结点的完全二叉树（其深度为$\lfloor lo{g}_{2}n\rfloor +1$）的结点按层序编号（从第1层到第$\lfloor lo{g}_{2}n\rfloor +1$，每层从左至右），则对任一结点（1<=i<=n），有：

（1）如果i=1，则结点i是二叉树的根，根节点无双亲；如果i>1，则其双亲节点为$\lfloor i/2\rfloor$。

（2）如果2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是节点2i；

（3）如果2i+1>n，则结点i无右孩子，则结点i无右孩子；否则其右孩子是结点2i+1；

顺序存储结构（数组）：用一组地址连续的存储单元依次自上而下，自左至右存储完全二叉树上的结点元素，即将完全二叉树上的编号为i的结点元素存储在如上定义的一维数组中下标为i-1的分量中。0表示不存在次结点，这种结构仅适用于完全二叉树（空间利用率较高）。

链式存储结构（链表）：由二叉树的概念可知，二叉树的结点中至少包含三个区域，即数据域，左右指针域。为了方便找到双亲节点，还可以加入父节点指针。利用这种结点结构所得二叉树的存储结构分别称为二叉链表和三叉链表。

二叉树的方法：

1.创建根结点，获取根节点，为指定结点添加子结点

2.遍历：深度遍历（先序，中序，后序遍历），广度遍历

3.查找某个结点是否在树中，获取树中结点数，获取树的高度，获取树的叶结点数，获取结点的父节点

4.判断树是否为空，判断二叉树是否是完全二叉树

基于数组的二叉树

方法概述：

1.创建根结点（creatRoot），添加结点（add），树中结点数

2.树是否为空（isEmpty）

3.根据层数打印二叉树

public class ArrayBinaryTree<T> { 
    private T[] data; private int deep; private int capacity; private int size; / * 初始化需要提供二叉树的深度，可以计算出需要分配的数组大小 * @param deep:二叉树的深度 */ public ArrayBinaryTree(int deep) { 
    this.deep = deep; capacity = (int) Math.pow(2, deep) - 1; data = (T[]) new Object[capacity]; } / * 创建根节点 * @param value：根节点的值 */ public void creatRoot(T value) { 
    data[0] = value; size++; } / * 向二叉树中添加结点 * @param value：待插入结点的值 * @param index：待插入结点的父节点，也就是插入位置 * @param left：插入位置是否是左子结点 */ public void add(T value, int index, boolean left) { 
    if (2 * index + 1 >= capacity) { 
    throw new RuntimeException("树已满，无法继续插入！"); } if (data[index] == null) { 
    throw new RuntimeException("index节点为空，无法插入！"); } if (left) { 
    data[index * 2 + 1] = value; size++; } else { 
    data[index * 2 + 2] = value; size++; } } public boolean isEmpty() { 
    return data[0] == null; } public int size() { 
    return size; } public void print() { 
    for (int i = 1; i <= deep; i++) { 
    int k = (int) Math.pow(2, i - 1) - 1; int j = (int) Math.pow(2, i) - 2; System.out.print("第" + i + "层上的数据为："); while (k <= j) { 
    System.out.print(data[k++] + ","); } System.out.println(); } } } 

基于二叉链表的二叉树

方法概述：

1.创建根结点（creatRoot），为指定结点添加子节点（add）

2.获取根结点（getRoot），获取树中结点数量（size），获取树的高度（getHeight），获取叶结点的数量（getLeafs），根据结点中的值查找某个节点findNode

3.判断树是否为空（isEmpty），判断树是否是完全二叉树（isCompleteBTree），

4.遍历二叉树（traversing binary tree）

​ 4.1深度优先遍历（Depth First Search，DFS）：先序遍历（DLR），中序遍历（LDR），后续遍历（LRD）分 别为preOrder，inOrder，postOrder

​ 4.2广度优先遍历（Breadth First Traversal，BFS）：逐层访问每层的结点，BSF

public class LinkedListBinaryTree<T> { 
    // 封装结点 class Node<T> { 
    public T data; public Node left; public Node right; public Node(T data) { 
    this.data = data; this.left = null; this.right = null; } } private Node<T> root; private int size; public LinkedListBinaryTree() { 
    root = null; size = 0; } / * 创建根结点 * * @param value：根结点的值 */ public void creatRoot(T value) { 
    if (value == null) { 
    throw new RuntimeException("根节点不能为空！"); } Node<T> node = new Node<T>(value); root = node; size++; } public Node getRoot() { 
    if (root == null) { 
    throw new RuntimeException("根结点为空！"); } return root; } public boolean isEmpty() { 
    return root == null; } public int size() { 
    return size; } / * 在指定的节点处插入结点 * * @param node：插入结点的父结点 * @param value：待插入结点的值 * @param left：是否是左子节点 * @return：返回被插入后的结点 */ public Node add(Node<T> node, T value, boolean left) { 
    if (value == null) { 
    throw new RuntimeException("子结点为空!"); } if (node == null) { 
    throw new RuntimeException("父结点为空！"); } Node<T> n; if (left) { 
    if (node.left != null) { 
    throw new RuntimeException("左节点已存在！"); } n = new Node<T>(value); node.left = n; size++; } else { 
    if (node.right != null) { 
    throw new RuntimeException("右节点已存在！"); } n = new Node<T>(value); node.right = n; size++; } return n; } / * 获取树的深度 * * @param root：待获取深度树的根结点 * @return：返回树的深度 */ public int getHeight(Node root) { 
    if (root == null) { 
    return 0; } int leftHeight = 0; int rightHeight = 0; leftHeight = getHeight(root.left); rightHeight = getHeight(root.right); return leftHeight >= rightHeight ? ++leftHeight : ++rightHeight; } / * 先序遍历 * * @param root:要遍历树的根结点 */ public void preOrder(Node root) { 
    if (root == null) { 
    return; } System.out.print(root.data + ","); preOrder(root.left); preOrder(root.right); } / * 中序遍历:要遍历树的根结点 * * @param root */ public void inOrder(Node root) { 
    if (root == null) { 
    return; } inOrder(root.left); System.out.print(root.data + ","); inOrder(root.right); } / * 后序遍历 * * @param root：要遍历树的根结点 */ public void postOrder(Node root) { 
    if (root == null) { 
    return; } postOrder(root.left); postOrder(root.right); System.out.print(root.data + ","); } / * 广度遍历 */ public void BFS() { 
    Node root = this.root; Queue<Node> queue = new LinkedList<Node>(); LinkedList<Node> list = new LinkedList<Node>(); queue.offer(root); while (!queue.isEmpty()) { 
    Node node = queue.poll(); list.add(node); if (node.left != null) { 
    queue.offer(node.left); } if (node.right != null) { 
    queue.offer(node.right); } } Iterator it = list.iterator(); while (it.hasNext()) { 
    Node cur = (Node) it.next(); System.out.print(cur.data + ","); } } / * 获取叶子结点的个数 * * @param root：要获取叶子结点的根结点 * @return：叶子结点的个数 */ public int getLeafs(Node<T> root) { 
    if (root == null) { 
    return 0; } else if (root.left == null && root.right == null) { 
    System.out.print("叶节点：" + root.data + ","); return 1; } int leftLeafs = 0; int rightLeafs = 0; leftLeafs = getLeafs(root.left); rightLeafs = getLeafs(root.right); return leftLeafs + rightLeafs; } / * 获取root树第k层上结点数 * * @param root：待获取的数的根结点 * @param k：第k层元素 * @return：返回root第k层结点个数 */ public int getKNodeNum(Node root, int k) { 
    if (k == 1) { 
    if (root == null) { 
    return 0; } else { 
    return 1; } } int lNodeNum; int rNodeNum; lNodeNum = getKNodeNum(root.left, k - 1); rNodeNum = getKNodeNum(root.right, k - 1); return lNodeNum + rNodeNum; } / * 在根结点为root的树中查找值x的结点 * * @param root：树根的结点 * @param x：待查找结点的值 * @return：返回树中值为x的结点 */ public Node findNode(Node root, T x) { 
    if (root == null) { 
    return null; } else if (root.data == x) { 
    return root; } Node lNode = findNode(root.left, x); if (lNode != null) { 
    return lNode; } Node rNode = findNode(root.right, x); if (rNode != null) { 
    return rNode; } return null; } / * 判断是否是完全二叉树 * * @return */ public boolean isCompleteBTree() { 
    Node root = this.root; Queue<Node> queue = new LinkedList<Node>(); queue.offer(root); while (!queue.isEmpty()) { 
    Node pre = queue.poll(); if (pre == null) { 
    break; } queue.offer(pre.left); queue.offer(pre.right); } while (!queue.isEmpty()) { 
    Node cur = queue.poll(); if (cur != null) { 
    return false; } } return true; } // 测试用例 public static void main(String[] args) { 
    LinkedListBinaryTree<Integer> llbt = new LinkedListBinaryTree<Integer>(); llbt.creatRoot(2); llbt.add(llbt.getRoot(), 3, true); llbt.add(llbt.getRoot(), 5, false); llbt.add(llbt.findNode(llbt.getRoot(), 3), 7, true); llbt.add(llbt.findNode(llbt.getRoot(), 3), 8, false); llbt.add(llbt.findNode(llbt.getRoot(), 5), 10, true); llbt.add(llbt.findNode(llbt.getRoot(), 5), 12, false); System.out.println("树中的结点数量为：" + llbt.size()); System.out.println("root的深度为：" + llbt.getHeight(llbt.getRoot())); System.out.print("先序遍历："); llbt.preOrder(llbt.getRoot()); System.out.println(); System.out.print("中序遍历："); llbt.inOrder(llbt.getRoot()); System.out.println(); System.out.print("后序遍历："); llbt.postOrder(llbt.getRoot()); System.out.println(); System.out.print("广度遍历："); llbt.BFS(); System.out.println(); System.out.println("第2层的节点数量为：" + llbt.getKNodeNum(llbt.getRoot(), 2)); System.out.println("第3层的节点数量为：" + llbt.getKNodeNum(llbt.getRoot(), 3)); System.out.println("叶结点的数量为：" + llbt.getLeafs(llbt.getRoot())); System.out.println("是否为空：" + llbt.isEmpty()); System.out.println("是否是完全二叉树：" + llbt.isCompleteBTree()); System.out.println("2的父节点为：" + llbt.getParent(llbt.getRoot(), 2)); System.out.println("3的父节点为：" + llbt.getParent(llbt.getRoot(), 3).data); System.out.println("10的父节点为：" + llbt.getParent(llbt.getRoot(), 10).data); } } 

测试结果：

树中的结点数量为：7 root的深度为：3 先序遍历：2,3,7,8,5,10,12, 中序遍历：7,3,8,2,10,5,12, 后序遍历：7,8,3,10,12,5,2, 广度遍历：2,3,5,7,8,10,12, 第2层的节点数量为：2 第3层的节点数量为：4 叶节点：7,叶节点：8,叶节点：10,叶节点：12,叶结点的数量为：4 是否为空：false 是否是完全二叉树：true 2的父节点为：null 3的父节点为：2 10的父节点为：5 

线索二叉树

线索二叉树（Threaded Binary Tree）

线索化实质上是将二叉链表中的空指针改为指向前驱或者后继的线索，而前驱或后继的信息只能在遍历中才能得到，因此线索化的过程即在遍历的过程中修改空指针的过程。

适用于经常遍历或查找结点在遍历所得线性序列中的前驱和后继，则应该使用线索链表做存储结构。

二叉查找（搜索，排序）树

二叉查找树（Binary Search Tree，BST）又被称为二叉搜索树。设x为二叉查找树中的一个结点，x结点包含关键字key，结点x的key值记为key[x]。如果y是x的左子树中的一个结点，则key[y]<=key[x]；如果y是x的右子树的一个结点，则key[y]>=key[x]。

简单来说，任意选取一个结点，以该结点为根节点的左右子树中，若左子树不为空，则左子树中的结点值均小于该跟结点的值，若右子树不为空，右子树中的节点值均大于该根节点的值。

总的来说二叉查找树相对于二叉树有三个特征：

1.任取一个结点，其值大于左子树中任意结点的值，其值小于任意右子树中任意结点的值（有序）。

2.任意结点的左，右子树也分别为二叉查找树

3.二叉查找树中没有键值相等的结点。

二叉查找树的方法：

因为二叉查找树结点之间具有大小关系，因此在添加结点方法中可以根据待添加结点的值与根结点比较，如果小于根结点的值则向左移动，如果大于根结点的值则向右移动，继续以上步骤直到找到为null时，插入此节点。同样这种方法还可以用于查找方法。

删除二叉树中结点时，根据待删除结点的左右子节点是否为空分为以下四种情况：

1.左右子结点都为空（叶子结点）

2.左右子结点都不为空

待删除的结点左右子树都不为空，这时需要将32结点右子树中的最小值作为代替32结点的新根结点。

4.左子节点不为空，右子节点为空

与3情况互为镜像，操作类似。

public class BinarySearchTree { 
    // 封装结点 class Node { 
    public int data; public Node left; public Node right; public Node(int data) { 
    this.data = data; this.left = null; this.right = null; } // 使结点类可以根据待插入结点的值进行插入 public void add(Node node) { 
    if (node == null) { 
    throw new RuntimeException("无法插入空结点！"); } if (node.data < this.data) { 
    if (this.left == null) { 
    this.left = node; return; } else { 
    this.left.add(node); } } else if (node.data > this.data) { 
    if (this.right == null) { 
    this.right = node; return; } else { 
    this.right.add(node); } } } // 结点类实现根据值查找对应结点 public Node searchNode(int value) { 
    if (this.data == value) { 
    return this; } else if (value < this.data) { 
    if (this.left == null) { 
    return null; } else { 
    return this.left.searchNode(value); } } else { 
    if (this.right == null) { 
    return null; } else { 
    return this.right.searchNode(value); } } } // 结点类实现根据值查找对应结点的父节点 public Node searchParent(int value) { 
    if ((this.left != null && this.left.data == value) || (this.right != null && this.right.data == value)) { 
    return this; } if (value < this.data && this.left != null) { 
    return this.left.searchParent(value); } else if (value > this.data && this.right != null) { 
    return this.right.searchParent(value); } return null; } } public BinarySearchTree() { 
    } private Node root; public Node getRoot() { 
    return root; } / * 添加结点 * * @param node */ public void add(Node node) { 
    // 如果根节点为空则将node赋给root if (root == null) { 
    root = node; } else { 
    root.add(node); } } / * 前序遍历 * * @param node */ public void preOrder(Node node) { 
    if (node == null) { 
    return; } System.out.print(node.data + ","); this.preOrder(node.left); this.preOrder(node.right); } / * 查找值为vlaue的结点，不存在就返回null * * @param value：待查找结点的值 * @return：返回结点 */ public Node searchNode(int value) { 
    if (root == null) { 
    return null; } else { 
    return root.searchNode(value); } } / * 寻找结点值为value的父节点 * * @param value：待查找父节点的值 * @return：返回父节点，如不存在返回null */ public Node searchParent(int value) { 
    if (root == null) { 
    return null; } return root.searchParent(value); } / * 删除结点 * * @param value：待删除结点的值 * @return：删除成功返回删除的结点，删除失败返回null */ public Node deleteNode(int value) { 
    // 树为空 if (root == null) { 
    return null; } // 值为value的结点不在树中 Node target = searchNode(value); if (target == null) { 
    System.out.println("树中无此结点，无法删除！"); return null; } Node parent = searchParent(value); // 根据待删除的结点左右子节点是否分为以下四种情况 // 情况1.左右子节点都为空，即带删除的为叶节点 if (target.left == null && target.right == null) { 
    if (parent.left.data == value) { 
    parent.left = null; } else { 
    parent.right = null; } } else if (target.left != null && target.right != null) { 
    // 情况2.左右节点都不为空； int min = deleteMin(target.right); target.data = min; } else if (target.left != null && target.right == null) { 
    // 情况3.左子节点不为，右子节点为空 if (parent.left.data == value) { 
    parent.left = target.left; } else { 
    parent.right = target.left; } } else if (target.left == null && target.right != null) { 
    // 情况4.左子节点为空，右子节点不为空 if (parent.right.data == value) { 
    parent.right = target.right; } else { 
    parent.left = target.right; } } return target; } / * 删除树中的最小值 * * @param node：带删除最小值的树的根结点 * @return：返回删除结点的值 */ public int deleteMin(Node node) { 
    Node target = node; // 向左寻找，直到左子节点为空 while (target.left != null) { 
    target = target.left; } // 调用deleteNode方法删除值为最小值的结点 deleteNode(target.data); return target.data; } public static void main(String[] args) { 
    // arr[0]为根结点，根结点确定后add方法不改变根结点 int[] arr = new int[] { 
    10, 5, 3, 7, 1, 4, 6, 8, 15, 12, 18, 11, 13, 16, 20 }; BinarySearchTree bst = new BinarySearchTree(); for (int i : arr) { 
    bst.add(bst.new Node(i)); } System.out.print("原始二叉搜索树："); bst.preOrder(bst.getRoot()); System.out.println(); System.out.print("删除最小结点后为："); bst.deleteMin(bst.getRoot()); bst.preOrder(bst.getRoot()); System.out.println(); System.out.print("删除叶结点8后的树："); bst.deleteNode(8); bst.preOrder(bst.getRoot()); System.out.println(); System.out.print("删除有一个右节点左节点为空的结点3后的树："); bst.deleteNode(3); bst.preOrder(bst.getRoot()); System.out.println(); System.out.print("删除有一个左节点右节点为空的结点7后的树："); bst.deleteNode(7); bst.preOrder(bst.getRoot()); System.out.println(); System.out.print("删除有两个子节点的结点15后的树："); bst.deleteNode(15); bst.preOrder(bst.getRoot()); System.out.println(); System.out.println("值为11的结点：" + bst.searchNode(11).data); System.out.println("值为11的结点的父节点：" + bst.searchParent(11).data); } } 

测试结果：

原始二叉搜索树：10,5,3,1,4,7,6,8,15,12,11,13,18,16,20, 删除最小结点后为：10,5,3,4,7,6,8,15,12,11,13,18,16,20, 删除叶结点8后的树：10,5,3,4,7,6,15,12,11,13,18,16,20, 删除有一个右节点左节点为空的结点3后的树：10,5,4,7,6,15,12,11,13,18,16,20, 删除有一个左节点右节点为空的结点7后的树：10,5,4,6,15,12,11,13,18,16,20, 删除有两个子节点的结点15后的树：10,5,4,6,16,12,11,13,18,20, 值为11的结点：11 值为11的结点的父节点：12 

参考资料：

数据结构 严蔚敏 吴伟民

https://blog.csdn.net/xdzhouxin/article/details/

https://blog.csdn.net/_/article/details/

https://blog.csdn.net/skylibiao/article/details/

https://blog.csdn.net/rodman177/article/details/

https://www.cnblogs.com/hadilo/p/5724118.html

https://blog.csdn.net/gavin_john/article/details/