数据结构:二叉树的定义和性质以及特殊二叉树

一、二叉树(Binary Tree)是n(n>=0)个结点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。如图1就是一棵二叉树

图1

二叉树的特点:

(1)每个结点最多有两棵子树,所以二叉树中不存在度大于2的结点。

(2)左子树和右子树是由顺序的,次序不能颠倒。

(3)即使树中某结点只有一棵子树,也要区分它是左子树还是右子树。

二叉树具有五种基本形态:

(1)空二叉树;(2)只有一个根结点;(3)根结点只有左子树;(4)根结点只有右子树;(5)根结点既有左子树又有右子树。

二、特殊二叉树

1、斜树:所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。

2、满二叉树:在一棵二叉树中,如果所有分支结点都存在左子树和右子树,并且所有叶子都在同一层上,这样的二叉树就称为满二叉树,如图2。

图2

满二叉树的特点有:

(1)叶子只能出现在最下一层。出现在其他层就不可能达到平衡。

(2)非叶子结点的度一定是2。

(3)在同样深度的二叉树中,满二叉树的结点个数最多,叶子树最多。

3、完全二叉树:

对一棵具有n个结点的二叉树按层序编号,如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同,则这棵二叉树称为完全二叉树,如图3。

图3

完全二叉树的特点:

(1)叶子结点只能出现在最下两层。

(2)最下层的叶子一定集中在左部连续位置

(3)倒数二层,若有叶子结点,一定都在右部连续位置。

(4)如果结点度为1,则该结点只有左孩子,即不存在只有右子树的情况。

(5)同样结点数的二叉树,完全二叉树的深度最小。

注意:满二叉树一定是棵完全二叉树,但完全二叉树不一定是满的。

三、二叉树的性质

1、在二叉树的第i层上至多有2^(i-1)个结点(i>=1)。

2、深度为K的二叉树至多有2^k - 1个结点(k>=1)。

3、对任何一棵二叉树T,如果其终端结点数为n0, 度为2的结点数为n2,则n0 = n2 + 1。

Proof: Let n = the total number of nodes

B = number of branches n0, n1, n2 represent the number of nodes with no children, a single child, and two children respectively. B = n - 1 (since all nodes except the root node come from a single branch)

B = n1 + 2*n2 n = n1+ 2*n2 + 1 n = n0 + n1 + n2 n1+ 2*n2 + 1 = n0 + n1 + n2 ==> n0 = n2 + 1

四、Encoding general trees as binary trees

Each node N in the ordered tree corresponds to a node N' in the binary tree;the left child of N' is the node corresponding to the first child of N, and 

the right child of N' is the node corresponding to N 's next sibling --- that is, the next node in order among the children of the parent of N.

参考:《大话数据结构》、《Data Structures》

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

二叉树性质

•【性质1】在二叉树的第i层上最多有2i-1个结点(i>=1)。 【性质2】深度为k的二叉树至多有2k –1个结点(k>=1)。 •【特别】一棵深度为k且有2k...

2416
来自专栏Android机动车

数据结构——树、森林和二叉树的转换

森林是由若干棵树组成的,所以可以完全理解为,森林中的每一棵树都是兄弟,可以按照兄弟的处理办法来操作。步骤不如:

652
来自专栏小文博客

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

873
来自专栏猿人谷

根据前序和中序推出后序

最近面试总遇到这种根据给出的两类序遍历,然后求按另一种形式序的遍历。看来有必要好好总结下这个知识点,省的每次笔试时都得花不少时间推导。 首先,我们看看前序、中序...

1726
来自专栏大闲人柴毛毛

剑指 offer代码解析——面试题39判断平衡二叉树

题目:输入一颗二叉树的根结点,判断该树是不是平衡二叉树。 如果某二叉树中任意结点的左右子树的高度相差不超过1,那么它就是一棵平衡二叉树。 分析:所谓平衡二...

2875
来自专栏猿人谷

判断二叉树是不是平衡

平衡二叉树(Balanced Binary Tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超...

1846
来自专栏用户画像

4.5.2 平衡二叉树

为了避免树的高度增长过快,降低二叉排序树的性能,我们规定在插入和删除二叉树结点时,要保证任意结点的左、右子树高度差的绝对值不超过1,将这样的二叉树称为平衡二叉树...

742
来自专栏向治洪

数据结构之二叉树

树 定义:满足以下条件的就是树: 1. 有且仅有一个特定的称为根Root的结点。 2. 当n>1时,其余结点可分为m(m>0)个互不相交的有限集,其...

18410
来自专栏Micro_awake web

python二叉树递归算法之后序遍历,前序遍历,中序遍历

1 #!/usr/bin/env python 2 # -*- coding: utf-8 -*- 3 # @Date : 2016-11-18 0...

1975
来自专栏Android机动车

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

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

982

扫码关注云+社区