文档介绍：第六章树和二叉树
第六章树和二叉树
树的概念和基本术语
二叉树
二叉树遍历
二叉树的计数
树与森林
霍夫曼树
二叉树(Binary Tree)
定义
五种形态
一棵二叉树是结点的一个有限集合,该集合或者为空,或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。
L
L
R
R
特点
每个结点至多只有两棵子树(二叉树中
不存在度大于2的结点)
二叉树(Binary Tree)
五种形态
L
L
R
R
特点
每个结点至多只有两棵子树(二叉树中
不存在度大于2的结点)
typedef char TreeData; //结点数据类型
typedef struct BTreeNode
{ //结点定义
TreeData data;
struct BTreeNode * LChild, * RChild;
} BTree;
typedef BTreeNode * BinTree;
//根指针
二叉链表的定义
二叉树遍历
树的遍历就是按某种次序访问树中的结点,要求每个结点访问一次且仅访问一次。
设访问根结点记作 D
遍历根的左子树记作 L
遍历根的右子树记作 R
则可能的遍历次序有
前序 DLR
中序 LDR
后序 LRD
D
L
R
中序遍历二叉树算法的定义:
若二叉树为空,则空操作;
否则
中序遍历左子树(L);
访问根结点(D);
中序遍历右子树(R)。
遍历结果
a + b * c - d - e / f
中序遍历(Inorder Traversal)
-
-
/
+
*
a
b
c
d
e
f
void InOrder ( BTree *T )
{
if ( T != NULL )
{
InOrder ( T->leftChild );
visit(T->data);
InOrder ( T->rightChild );
}
}
中序遍历二叉树的递归算法
int Leaf_Count(BTree * T)
{//求二叉树中叶子结点的数目
if(!T) return 0; //空树没有叶子
else if(!T->LChild&&!T->RChild) return 1; //叶子结点  else return Leaf_Count(T->LChild)+
Leaf_Count(T->RChild); //左子树的叶子数加上右子树的叶子数 }
3. 求二叉树中叶子结点的个数
Ltag=0, LChild为左孩子指针
Ltag=1, LChild为前驱线索
Rtag=0, RChild为右孩子指针
Rtag=1, RChild为后继指针
LChild
RChild
Data
Ltag
Rtag
线索二叉树(Threaded Binary Tree)
结点结构