树是一种抽象数据类型,或是实现这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。如下图所示:
树形结构的价值:
由于大部分对树的操作的时间复杂度可以被干到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) 个结点的有限集合:
// 首先实现单个结点的数据结构
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的层次顺序,对二叉树中的各个结点进行访问。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。