首页 > 代码库 > 第08章 二叉树
第08章 二叉树
二叉树
1.为什么要使用二叉树?
二叉树结合了有序数组快速查找和线性链表快速插入删除的优势。
树是一种既能像有序数组一样实现快速查询,又能像链表一样实现快速地插入和删除的数据结构.
2.有关树的几个术语
路径:从一个节点走到另一个节点,过程中数据的排列叫做路径.
根:一个树只有一个根,只有子节点,没有父节点.
父节点:每个节点都向上连接的节点叫做父节点,根没有父节点,一个子节点只有一个父节点.
子节点:每个节点都向下连接的一个或者多个节点叫做子节点.
子树:每个节点都可以作为子树的根,子节点的节点都包含在子树中.
访问:当数据流向到某个节点时,就成为访问了该节点.
遍历:遵循某种特定的顺序来访问树所有节点的过程叫做遍历.
层:节点层数是指从根开始到某个节点的代数,根为第0代.
关键字:对象的数据域中用来作为查询字段的叫做关键字.
二叉树:每个节点最多有2个子节点的树成为二叉树.
3.树的效率
树的时间复杂度为O(log N),更精确地说是O(log 2 N).(此处表示以2为底N的对数)
4.遍历树
三种遍历方式:
遍历树最简单的方法是递归。
前序遍历(preorder):
1.调用自身遍历节点的左子树
2.调用自身遍历节点的右子树
3.访问这个节点
中序遍历 (inorder) :
中序遍历会访问所有的节点按照关键字升序排列。
1.调用自身遍历节点的左子树
2.访问这个节点
3.调用自身遍历节点的右子树
后序遍历(postorder):
1.调用自身遍历节点的左子树
2.调用自身遍历节点的右子树
3.访问这个节点
5.删除树
1.无节点
2.一个节点
3.两个节点
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。