数据结构二叉树知识点总结

术语 

1. 节点的度:一个节点含有的子树的个数称为该节点的度;

2. 叶节点或终端节点:度为零的节点; 

3. 非终端节点或分支节点:度不为零的节点; 

4. 父亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点; 

5. 兄弟节点:具有相同父节点的节点互称为兄弟节点; 

6. 节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推; 

7. 树的高度或深度:树中节点的最大层次; 

8. 堂兄弟节点:父节点在同一层的节点互为堂兄弟; 

9. 节点的祖先:从根到该节点所经分支上的所有节点; 

10. 孙:以某节点为根的子树中任一节点都称为该节点的子孙。 

11. 森林:由m(m>=0)棵互不相交的树的集合称为森林; 

12. 满二叉树:一棵深度为k,且有2^k-1 (2的k次方减一)个节点称之为满二叉树 

13. 完全二叉树:完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。叶节点只能出现在最下层和次下层,并且最下面一层的结点都集中在该层最左边的若干位置的二叉树

二叉树的性质

1.在非空二叉树中,第i层的结点总数不超过2^(i-1),i>=1; 

2.深度为h的二叉树最多有2^h-1个结点(h>=1),最少有h个结点; 

3.对于任意一棵二叉树,如果其叶结点数为N0,而度数为2的结点总数为N2,则N0=N2+1; 

4.具有n个结点的完全二叉树的深度为K =[log2n」+1(取下整数)

5.有N个结点的完全二叉树各结点如果用顺序方式存储,则结点之间有如下关系: 若I为结点编号则 如果I>1,则其父结点的编号为I/2;

6.完全二叉树,如果2*I<=N,则其左儿子(即左子树的根结点)的编号为2*I;若2*I>N,则无左儿子; 如果2*I+1<=N,则其右儿子的结点编号为2*I+1;若2*I+1>N,则无右儿子。

7.给定N个节点,能构成h(N)种不同的二叉树。h(N)为卡特兰数的第N项。h(n)=C(2*n,n)/(n+1)。 

8.设有i个枝点,I为所有枝点的道路长度总和,J为叶的道路长度总和J=I+2i

二叉树的遍历三种方式,如下: 

(1)前序遍历(DLR),首先访问根结点,然后遍历左子树,最后遍历右子树。简记根-左-右。 

(2)中序遍历(LDR),首先遍历左子树,然后访问根结点,最后遍历右子树。简记左-根-右。 

(3)后序遍历(LRD),首先遍历左子树,然后遍历右子树,最后访问根结点。简记左-右-根。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏kevindroid

leetcode110 Balanced Binary Tree

15750
来自专栏海天一树

二叉树的建立和遍历

二叉树:每个结点的子结点个数不大于2的树,叫做二叉树。 根结点:最顶部的那个结点叫做根结点,根结点是所有子结点的共同祖先。比如上图中的“7”结点就是根结点。 子...

10230
来自专栏小文博客

小文’s blog — 平衡二叉树构造方法

11130
来自专栏weixuqin 的专栏

数据结构学习笔记(树、二叉树)

27030
来自专栏软件开发 -- 分享 互助 成长

二叉排序树和平衡二叉树

二叉排序树又称二叉查找树或二叉搜索树。 它一棵空树或者是具有下列性质: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空,...

217100
来自专栏郭耀华‘s Blog

数据结构二叉树知识点总结

10520
来自专栏开发与安全

数据结构:树的定义和基本概念

一、树(Tree)是n(n>=0)个结点的有限集。n=0时称为空树。在任意一棵非空树中:(1)有且仅有一个特定的称为根(root)的结点。 (2)当n>1时,其...

20780
来自专栏曾大稳的博客

树(Tree)以及二叉树的遍历

树(tree) 是一种抽象数据类型(ADT)或是实作这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。它是由n(n>0)个有限节点组成一个具有层次...

85610
来自专栏Android机动车

数据结构——二叉树的定义和性质

在一些电视节目中,会猜测商品价格,有的人是一点一点的数字累加,这样的策略效率太低了。其实有一种经典的折半查找算法,就类似于我们今天要说的二叉树。

13720
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题19二叉树的镜像

   分析:所谓“镜像”就是从镜子里看到的样子。我们可以画一棵二叉树,然后画出该二叉树的镜像。画完图之后我们会发现,所谓“二叉树的镜像”就是把二叉树中所有子树...

29250

扫码关注云+社区

领取腾讯云代金券