二叉树的基本定义
2.树的深度——组成该树各结点的最大层次,如上图,其深度为3;
3.森林——指若干棵互不相交的树的集合,如上图,去掉根结点A,其原来的二棵子树T1、T2
、T3的集合{T1,T2,T3}就为森林;
4.有序树——指树中同层结点从左到右有次序排列,它们之间的次序不能互换,这样的树称为有序树,否则称为无序树。
树的表示
树的表示方法有许多,常用的方法是用括号:先将根结点放入一对圆括号中,然后把它的子树由左至右的顺序放入括号中,而对子树也采用同样的方法处理;同层子树与它的根结点用圆括号括起来,同层子树之间用逗号隔开,最后用闭括号括起来。如上图可写成如下形式:
(A(B(E(K,L),F),C(G),D(H(M),I,J)))
二叉树 基本形态
二叉树也是递归定义的,其结点有左右子树之分,逻辑上二叉树有五种基本形态:
(1)空二叉树——(a);
(2)只有一个根结点的二叉树——(b);
(3)只有左子树——(c);
(4)只有右子树——(d);
(5)完全二叉树——(e)
注意:尽管二叉树与树有许多相似之处,但二叉树不是树的特殊情形。
重要概念
(1)完全二叉树——若设二叉树的高度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层有叶子结点,并且叶子结点都是从左到右依次排布,这就是完全二叉树。
(2)——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树,。
(3)深度——二叉树的层数,就是高度。
性质
(1) 在二叉树中,第i层的结点总数不超过2^(i-1);
(2) 深度为h的二叉树最多有2^h-1个结点(h>=1),最少有h个结点;
(3) 对于任意一棵二叉树,如果其叶结点数为N0,而度数为2的结点总数为N2,则N0=N2+1;
(4) 具有n个结点的完全二叉树的深度为int(log2n)+1
(5)有N个结点的完全二叉树各结点如果用顺序方式存储,则结点之间有如下关系: 若I为结点编号则 如果I1,则其父结点的编号为I/2;
如果2*IN,则无左儿子; 如果2*I+1N,则无右儿子。
(6)给定N个节点,能构成h(N)种不同的二叉树。
h(N)为卡特兰数的第N项。h(n)=C(n,2*n)/(n+1)。
(7)设有i个枝点,I为所有枝点的道路长度总和,J为叶的道路长度总和J=I+2i 普通树转换成二叉树
二叉树很像一株倒悬着的树,从树根到大分枝、小分枝、直到叶子把数据联系起来,这种数据结构就叫做树结构,简称树。树中每个分叉点称为结点,起始结点称为树根,任意两个结点间的连接关系称为树枝,结点下面不再有分枝称为树叶。结点的前趋结点称为该结点的"双亲",结点的后趋结点称为该结点的"子女"或"孩子",同一结点的"子女"之间互称"兄弟"。
普通树转二叉树,一般采用左“子女”右“兄弟”的方式来转化。
转化规则:
普通树为有序树T,将其转化成二叉树T’如下:
⑴T中的结点与T’中的结点一一对应,即T中每个结点的序号和值在T’中保持不变; ⑵T中某结点v的第一个儿子结点为v1,则在T’中v1为对应结点v的左儿子结点; ⑶T中结点v的儿子序列,在T’中被依次链接成一条开始于v1的右链;
由上述转化规则可以看出,一棵有序树转化成二叉树的根结点是没有右子树的,并且除保留每个结点的最左分支外,其余分支应去掉,然后从最左的儿子开始沿右儿子方向依次链接该结点的全部儿子。
还有一种比较有趣的方法
1)在树的所有兄弟结点上添加一条水平线
2)删去所有除左子树之外的所有父到子之间的树枝或者说成删去父结点到除最左陔子之外的所有其它孩子之间的树枝。
3)将添加的水平线顺时间转动45度。
/ | \
0 0 0
增加上水平线
/ | \
0- 0- 0
删除父到子除最左之外的所有树枝
/
0 - 0 - 0
再将他连线转动45度成为最终的二叉树为
/
\
\
转动后将是这个样子
在我自己理解起来最简单的就是
在任一个结点上除了左子树外,左子树的右边的兄弟将全部连接成为左子树的右子树举例如
二叉树
A
/ | \
B C D
应上面我说的除左子树外,左子树的右兄弟都连接成他的子。成为A为根,B是他的左子不变,C成为B的右子树D又连成C的右子树,结果为
A
/
B
\
C
\
D
完全二叉树
对满二叉树,从第一层的结点(即根)开始,由下而上,由左及右,按顺序结点编号,便得到满二叉树的一个顺序表示。据此编号,完全二叉树定义如下:一棵具有n个结点,深度为K的二叉树,当且仅当所有结点对应于深度为K的满二叉树中编号由1至n的那些结点时,该二叉树便是完全二叉树。
编辑本段二叉树遍历
遍历是对树的一种最基本的运算,所谓遍历二叉树,就是按一定的规则和顺序走遍二叉树的所有结点,使每一个结点都被访问一次,而且只被访问一次。由于二叉树是非线性结构,因此,树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。
设L、D、R分别表示遍历左子树、访问根结点和遍历右子树, 则对一棵二叉树的遍历有三种情况:DLR(称为先根次序遍历),LDR(称为中根次序遍历),LRD (称为后根次序遍历)。
(1)先序遍历:首先访问根,再先序遍历左(右)子树,最后先序遍历右(左)子树
(2)中序遍历:首先中序遍历左(右)子树,再访问根,最后中序遍历右(左)子树
(3)后序遍历:首先后序遍历左(右)子树,再后序遍历右(左)子树,最后访问根
(4)层次遍历:即按照层次访问,通常用队列来做。访问根,访问子女,再访问子女的子女(越往后的层次越低)(两个子女的级别相同)
特殊的二叉树
1. 完全二叉树:若设二叉树的高度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层从右向左连续缺若干结点,这就是完全二叉树。
2. 满二叉树:一个高度为h的二叉树包含正是2^h-1元素称为满二叉树。
线索二叉树
线索二叉树(保留遍历时结点在任一序列的前驱和后继的信息):若结点有左子树,则其lchild域指示其左孩子,否则令lchild域指示其前驱;若结点有右子树,则其rchild域指示其右孩子,否则令rchild指示其后继。还需在结点结构中增加两个标志域LTag和RTag。LTag=0时,lchild域指示结点的左孩子,LTag=1时,lchild域指示结点的前驱;RTag=0时,rchild域指示结点的右孩子,RTag=1时,rchild域指示结点的后继。以这种结点结构构成的二叉线索链表,链表作为二叉树的存储结构,叫做其中指向结点前驱和后继的指针叫做线索,加上线索的二叉树称为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。若对二叉树进行中序遍历,则所得的线索二叉树称为中序线索二叉树,线索链表称为为中序线索链表。线索二叉树是一种物理结构。
线索二叉树的存储结构
在中序线索树找结点后继的规律是:若其右标志为1,则右链为线索,指示其后继,否则遍历其右子树时访问的第一个结点(右子树最左下的结点)为其后继;找结点前驱的规律是:若其左标志为1,则左链为线索,指示其前驱,否则遍历左子树时最后访问的一个结点(左子树中最右下的结点)为其前驱。
在后序线索树中找到结点的后继分三种情况:
若结点是二叉树的根,则其后继为空;若结点是其双亲的右孩子,或是其双亲的左孩子且其双亲没有右子树,则其后继即为双亲结点;若结点是其双亲的左孩子,且其双亲有右子树,则其后继为双亲右子树上按后序遍历列出的第一个结点。