资源简介

(共47张PPT)
用抽象数据类型表示二叉树
信息技术选择性必修1 | 数据与数据结构 | 第四章第三节
课前回顾
数 组
链 表
查 找
插 入
删 除
√
×
√
×
3 二叉树的抽象数据类型
1 树
4 二叉树的基本操作方法
2 二叉树
目录
1
树
Part one
树形结构
树形结构
1
3
5
10
7
2
9
11
8
6
4
12
13
14
树的定义：n(n>=0)个结点的有限集合
结点数n>0时——有且仅有一个根结点 + m个互不相交的有限结点集
（m棵子树，m>=0）
结点数n=0时——空树
2
二叉树
Part two
二叉树定义
树
……
二叉树
二叉树定义：结点度数不超过2的树；每个节点的左子树的根节点被称为左孩子，右子树的根节点被称为右孩子。
特殊的二叉树
1. 满二叉树：一颗高度为h，且含有2h-1个结点的二叉树为满二叉树。
1
2
3
4
5
7
6
特殊的二叉树
2. 完全二叉树：假设一个高度为h、有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号1~n的结点一一对应时，称为完全二叉树。
1
2
3
4
5
6
1
2
3
4
5
7
6
特殊的二叉树
2. 完全二叉树：假设一个高度为h、有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号1~n的结点一一对应时，称为完全二叉树。
1
2
3
4
5
7
6
1
2
3
4
5
6
二叉树的存储结构
1. 顺序存储：用一组连续的存储单元依次自上而下、自左而右存储完全二叉树上的结点元素。
1
2
3
4
5
6
1 2 3 4 5 6
数组
0
1
2
3
4
5
二叉树的存储结构
1. 顺序存储：用一组连续的存储单元依次自上而下、自左而右存储完全二叉树上的结点元素。
1
2
3
4
5
6
1 2 3 4 5 6
数组
0
1
2
3
4
5
6
二叉树的存储结构
顺序存储弊端：
1
2
3
1 2 3
数组
0
1
2
3
4
5
6
空间利用率不高，比较适合完全二叉树。
二叉树的存储结构
2. 链式存储：用链表来存放一棵二叉树，二叉树中每个结点用链表的一个链结点来存储。
data next
lchild data rchild
二叉树的存储结构
2. 链式存储：用链表来存放一棵二叉树，二叉树中每个结点用链表的一个链结点来存储。
lchild data rchild
typedef struct BiNode{
TElemType data;
struct BiNode *lchild,*rchild;
//左右孩子指针
}BiNode,*BiTree;
二叉树的存储结构
2. 链式存储：用链表来存放一棵二叉树，二叉树中每个结点用链表的一个链结点来存储。
1
2
3
4
5
6
1
2
3
4
5
6
小结
3
二叉树的抽象数据类型
Part three
参考定义
ADT 二叉树
{
数据：采用任何一种方式存储二叉树，其存储类型用BinTreeType标识符表示，该类
型的一个二叉树用BT标识符表示。二叉树节点所保存的数据类型用ElemType表示。
操作：
void InitBTree(BinTreeType &BT)
//初始化二叉树，把它置为一课空树
void CreateBTree(BinTreeType &BT)
//建立对应的存储结构
bool EmptyBTree(BinTreeType &BT)
//判断一棵二叉树是否为空，若是则返回true，否则返回false
void TraverseBTree(BinTreeType &BT)
//按照一定的次序遍历一棵二叉树，使得每个节点的值均被访问一次
bool FindBTree(BinTreeType &BT , ElemType &node)
//从二叉树中查找值为node的节点，若存在，返回true，否则返回false
int BTreeDepth(BinTreeType &BT)
//求一棵二叉树的深度
void ClearBTree(BinTreeType &BT)
//清楚二叉树中的所有节点，使之变成一棵空树
…………
}ADT 二叉树
4
二叉树的基本操作方法
Part four
二叉树的遍历
遍历：按照一定的次序访问树中所有节点，并且每个节点的值仅被访问一次的过程。
根节点 N
左子树 L
右子树 R
先序遍历
中序遍历
后序遍历
二叉树的遍历
遍历：按照一定的次序访问树中所有节点，并且每个节点的值仅被访问一次的过程。
根节点 N
左子树 L
右子树 R
先序遍历
中序遍历
后序遍历
二叉树的遍历
遍历：按照一定的次序访问树中所有节点，并且每个节点的值仅被访问一次的过程。
根节点 N
左子树 L
右子树 R
先序遍历
中序遍历
后序遍历
二叉树的遍历
遍历：按照一定的次序访问树中所有节点，并且每个节点的值仅被访问一次的过程。
根节点 N
左子树 L
右子树 R
先序遍历
中序遍历
后序遍历
二叉树的遍历
若二叉树为非空：
（1）访问根节点
（2）先序遍历左子树
（3）先序遍历右子树
先序遍历
A
B
C
A
B
C
先序遍历
中序遍历
后序遍历
二叉树的遍历
若二叉树为非空：
（1）访问根节点
（2）先序遍历左子树
（3）先序遍历右子树
先序遍历
A
B
C
A
B
C
D
E
D
E
先序遍历
中序遍历
后序遍历
二叉树的遍历
若二叉树为非空：
（1）访问根节点
（2）先序遍历左子树
（3）先序遍历右子树
先序遍历
void preorder (BiTree T)
{
if(T!=NULL)
{
cout<data;
preorder(T->lchild);
preorder(T->rchild );
}
}
算法实现：
先序遍历
中序遍历
后序遍历
二叉树的遍历
void preorder (BiTree T)
{
if( T!=NULL)
{
cout<< T->data;
preorder( T->lchild);
preorder( T->rchild); );
}
}
A
B
C
D
E
F
A
A
A
A
A
A
先序遍历
中序遍历
后序遍历
二叉树的遍历
void preorder (BiTree T)
{
if( T!=NULL)
{
cout<< T->data;
preorder( T->lchild);
preorder( T->rchild); );
}
}
A
B
C
D
E
F
A
A
A
A
A
void preorder (BiTree T)
{
if( T!=NULL)
{
cout<< T->data;
preorder( T->lchild);
preorder( T->rchild); );
}
}
B
B
B
B
B
A
B
先序遍历
中序遍历
后序遍历
二叉树的遍历
void preorder (BiTree T)
{
if( T!=NULL)
{
cout<< T->data;
preorder( T->lchild);
preorder( T->rchild); );
}
}
A
B
C
D
E
F
A
A
A
A
A
void preorder (BiTree T)
{
if( T!=NULL)
{
cout<< T->data;
preorder( T->lchild);
preorder( T->rchild); );
}
}
B
B
B
B
B
A
B
void preorder (BiTree T)
{
if( T!=NULL)
{
cout<< T->data;
preorder( T->lchild);
preorder( T->rchild); );
}
}
D
D
D
D
D
D
先序遍历
中序遍历
后序遍历
二叉树的遍历
void preorder (BiTree T)
{
if( T!=NULL)
{
cout<< T->data;
preorder( T->lchild);
preorder( T->rchild); );
}
}
A
B
C
D
E
F
A
A
A
A
A
void preorder (BiTree T)
{
if( T!=NULL)
{
cout<< T->data;
preorder( T->lchild);
preorder( T->rchild); );
}
}
B
B
B
B
B
A
B
void preorder (BiTree T)
{
if( T!=NULL)
{
cout<< T->data;
preorder( T->lchild);
preorder( T->rchild); );
}
}
D
D
D
D
D
D
先序遍历
中序遍历
后序遍历
二叉树的遍历
void preorder (BiTree T)
{
if( T!=NULL)
{
cout<< T->data;
preorder( T->lchild);
preorder( T->rchild); );
}
}
A
B
C
D
E
F
A
A
A
A
A
void preorder (BiTree T)
{
if( T!=NULL)
{
cout<< T->data;
preorder( T->lchild);
preorder( T->rchild); );
}
}
B
B
B
B
B
A
B
void preorder (BiTree T)
{
if( T!=NULL)
{
cout<< T->data;
preorder( T->lchild);
preorder( T->rchild); );
}
}
D
D
D
D
D
D
先序遍历
中序遍历
后序遍历
二叉树的遍历
void preorder (BiTree T)
{
if( T!=NULL)
{
cout<< T->data;
preorder( T->lchild);
preorder( T->rchild); );
}
}
A
B
C
D
E
F
A
A
A
A
A
void preorder (BiTree T)
{
if( T!=NULL)
{
cout<< T->data;
preorder( T->lchild);
preorder( T->rchild); );
}
}
B
B
B
B
B
A
B
void preorder (BiTree T)
{
if( T!=NULL)
{
cout<< T->data;
preorder( T->lchild);
preorder( T->rchild); );
}
}
D
E
E
E
E
E
E
先序遍历
中序遍历
后序遍历
二叉树的遍历
void preorder (BiTree T)
{
if( T!=NULL)
{
cout<< T->data;
preorder( T->lchild);
preorder( T->rchild); );
}
}
A
B
C
D
E
F
A
A
A
A
A
void preorder (BiTree T)
{
if( T!=NULL)
{
cout<< T->data;
preorder( T->lchild);
preorder( T->rchild); );
}
}
B
B
B
B
B
A
B
void preorder (BiTree T)
{
if( T!=NULL)
{
cout<< T->data;
preorder( T->lchild);
preorder( T->rchild); );
}
}
D
E
E
E
E
E
E
先序遍历
中序遍历
后序遍历
二叉树的遍历
void preorder (BiTree T)
{
if( T!=NULL)
{
cout<< T->data;
preorder( T->lchild);
preorder( T->rchild); );
}
}
A
B
C
D
E
F
A
A
A
A
A
void preorder (BiTree T)
{
if( T!=NULL)
{
cout<< T->data;
preorder( T->lchild);
preorder( T->rchild); );
}
}
B
B
B
B
B
A
B
void preorder (BiTree T)
{
if( T!=NULL)
{
cout<< T->data;
preorder( T->lchild);
preorder( T->rchild); );
}
}
D
E
E
E
E
E
E
先序遍历
中序遍历
后序遍历
二叉树的遍历
void preorder (BiTree T)
{
if( T!=NULL)
{
cout<< T->data;
preorder( T->lchild);
preorder( T->rchild); );
}
}
A
B
C
D
E
F
A
A
A
A
A
void preorder (BiTree T)
{
if( T!=NULL)
{
cout<< T->data;
preorder( T->lchild);
preorder( T->rchild); );
}
}
B
B
B
B
B
A
B
D
E
先序遍历
中序遍历
后序遍历
二叉树的遍历
void preorder (BiTree T)
{
if( T!=NULL)
{
cout<< T->data;
preorder( T->lchild);
preorder( T->rchild); );
}
}
A
B
C
D
E
F
A
A
A
A
A
A
B
D
E
void preorder (BiTree T)
{
if( T!=NULL)
{
cout<< T->data;
preorder( T->lchild);
preorder( T->rchild); );
}
}
C
C
C
C
C
C
先序遍历
中序遍历
后序遍历
二叉树的遍历
void preorder (BiTree T)
{
if( T!=NULL)
{
cout<< T->data;
preorder( T->lchild);
preorder( T->rchild); );
}
}
A
B
C
D
E
F
A
A
A
A
A
A
B
D
E
void preorder (BiTree T)
{
if( T!=NULL)
{
cout<< T->data;
preorder( T->lchild);
preorder( T->rchild); );
}
}
C
C
C
C
C
C
先序遍历
中序遍历
后序遍历
二叉树的遍历
void preorder (BiTree T)
{
if( T!=NULL)
{
cout<< T->data;
preorder( T->lchild);
preorder( T->rchild); );
}
}
A
B
C
D
E
F
A
A
A
A
A
A
B
D
E
void preorder (BiTree T)
{
if( T!=NULL)
{
cout<< T->data;
preorder( T->lchild);
preorder( T->rchild); );
}
}
C
C
C
C
C
C
void preorder (BiTree T)
{
if( T!=NULL)
{
cout<< T->data;
preorder( T->lchild);
preorder( T->rchild); );
}
}
F
F
F
F
F
F
先序遍历
中序遍历
后序遍历
二叉树的遍历
void preorder (BiTree T)
{
if( T!=NULL)
{
cout<< T->data;
preorder( T->lchild);
preorder( T->rchild); );
}
}
A
B
C
D
E
F
A
A
A
A
A
A
B
D
E
void preorder (BiTree T)
{
if( T!=NULL)
{
cout<< T->data;
preorder( T->lchild);
preorder( T->rchild); );
}
}
C
C
C
C
C
C
void preorder (BiTree T)
{
if( T!=NULL)
{
cout<< T->data;
preorder( T->lchild);
preorder( T->rchild); );
}
}
F
F
F
F
F
F
先序遍历
中序遍历
后序遍历
二叉树的遍历
void preorder (BiTree T)
{
if( T!=NULL)
{
cout<< T->data;
preorder( T->lchild);
preorder( T->rchild); );
}
}
A
B
C
D
E
F
A
A
A
A
A
A
B
D
E
void preorder (BiTree T)
{
if( T!=NULL)
{
cout<< T->data;
preorder( T->lchild);
preorder( T->rchild); );
}
}
C
C
C
C
C
C
void preorder (BiTree T)
{
if( T!=NULL)
{
cout<< T->data;
preorder( T->lchild);
preorder( T->rchild); );
}
}
F
F
F
F
F
F
先序遍历
中序遍历
后序遍历
二叉树的遍历
A
B
C
D
E
F
A
B
D
E
C
F
先序遍历
中序遍历
后序遍历
二叉树的遍历
若二叉树为非空：
（1）中序遍历左子树
（2）访问根节点
（3）中序遍历右子树
中序遍历
void inorder (BiTree T)
{
if(T!=NULL)
{
inorder(T->lchild);
cout<data;
inorder(T->rchild );
}
}
算法实现：
先序遍历
中序遍历
后序遍历
二叉树的遍历
若二叉树为非空：
（1）后序遍历左子树
（2）后序遍历右子树
（3）访问根节点
后序遍历
void postorder (BiTree T)
{
if(T!=NULL)
{
postorder(T->lchild);
postorder(T->rchild );
cout<data;
}
}
算法实现：
课后思考
给定一个二叉树的前序和中序遍历序列，输出其后序遍历序列
输入
3 4 1 6 2 5 8 9
1 4 6 3 2 8 5 9
输出
？
用抽象数据类型表示二叉树
信息技术选择性必修1 | 数据与数据结构 | 第四章第三节

展开更多......

收起↑