null第六章（基础知识部分） 树与二叉树第六章（基础知识部分） 树与二叉树杨震 计算机科学与技术学院提 纲提 纲树的结构与操作1二叉树的定义与性质2二叉树的存储3二叉树的遍历46.1 树的结构及基本操作6.1 树的结构及基本操作树是一类重要的非线性数据结构，是以分支关系定义的层次结构。
[树的定义]
树是由n(n0)个结点组成的有限集合T，非空树满足：
1)有一个称之为根(root)的结点。
2)除根以外的其余结点被分成m(0m
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示该结点在树中的相对位置。根为第一层，其它的结点依次下推；若某结点在第L层上，则其孩子在第L+1层上。
堂兄弟 双亲在同一层的结点互为堂兄弟。
树的深(高)度 树中结点的最大层次。
有序树 树中各结点的子树从左至右是有次序的，不能互换。否则，称为无序树。
路径长度 从树中某结点Ni出发，能够“自上而下地”通过树中结点到达结点Nj，则称Ni到Nj存在一条路径，路径长度等于这两个结点之间的分支数。
树的路径长度 从根到每个结点的路径长度之和。
森林 是m(m0)棵互不相交的树的集合。null[树的基本操作]
1)初始化操作 initiate(T)
2)求根函数 root(T) / root(x)
3)求双亲函数 parent(T,x)
4)求孩子结点函数 child(T,x,i)
5)求右兄弟函数 right_sibling(T,x)
6)建树函数 crt_tree(x,F)
7)插入子树操作 ins_child(y,i,x)
8)删除子树操作 del_child(x,i)
9)遍历操作 traverse(T)
10)清除结构操作 clear(T)
6.2 二叉树的定义与性质6.2 二叉树的定义与性质[二叉树的概念]
二叉树的定义 二叉树是n(n0)个结点的有限集合，它或为空树(n=0)，或由一个根结点和两棵互不相交的左子树和右子树的二叉树组成。
二叉树的特点
定义是递归的
0结点的度2
是有序树
null二叉树的五种基本形态
两种特殊的二叉树
满二叉树 每一层上的结点数都是最大结点数。
完全二叉树 只有最下面两层结点的度可小于2，而最下一层的叶结点集中在左边若干位置上。12 34 5 6 712 34 5 6 78 9 10null性质1 二叉树的第i层上至多有2i-1(i1)个结点。
性质2 深度为k的二叉树至多有2k-1个结点(k1)。
性质3 对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2 ，则n0 = n2 + 1。
性质4 具有n个结点的完全二叉树的深度为 log2n+1。
性质5 一棵具有n个结点的完全二叉树(又称顺序二叉树)，对其结点按层从上至下(每层从左至右)进行1至n的编号，则对任一结点i(1in)有：
(1)若i>1，则i的双亲是i/2；若i=1，则i是根，无双亲。
(2)若2in，则i的左孩子是2i；否则， i无左孩子。
(3)若2i+1n，则i的右孩子是2i+1；否则， i无右孩子。
[二叉树的性质]6.3 二叉树的存储结构6.3 二叉树的存储结构顺序存储结构
[完全二叉树：按完全二叉树编号存放]
A B C D E
1 2 3 6 13
[三元组：存储结点数据和
左、右孩子在向量中的序号]
0 1 2 3 4
data A B C D E 1 2 3 4 5
lc 1 -1 3 -1 -1 data A B C D E
rc 2 -1 -1 4 -1 parent 0 1 -1 3 -4AB CDE[双亲：存储结点数据和 其父结点的序号]null[二叉链表][三叉链表
/带双亲的二叉链表] lc data rc lc data parent rc A^ B ^ C ^^ D^ E ^ A ^^ B ^ C ^^ D^ E ^ btbtnull二叉链表的类型定义
typedef
struct btnode{
btnode *lc,rc;
elemtp data;
} *BiTree;
三叉链表的类型定义
typedef
struct btnode{
btnode *lc,rc;
btnode *parent;
elemtp data;
} *BiTree;
6.4 二叉树的遍历6.4 二叉树的遍历[遍历的目的] 非线性结构线性结构
[遍历的概念] 指按某条搜索路线走遍二叉树的每个结点，使得树中每个结点都被访问一次，且仅被访问一次。
[典型的遍历方法]
先(根)序遍历 DLR
中(根)序遍历 LDR
后(根)序遍历 LRD
层序遍历DL R上述逆序方式很少使用null先序遍历：ABDEC
中序遍历：DBEAC
后序遍历：DEBCA
[利用遍历结果确定二叉树]
先序序列+中序序列
中序序列+后序序列
先序序列+后序序列
先序序列: ABCDEFGH
中序序列: BDCEAFHGAB CD EABFCGDEH思考：层序+先序/中序/后序
能否确定？如何做？null[先序遍历算法][递归算法]
void Preorder (BiTree T，void(*visit)( BiTree ))
{
if (T)
{ visite(T);
Preorder(T->lc,visit);
Preorder(T->rc,visit);
}
}[改进的递归算法]
void Preorder2 (BiTree T，void(*visit)( BiTree ))
{
visite(T);
if (T->lc)
Preorder2(T->lchild,visit);
if (T->rc)
Preorder2(T->rc, ,visit);
}null[消除尾递归的递归算法]
void Preorder3 (BiTree T，void(*visit)( BiTree ))
{
while (T)
{
visite(T);
Preorder3(T->lc,visit);
T = T->rc;
}[非递归算法]
void Preorder4 (BiTreeT,void(*visit)( BiTree ))
{ inistack(s);
p=bt;
push(s,NULL);
while (p)
{ visite(p);
if (p->rc)
push(s, p->rc);
if ( p->lc)
p=p->lc;
else
p=pop(s);
}
}null[中序遍历算法]
void Inorder (BiTree T，void(*visit)( BiTree ))
{
if (T)
{
Inorder(T->lc,visit);
visite(T);
Inorder(T->rc,visit);
}
}
[后序遍历算法]
void Postorder(BiTree T,
void(*visit)( BiTree ))
if (T)
{ Postorder(T->lc,visit);
Postorder(T->rc,visit);
visite(T);
}
null[按层次遍历算法]
void Levelorder (BiTree T);
{ iniqueue( q);
if (T) enqueue( q, T);
while (!empty( q))
{ x= dequeue( q);
visite( x );
if (x->lchild) enqueue( q, x->lc );
if (x->lchild) enqueue( q, x->lc );
}
}
null对用二叉链表表示的二叉树，设计一个算法，求其后序遍历的第一个结点。
typedef struct node {
etype data;
node *left, *right;
} node, *bitptr;
bitptr firstnode( bitptr root ) nullbitptr firstnode( bitptr root )
{
if ( ! root ) return NULL; // 空树不存在此结点
while ( root->left || root->right ) // 尚未找到叶子结点
{
if ( root->left )
root = root->left;
// 若有左子树，则沿左分枝向下查找最左下的叶子结点
else
root = root->right;
// 若无左子树，则沿右分枝向下查找最左下的叶子结点
}
return root; // 返回后序遍历的第一个结点
}
算法思想：
（1）若树根有左子树，则树根的左子树上最左下的叶子结点即为所求；
（2）若树根无左子树，仅有右子树，则树根右子树上最左下的叶子结点即为所求。 
浙公网安备 33021202002483