文档介绍：第六章树和二叉树
第六章树和二叉树
树的概念和基本术语
二叉树
二叉树遍历
二叉树的计数
树与森林
霍夫曼树
二叉树(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
前序遍历二叉树算法的定义:
若二叉树为空,则空操作;
否则
访问根结点(D);
前序遍历左子树(L);
前序遍历右子树(R)。
遍历结果
- + a * b - c d / e f
前序遍历(Preorder Traversal)
-
-
/
+
*
a
b
c
d
e
f
void PreOrder ( BTree *T )
{
if ( T != NULL )
{
visit(T->data);
PreOrder ( T->LChild );
PreOrder ( T->RChild );
}
}
前序遍历二叉树的递归算法
中序遍历二叉树算法的定义:
若二叉树为空,则空操作;
否则
中序遍历左子树(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 );
}
}
中序遍历二叉树的递归算法