二叉树的概念
二叉树(Binary Tree)是n(n>&＃61;0)个结点的有限集合&＃xff0c;该集合或者为空集(空二叉树)&＃xff0c;或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。
二叉树的特点
每个结点最多有两棵子树&＃xff0c;所以二叉树中不存在度大于2的结点。二叉树中每一个节点都是一个对象&＃xff0c;每一个数据节点都有三个指针&＃xff0c;分别是指向父母、左孩子和右孩子的指针。每一个节点都是通过指针相互连接的。相连指针的关系都是父子关系。
二叉树节点的定义
二叉树节点定义如下&＃xff1a;
struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};
二叉树的五种基本形态
空二叉树
只有一个根结点
根结点只有左子树
根结点只有右子树
根结点既有左子树又有右子树
拥有三个结点的普通树只有两种情况&＃xff1a;两层或者三层。但由于二叉树要区分左右&＃xff0c;所以就会演变成如下的五种形态&＃xff1a;
特殊二叉树
斜树
如上面倒数第一副图的第2、3小图所示。
满二叉树
在一棵二叉树中&＃xff0c;如果所有分支结点都存在左子树和右子树&＃xff0c;并且所有叶子都在同一层上&＃xff0c;这样的二叉树称为满二叉树。如下图所示&＃xff1a;
完全二叉树
完全二叉树是指最后一层左边是满的&＃xff0c;右边可能满也可能不满&＃xff0c;然后其余层都是满的。一个深度为k&＃xff0c;节点个数为 2^k - 1 的二叉树为满二叉树(完全二叉树)。就是一棵树&＃xff0c;深度为k&＃xff0c;并且没有空位。
完全二叉树的特点有&＃xff1a;
叶子结点只能出现在最下两层。
最下层的叶子一定集中在左部连续位置。
倒数第二层&＃xff0c;若有叶子结点&＃xff0c;一定都在右部连续位置。
如果结点度为1&＃xff0c;则该结点只有左孩子。
同样结点树的二叉树&＃xff0c;完全二叉树的深度最小。
注意&＃xff1a;满二叉树一定是完全二叉树&＃xff0c;但完全二叉树不一定是满二叉树。
算法如下&＃xff1a;
bool is_complete(tree *root)
{
queue q;
tree *ptr;
// 进行广度优先遍历(层次遍历)&＃xff0c;并把NULL节点也放入队列
q.push(root);
while ((ptr &＃61; q.pop()) !&＃61; NULL)
{
q.push(ptr->left);
q.push(ptr->right);
}
// 判断是否还有未被访问到的节点
while (!q.is_empty())
{
ptr &＃61; q.pop();
// 有未访问到的的非NULL节点&＃xff0c;则树存在空洞&＃xff0c;为非完全二叉树
if (NULL !&＃61; ptr)
{
return false;
}
}
return true;
}
二叉树的性质
二叉树的性质一&＃xff1a;在二叉树的第i层上至多有2^(i-1)个结点(i>&＃61;1)
二叉树的性质二&＃xff1a;深度为k的二叉树至多有2^k-1个结点(k>&＃61;1)
二叉树的顺序存储结构
二叉树的顺序存储结构就是用一维数组存储二叉树中的各个结点&＃xff0c;并且结点的存储位置能体现结点之间的逻辑关系。
二叉链表
既然顺序存储方式的适用性不强&＃xff0c;那么我们就要考虑链式存储结构啦。二叉树的存储按照国际惯例来说一般也是采用链式存储结构的。
二叉树每个结点最多有两个孩子&＃xff0c;所以为它设计一个数据域和两个指针域是比较自然的想法&＃xff0c;我们称这样的链表叫做二叉链表。
二叉树的遍历
二叉树的遍历(traversing binary tree)是指从根结点出发&＃xff0c;按照某种次序依次访问二叉树中所有结点&＃xff0c;使得每个结点被访问一次且仅被访问一次。
二叉树的遍历有三种方式&＃xff0c;如下&＃xff1a;
(1)前序遍历(DLR)&＃xff0c;首先访问根结点&＃xff0c;然后遍历左子树&＃xff0c;最后遍历右子树。简记根-左-右。
(2)中序遍历(LDR)&＃xff0c;首先遍历左子树&＃xff0c;然后访问根结点&＃xff0c;最后遍历右子树。简记左-根-右。
(3)后序遍历(LRD)&＃xff0c;首先遍历左子树&＃xff0c;然后遍历右子树&＃xff0c;最后访问根结点。简记左-右-根。
前序遍历&＃xff1a;
若二叉树为空&＃xff0c;则空操作返回&＃xff0c;否则先访问根结点&＃xff0c;然后前序遍历左子树&＃xff0c;再前序遍历右子树。
遍历的顺序为&＃xff1a;A B D H I E J C F K G
//先序遍历
function preOrder(node){
if(!node &＃61;&＃61; null){
putstr(node.show()&＃43; " ");
preOrder(node.left);
preOrder(node.right);
}
}
中序遍历&＃xff1a;
若树为空&＃xff0c;则空操作返回&＃xff0c;否则从根结点开始(注意并不是先访问根结点)&＃xff0c;中序遍历根结点的左子树&＃xff0c;然后是访问根结点&＃xff0c;最后中序遍历右子树。
遍历的顺序为&＃xff1a;H D I B E J A F K C G
//使用递归方式实现中序遍历
function inOrder(node){
if(!(node &＃61;&＃61; null)){
inOrder(node.left);//先访问左子树
putstr(node.show()&＃43; " ");//再访问根节点
inOrder(node.right);//最后访问右子树
}
}
后序遍历&＃xff1a;
若树为空&＃xff0c;则空操作返回&＃xff0c;否则从左到右先叶子后结点的方式遍历访问左右子树&＃xff0c;最后访问根结点。
遍历的顺序为&＃xff1a;H I D J E B K F G C A
//后序遍历
function postOrder(node){
if(!node &＃61;&＃61; null){
postOrder(node.left);
postOrder(node.right);
putStr(node.show()&＃43; " ");
}
}
实现二叉查找树
二叉查找树(BST)由节点组成&＃xff0c;所以我们定义一个Node节点对象如下&＃xff1a;
function Node(data,left,right){
this.data &＃61; data;
this.left &＃61; left;//保存left节点链接
this.right &＃61; right;
this.show &＃61; show;
}
function show(){
return this.data;//显示保存在节点中的数据
}
查找最大和最小值
查找BST上的最小值和最大值非常简单&＃xff0c;因为较小的值总是在左子节点上&＃xff0c;在BST上查找最小值&＃xff0c;只需遍历左子树&＃xff0c;直到找到最后一个节点
查找最小值
function getMin(){
var current &＃61; this.root;
while(!(current.left &＃61;&＃61; null)){
current &＃61; current.left;
}
return current.data;
}
该方法沿着BST的左子树挨个遍历&＃xff0c;直到遍历到BST最左的节点&＃xff0c;该节点被定义为&＃xff1a;
current.left &＃61; null;
这时&＃xff0c;当前节点上保存的值就是最小值
查找最大值
在BST上查找最大值只需要遍历右子树&＃xff0c;直到找到最后一个节点&＃xff0c;该节点上保存的值就是最大值。
function getMax(){
var current &＃61; this.root;
while(!(current.right &＃61;&＃61; null)){
current &＃61; current.right;
}
return current.data;
}
京公网安备 11010802041100号