树(英语:tree)是一种抽象数据类型(ADT)或是实现这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。它是由n(n>0)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。 特点
节点的度:一个节点含有的子树的个数称为该节点的度; 树的度:一棵树中,最大的节点度称为树的度; 叶节点或终端节点:度为零的节点; 高度Height 节点到叶子节点的最长路径,树的高度等于根节点的高度。 深度Depth 根节点到这个节点的所尽力的边的个数 层Level:节点的深度+1 父亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点; 叶子结点(Leaves):是树的末端结点,他们没有子结点,就像真实的树那样 ,由根开始,伸展枝干,到叶为止。
image.png
家族关系
图片.png
公司组织结构
图片.png
html结构
图片.png
效率
图片.png
这个索引可以把原本O(n)的查找操作变为O(logn),可以简单地理解为在数据结构的层面上构造了一个二分查找算法。
python实现
class TreeNode:
def __init__(self,val):
self.val = val
self.left,self.right = None,None
Java实现
public class TreeNode {
public int val;
public TreeNode left,right;
public TreeNode(int val){
this.left = null;
this.right = null;
this.val = val;
}
}
层序遍历 通过队列实现
// 层序遍历
public void levelOrder(){
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()){
Node curNode = queue.remove();
System.out.println(curNode.data);
if (curNode.left!=null){
queue.add(curNode.left);
}
if (curNode.right!=null){
queue.add(curNode.right);
}
}
}