BinTree(二叉树)

发表于 | 分类于

阐述一下二叉树的理解

1.二叉树的一些性质

这里写图片描述

二叉树性质

  1. 在二叉树的第i层上至多有2i-1个结点（i≥1）
  2. 深度为k的二叉树至多有2k-1个结点（k≥1）
  3. 对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1
  4. 左子树的所有节点小于父节点
  5. 有字数的所有节点大于父节点

    满二叉树

这里写图片描述

  1. 一棵深度为k且有2k-1个结点的二叉树称为满二叉树。

    完全二叉树

    这里写图片描述

可以对满二叉树的结点进行连续编号，约定编号从根结点起，自上而下，自左至右，则由此可引出完全二叉树的定义。深度为k且有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称之为完全二叉树。

一般二叉树

这里写图片描述

除了满二叉树之外 都是一般二叉树

2.二叉树的遍历

  1. 先序遍历、后序遍历、中序遍历就不赘述了网上一搜一大片。
  2. 阐述一下怎么按照深度从左到右遍历。

以图a为例子 我们需要借助队列的数据结构。

  1. 首先获取根节点，获取他的做孩子 2 与右孩子 3，并放入队列quene中
  2. 从队列中去一个元素 即 2 把该元素的左右孩子即 4、5放入队列
  3. 递归 2

得到的数据输出就是按照深度从左到右遍历的数据输出。

3.搜索二叉树（查找二叉树的）的搜索方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
T key = a search key 
Node root = point to the root of a BST 
while(true){
if(root==null){ 
    break; 
    
} 
if(root.value.equals(key)){
return root; 
    
} else if(key.compareTo(root.value)<0){
root = root.left; 
    
} else{ 
root = root.right;
}
} 
return null;

从程序中可以看出，当BST查找的时候，先与当前节点进行比较：

1.如果相等的话就返回当前节点；

2.如果少于当前节点则继续查找当前节点的左节点；

3.如果大于当前节点则继续查找当前节点的右节点。

到此为止。