首页 > 代码库 > 数据结构和算法——二叉树

数据结构和算法——二叉树


1.树的优点

有序数组: 查找很快,二分法实现的查找所需要的时间为O(logN),遍历也很快,但是在有序数组中插入,删除却需要先 找到位置,
       在把数组部分元素后移,效率并不高。


链表: 链表的插入和删除都是很快速的,仅仅需要改变下引用值就行了,时间仅为O(1),但是在链表中查找数据却需要遍历所有的元素,
       这个效率有些慢了。

树的优点: 树结合了有序数组和链表的优点,可以实现快速的查找,也可以快速的删除,查找。


树的一些专用术语:
路径:
  顺着连接节点的边从一个节点到另一个节点的,所经过的所有节点的顺序排列就是路径。
根:
  根即是树的顶端,一个树有且只有一个根,从根到所有节点的路径有且只有一条。
父节点:
  每一个节点的连接的上一个节点即是该节点的父节点。
子节点;
  每一个节点的向下连接的节点即是改节点的子节点
子树:
  每个节点都可以认为是一个树的根,
叶节点:
  就是没有子节点的节点
层:
  一个节点的层数,从根节点到该节点有多少代,就是多少层

二叉树:
  树种的节点可以有多个节点,二叉树是最多只能有2个节点的树。二叉树的两个节点被称为左子节点和右子节点。
 二叉树的节点是最多有2个子节点,但并不是必须有2个子节点。

平衡树和非平衡树:
如果一个树中存在一个或多个的子树,只有右子节点,或左子节点,那么这个树就是非平衡树。

2.二叉搜索树:
根节点的左右2个节点,小于根节点在放在左侧,大于根节点的放在右侧。
<1>插入
<2>查找
<3>遍历
1.中序遍历
(1)调用自身遍历节点的左子树
(2)访问这个节点
(3)调用自身遍历节点的右子树
2.前序遍历
(1)访问这个节点
(2)调用自身遍历节点的左子树
(3)调用自身遍历节点的右子树
3.后序遍历
(1)调用自身遍历节点的左子树
(2)调用自身遍历节点的右子树
(3)访问这个节点
<4>删除
     (1)删除叶节点(没有子节点的)
     (2)删除节点(一个子节点的)
     (3)删除节点(二个子节点的)
<5>查找最大最小值

数据结构和算法——二叉树