|
|
|
|
|
二叉树是n个节点的有限集合，它或者是空树，或者是由一个根节点及两棵不相交的、分别称为左子树和右子树的树所组成。
|
|
|
|
|
|
二叉树的节点的子树要区分左子树和右子树，即使在节点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树；另外，二叉树的节点的最大度为2，而树中不限制节点的度数。
|
|
|
|
|
|
.在二叉树的第i层至多有2i-1个节点（根节点为1层）。
|
|
|
|
|
|
.对任何一棵二叉树T，如果其终端节点数为n0，度为2的节点数为n2，则n0=n2+1。
|
|
|
|
.具有n个节点的完全二叉树的深度为［log2n」+1。
|
|
|
|
|
|
|
|
.完全二叉树：除了最外层，其余层上的节点数目都达到最大值，而第h层上的节点集中存放在左子树中。
|
|
|
|
.平衡二叉树（AVL树）：二叉排序树的一种，其检索效率介于最优二叉树（Huffman树）和一般二叉排序树之间，要求任何一个节点的左右子树的高度差都不大于1。
|
|
|
|
.二叉查找树：又称二叉排序树，左子树的值都小于根节点的值，而右子树的值都大于根节点的值，同时左、右子树都是查找树。
|
|
|
|
|
|
二叉树的遍历是非常重要的操作，有前序、中序、后序和层序遍历，要求熟练掌握。
|
|
|
|
|
|
二叉树因具有递归性质，因此能很方便地用递归实现遍历，借助栈同样可以用非递归方式实现遍历。注意体会栈的使用，在此采用不带头节点的单链表作为栈的存储结构，Stop是栈顶指针，注意出栈／入栈操作。
|
|
|
|
|
|
|
