数据结构--严蔚敏-树.ppt

数据结构线性结构：线性表,栈,队列
串,数组,广义表

非线性结构：树和二叉树
图，网
6.1树的定义

6.1.1定义和术语

1.树（tree):
树是n(n≥0)个结点的有限集T,
当n=0时，T为空树；
当n>0时,
(1)有且仅有一个称为T的根的结点,
(2)当n>1时,余下的结点分为m(m>0)个互不相交的有限集T1,T2,...,Tm,每个Ti(1≤i≤m)也是一棵树,且称为根的子树。AJBBBD树T2.嵌套集合：6.1.3树的基本操作

1.置T为空树：T={}
2.销毁树T
3.生成树T
4.遍历树T：按某种规则(次序)访问树T的每一个结点一次且
一次的过程。
5.求树T的深度
6.求树T的度
7.插入一个结点
8.删除一个结点
9.求结点的层号
10.求结点的度
11.求树T的叶子/非叶子
12...................6.2二叉树(binarytree)

6.2.1定义和术语

1.二叉树的递归定义
二叉树是有限个结点的集合，它或者为空集；或者是
由一个根结点和两棵互不相交的，且分别称为根的左子树
和右子树的二叉树所组成。
若二叉树为空集，则为空二叉树。二叉树T4T4T1二叉树111AAApC二叉树6.3遍历二叉树和线索二叉树

6.3.1遍历二叉树
按某种规则访问二叉树的每一个结点一次且仅一次的过程。
设:D----访问根结点,输出根结点；
L----递归遍历左二叉树；
R----递归遍历右二叉树。

遍历规则(方案):
DLR----前序遍历(先根,preorder)
LDR----中序遍历(中根,inorder)
LRD----后序遍历(后根,postorder)
DRL----逆前序遍历
RDL----逆中序遍历
RLD----逆后序遍历C前序遍历递归算法过程:先序遍历递归算法:

typedefstructBiTNode*BiTree;//结点指针类型
voidPreOrderTraverse(BiTreeT)
//T是指向二叉链表根结点的指针
{
if(!T)return;
else
{printf(“%c”,T->data);//访问根指针
PreOrderTraverse(T->lchild)；//递归访问左子树
PreOrderTraverse(T->rchild)；//递归访问右子树
}
return；
}
先序遍历递归算法

typedefstructBiTNode*BiTree;//结点指针类型
voidPreOrderTraverse(BiTreeT)
//T是指向二叉链表根结点的指针
{
if(T)
{printf(“%c”,T->data);//访问根指针
PreOrderTraverse(T->lchild)；//递归访问左子树
PreOrderTraverse(T->rchild)；//递归访问右子树
}
return；
}
T中序遍历递归算法

typedefstructBiTNode*BiTree;//结点指针类型
voidMidOrderTraverse(BiTreeT)
//T是指向二叉链表根结点的指针
{
if(T)
{MidOrderTraverse(T->lchild)；//递归访问左子树
printf(“%c”,T->data);//访问根指针
MidOrderTraverse(T->rchild)；//递归访问右子树
}
return；
}
T后序遍历递归算法

typedefstructBiTNode*BiTree;//结点指针类型
voidPostOrderTraverse(BiTreeT)
//T是指向二叉链表根结点的指针
{
if(T)
{PostOrderTraverse(T->lchild)；//递归访问左子树
PostOrderTraverse(T->rchild)；//递归访问右子树
printf(“%c”,T->data);//访问根指针
}
return；
}
4.非递归算法(中序遍历)

递归算法简明精炼，但效率较低，实际应用中常使用非递归；
某些高级语言不支持递归；
非递归算法思想：
（1）设置一个栈S存放所经过的根结点（指针）信息；初始化S；
（2）第一次访问到根结点并不访问，而是入栈；
（3）中序遍历它的左子树，左子树遍历结束后，第二次遇到根结点，就将根结点（指针）退栈，并且访问根结点；然后中序遍历它的右子树。
（4）当需要退栈时，如果栈为空则结束。

AD退栈t，访问C，
t->rchildt中序遍历非递归算法：

voidMidorder(structBiTNode*t)
//t为根指针
{
structBiTNode*st[maxleng+1];
//定义指针栈st[1..maxleng]
//用于保存