二叉树的计算.pdf

⼆⼆叉叉树树的的计计算算

⼆叉树是⼀种典型的⾮线性结构，如果在⼀个数据结构中，每个节点只能有⼀个⽗节点是可以有多个⼦节点，这样的数据结构我们就把它

称为树，如果我们再加⼀个规定，每个⽗节点最多只有2个⼦节点的话，那么这样的树我们就把它称为⼆叉树。既然刚才说了⼆叉树⼀个节

点下最多只有2个⼦节点，那就意味着对于⼆叉树中的任意⼀个节点有三种情况，对于这三种情况，我们分别把这个⽗节点称为度为2的节

点、度为1的节点、度为0的节点，也就是说⼀个⽗节点它下⾯有⼏个⼦节点那么它的度就是⼏，对于度为0的⼦节点来说由于它没有⼦节点

了也把它称为叶⼦节点。所以学了⼆叉树就要知道⼆叉树并不是表⽰每个节点下⾯必须开两个叉⽽是最多开两个叉

现在学⼀个新的概念就是⼆叉树的层数，我们看下⾯的⼆叉树，最上⾯的节点称为根节点，⼀个⼆叉树只能有⼀个根节点，如果把根节点叫

第⼀层的话，下⾯依次是第⼆层第三层，我们发现⼆叉树越往下它所能容纳的节点数就越多，发现每⼀层所能容纳最多的节点数是上⼀层的

⼆倍，所以这样⼀来如果想要计算第n层最多容纳多少个节点，把刚才的规律总结出来就是2^(n-1)个——读2的n-1次幂。现在来算⼀算假设

就有⼀个层数为6的⼆叉树它⼀共有多少个节点，像这样每⼀层都达到了最⼤容量的⼆叉树我们称为满⼆叉树。

了解⼆叉树中节点数和层数的关系之后，再来介绍⼀个⼆叉树中⼀个⾮常重要的数学关系，就是对于任何⼀个⼆叉树来说，它的叶⼦节点数

永远⽐度为2的节点数多1，

⼆⼆叉叉树树的的遍遍历历

所谓遍历就是将数据结构中的数据全部访问⼀遍的过程，既要做到⼀个都不能少⼜要做到都不能重复，在之前学习的线性表中，遍历⾮常的

简单，我们只需要从头到尾⼀个挨着⼀个访问就可以了，虽然简单是完全可以满⾜遍历的要求，是对于⼆叉树来说，它的结构⽐线性表

复杂多了，如果想在遍历的过程中⼀个都不少⼜⼀个都不重复，就必须要有⼀套系统的遍历⽅法才⾏。

⼀般来说在⼆叉树中有三种⽅式遍历，分别是先序遍历、中序遍历和后序遍历。

这三种遍历规则看到规则知道怎么遍历，是给先序、中序、后序记不住哪个是怎么遍历的，实际上刚才这三种遍历规则是⾮常有讲究的，

⾸先这三种遍历⽅式都⼀定是先左后右，没有先遍历右边后遍历左边这种说法，左永远都在右的前⾯，不同的是中的位置，先序中就在前

⾯，中序中就在中间，后序中就在后⾯，其实这三种遍历⽅式是以中的位置来命名的