UtopiaXC Blog - 复习
type: channel
link: https://blog.utopiaxc.com/tag/%E5%A4%8D%E4%B9%A0/
items: 树结构复习（未完待续）

树结构复习（未完待续）
type: item
date: 2021-03-25T15:23:00+08:00
description: 一、树的基本定义图1.1 一颗树（图片来源：Wikipedia） 1、树基本概念树：一种用来模拟拥有树状结构的数据结构模型，形似一颗倒置的树，是一种特殊的稀疏图树的结点：每一个用于保存数据的元素，如图1.1中的A、B、C等度：节点的度：节点拥有的子元素的个数，例如图1.1中的B节点，度为3。树的度：节点度最大的节点的度，如图1.1树的度为3根节点：位于最顶端的节点，如图1.1中的A叶子节点：度为0的节点，也成为末端节点，如图1.1中的K、J、L、O、P均为叶子节点孩子节点：一个节点的子元素节点（节点子树的根节点），如图1.1中的B，孩子节点为D、E、F双亲结点（父节点）：一个节点具有子元素节点，那么对于其所有子元素节点来说该节点为双亲结点（父节点），如图1.1中的D、E、F，他们的双亲节点为B兄弟节点：具有相同双亲节点的节点称之为兄弟节点，如图1.1中的D、E、F，他们互为兄弟节点祖先：由根节点到该节点之间的所有父节点，如图1.1，I节点的祖先节点为A、B、D子孙：该节点子树的全部节点，如图1.1中B节点的子孙为D、E、F、I、J、K2、深度与高度深度指任意节点到根节点的唯一路径的距离，根节点深度为0。如图1.1，D节点深度为2。高度指任意节点到叶子节点最长路径的距离，叶子节点高度为0。如图1.1 D节点的高度为对于树来说，树的高度为根节点的高度，深度为叶子节点的深度的最大值，因此高度等于深度。如图1.1，深度与高度均为5高度与深度的计算可使用递归，详见二叉树的高度与深度计算。3、树的表示方法双亲表示法：在树结构中，除根节点外所有节点均只有一个双亲节点，因此可以使用其双亲节点来表示该树。存储方式数组下标dataparent0A-11B02C03D14E15F16G27H28I39J410K811L612M613N714O1215P13代码实现（Java）import java.util.Vector; //树的节点 class TreeNode<T> { private T data; private int parent; public TreeNode(T data, int parent) { this.data = data; this.parent = parent; } } //树类 public class Tree<T> { private int countNodes; private Vector<TreeNode<T>> nodes; public Tree(int countNodes,Vector<TreeNode<T>> nodes){ this.countNodes=countNodes; this.nodes=nodes; } }孩子表示法：将树中的每个节点与其子节点用链表形式连接起来，并将所有链表置入线性表中。存储方式代码实现（Java）孩子双亲表示法：同时采用孩子表示法和双亲表示法存储方式代码实现（Java）孩子兄弟表示法二、二叉树1、二叉树的基本概念二叉树子树斜树满二叉树2、二叉树的实现3、二叉树的遍历前序遍历中序遍历后序遍历层序遍历4、反转二叉树三、树的遍历1、深度优先搜索DFS2、广度优先搜索BFS四、特殊的树1、红黑树2、字典树3、二叉排序树（二叉搜索树）4、哈夫曼树5、线索二叉树6、平衡二叉树7、堆8、B树9、B+树 本篇内容为原创内容，采用CC BY-NC-SA 4.0协议许可 2021-03-25 15:23 UtopiaXC 于大连