文档章节

二叉树总结

 笨拙的小Q
发布于 2016/04/19 13:06
字数 642
阅读 31
收藏 0

1、二叉树是一棵树,其中每个节点都不能有多于2个儿子。

二叉树的一个性质是:一棵普通二叉树的深度要比它的节点个数N小得多。即普通二叉树的平均深度为O(N^0.5)。

二叉查找树的平均深度为O(logN);最坏情况下,一棵有N各节点的普通二叉树的深度可以大到N-1。

注意:当涉及到树时,我们不明显画出null链,因为具有n个节点的每颗二叉树都将需要n+1个null链。

树的相关概念:

路径:从节点n1到nk的路径定义为节点n1,n2,n3,........nk的一个序列,使得对于1<=i<k,节点ni是ni+1的父亲。这条路径的长度是该路径上边的条数,即k-1。从每个节点到它自己有一条长度为0的路径。注意,在一棵树中从根到每个节点恰好存在一条路径。

深度:对于任意节点ni,ni的深度为从根到ni的唯一的路径的长度。因此,根的深度为0.ni的高度是从ni到叶节点的最长路径的长度。因此所有叶节点的高度都为0;一棵树的深度等于它的最深的叶节点的深度;该深度总是等于这棵树的高度。

各种特殊的树:

1、平衡二叉树

     平衡二叉树,是一种二叉查找树(二叉排序树),其中每个节点的左子树和右子树的高度差不大于1。

下面是判断一棵树是否为平衡二叉树的代码:

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root==null){
            return true;
        }
        int left = depth(root.left);
        int right = depth(root.right);
        int diff = left-right;
        if(diff>1||diff<-1) return false;
        return IsBalanced_Solution(root.left)&&IsBalanced_Solution(root.right);
    }
    public int depth(TreeNode pRoot)//求二叉树的高度(深度)
    {
     if(pRoot==null){
            return 0;
        }
        int nLeft = depth(pRoot.left);
        int nRight = depth(pRoot.right);
        return (nLeft>nRight)?(nLeft+1):(nRight+1);
    }
}

2、二叉排序树(二叉查找树、二叉搜索树)

二叉查找树,或者是一棵空树,或者具有下面的性质:

1、若它的左子树不为空,则左子树上所有节点的值均小于它的根节点的值

2、若它的右子树不为空,则其右子树上所有节点的值均大于它的根节点的值。

3、它的左右子树也分别是二叉查找树。

检查是否为BST的代码如下:

http://my.oschina.net/u/2444659/blog/662711

待续。。。。。

© 著作权归作者所有

粉丝 2
博文 58
码字总数 27842
作品 0
南京
私信 提问

暂无文章

《Designing.Data-Intensive.Applications》笔记 四

第九章 一致性与共识 分布式系统最重要的的抽象之一是共识(consensus):让所有的节点对某件事达成一致。 最终一致性(eventual consistency)只提供较弱的保证,需要探索更高的一致性保证(stro...

丰田破产标志
今天
4
0
docker 使用mysql

1, 进入容器 比如 myslq1 里面进行操作 docker exec -it mysql1 /bin/bash 2. 退出 容器 交互: exit 3. mysql 启动在容器里面,并且 可以本地连接mysql docker run --name mysql1 --env MY...

之渊
今天
6
0
python数据结构

1、字符串及其方法(案例来自Python-100-Days) def main(): str1 = 'hello, world!' # 通过len函数计算字符串的长度 print(len(str1)) # 13 # 获得字符串首字母大写的...

huijue
今天
4
0
OSChina 周日乱弹 —— 我,小小编辑,食人族酋长

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @宇辰OSC :分享娃娃的单曲《飘洋过海来看你》: #今日歌曲推荐# 《飘洋过海来看你》- 娃娃 手机党少年们想听歌,请使劲儿戳(这里) @宇辰OSC...

小小编辑
今天
999
11
MongoDB系列-- SpringBoot 中对 MongoDB 的 基本操作

SpringBoot 中对 MongoDB 的 基本操作 Database 库的创建 首先 在MongoDB 操作客户端 Robo 3T 中 创建数据库: 增加用户User: 创建 Collections 集合(类似mysql 中的 表): 后面我们大部分都...

TcWong
今天
40
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部