Tree树
概念
树（英语：tree）是一种抽象数据类型（ADT）或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>0）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。 特点
- 每个节点都只有有限个子节点或无子节点；
- 没有父节点的节点称为根节点；
- 每一个非根节点有且只有一个父节点；
- 除了根节点外，每个子节点可以分为多个不相交的子树；
- 树里面没有环路(cycle)
术语
节点的度：一个节点含有的子树的个数称为该节点的度； 树的度：一棵树中，最大的节点度称为树的度； 叶节点或终端节点：度为零的节点； 高度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,NoneJava实现
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);
}
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019.06.04 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录