1
7.7 树与二叉树的转换
转换步骤：
step1,将树中同一结点的兄弟相连 ; 加线
抹线
旋转
讨论 1：树如何转为二叉树？
孩子 — 兄弟
表示法
step2,保留结点的最左孩子连线，
删除其它孩子连线；
step3,将同一孩子的连线绕左孩子
旋转 45度角。
2
方法,加 线 — 抹线 — 旋转
a
b
e
i
d
f hg
c
树转二叉树举 例,
a
b
e i
d
f
h
g
c
兄弟相连 长兄为父 孩子靠左
特点是？
根结点没有右孩子！
3
讨论 2：二叉树怎样还原为树？
a
b
e i
d
f
h
g
c
要点,逆操作，把 所有右孩子变为兄弟 ！
a
b
d e
f hg
ic
4
法一：
① 各森林先各自转为二叉树；
② 依次连到前一个二叉树的右子树上。
讨论 3：森林如何转为二叉树？
即 F={T1,T2,…,Tm} B={root,LB,RB}
法二,森林直接变兄弟，再转为二叉树
（参见教材 P138图 6.17，两种方法都有转换示意图）
法一和法二得到的二叉树是完
全相同的、惟一的。
5
A
B C D
E
F
G
H
J
I
A
B C D
E
F
G
H
J
I
A
B
C
D
E
F G
H
J
I
森林转二叉树举例：
（用法二，森林直接变兄弟，再转为二叉树）
兄弟相连 长兄为父
头树为根 孩子靠左
6
A
B
C
D
E
F G
H
J
I
讨论 4：二叉树如何还原为森林？
要点,把最右边的子树变为森林，其余右子树变为兄弟
即 B={root,LB,RB} F={T1,T2,…,Tm}
A
B C D
E
F
G
H
J
I
E
F
A
B
C
D
G
H
J
I
7
7.8 树的遍历
树的遍历
例如,a
b
d
ec
先根序列：
后根序列：
a b c d e
b d c e a
深度优先遍历 （先根、后根）
广度优先遍历 （层次）
先根遍历
访问根结点；
按照从左到右依次先根遍
历根结点的每棵子树。
? 后根遍历
? 按照从左到右 依次后根遍
历根结点的每棵子树；
? 访问根结点。
树没有中序遍历（因
子树不分左右）
8
讨论：树若采用, 先转换，后遍历, 方式，结果是否一样？
a
b
d e
c
先序遍历：
后序遍历：
中序遍历：
d e c b a
a
b
d
ec
a b c d e
b d c e a
1,树的先根遍历与二叉树的 先序 遍历相同；
2,树的 后根 遍历相当于二叉树的 中序 遍历；
3,树没有中序遍历，因为子树无左右之分。
结论：
树的先根序列,a b c d e
树的后根序列,b d c e a
9
Void ABC(Bitree p,int l,int &h)
{ if p≠NIL then
{ l=l+1;
if l>h then h=l;
ABC(p->Lchild,l,h);
ABC(p->Rchild,l,h);
}
}
法 1：从根开始向下计算层次 (比从叶子往上计算更简单 )
l,h分别表示二叉树的层次
数和深度。
想一想,l和 h的初始值应设
为多少？
开始调用时，应当用 ABC
（ p,0,0）
若去掉 h形参中的,&”号，则 h不
变化，算出的更深层数不能正确
返回,h将永远为 0。
附 1：求二叉树的深度的算法
10
int BTreeDepth(Btree *BT) //*BT为二叉树某结点的指针
{ int leftdep,rightdep; //设左右两个深度 /层次计数器
if(BT==NULL) return(0); //当前结点指针为空则立即返回
else
{ leftdep= BTreeDepth(BT->left); //遍历当前结点左子树
rightdep=BTreeDepth(BT->right); //遍历当前结点右子树
if( leftdep>rightdep)return(leftdep+1); //从叶子起计数
else return(rightdep+1);
}
} //BTreeDepth
法 2：递归时从叶子开始向上计数，层深者保留。
11
void LayerOrder(Bitree T)//层序遍历二叉树
{ InitQueue(Q); //建一个空队 （ 初始化队列 ）
EnQueue(Q,T); //将一个结点插入队尾的函数
while( !QueueEmpty(Q) )
{ DeQueue(Q,&p); //队首结点出队 (送入 p)
visit(p);
if(p->lchild) EnQueue(Q,p->lchild); //p的左孩子入队
if(p->rchild) EnQueue(Q,p->rchild);//p的右孩子入队
}
}//LayerOrder
附 2：层次遍历算法 (需要利用队列 )
当孩子为空时不要
将空指针入队
12
附 3：判别给定二叉树是否为完全二叉树
int IsFull_Bitree(Bitree T)//是完全二叉树返回 1,否则返 0
{ InitQueue(Q); //建队 （ 初始化队列 ）
flag=0; //标志初始化
EnQueue(Q,T); //结点 T入队 （ 空指针也要入队 ）
while(!QueueEmpty(Q))
{ DeQueue(Q,&p); //队首结点出队 (送入 p)
if(!p) flag=1; //队首结点为空则标志变, 但也许是队尾
else if(flag)return 0; //下一轮才能确定是不是完全二叉树
else
{ EnQueue(Q,p->lchild);//不管孩子是否为空,都入队列
EnQueue(Q,p->rchild);
}
}//while
return 1; //执行至此必为队空且中间无空指针, 完全二叉
}//IsFull_Bitree
13
Status InOrderTrav( BiTree T,Status(*Visit)(TElemType e) )
{ //此处 Visit意思是对元素 e的一种操作
InitStack（ S）； p=T; //初始化栈
while( p || !StackEmpty(S) ) //树不空或栈不空则开始遍历
{ if( p ){Push(S,p);p=p->lchild;} //根指针进栈, 遍历左子树
else{
Pop(S,p)； //根指针退栈
if(! Visit(p->data))return ERROR;//访问根结点
p=p->rchild; //遍历右子树
} //else
} //while
return OK;
} //InOrderTrav
附 4：中序遍历的非递归算法 (或称迭代算法 )
7.7 树与二叉树的转换
转换步骤：
step1,将树中同一结点的兄弟相连 ; 加线
抹线
旋转
讨论 1：树如何转为二叉树？
孩子 — 兄弟
表示法
step2,保留结点的最左孩子连线，
删除其它孩子连线；
step3,将同一孩子的连线绕左孩子
旋转 45度角。
2
方法,加 线 — 抹线 — 旋转
a
b
e
i
d
f hg
c
树转二叉树举 例,
a
b
e i
d
f
h
g
c
兄弟相连 长兄为父 孩子靠左
特点是？
根结点没有右孩子！
3
讨论 2：二叉树怎样还原为树？
a
b
e i
d
f
h
g
c
要点,逆操作，把 所有右孩子变为兄弟 ！
a
b
d e
f hg
ic
4
法一：
① 各森林先各自转为二叉树；
② 依次连到前一个二叉树的右子树上。
讨论 3：森林如何转为二叉树？
即 F={T1,T2,…,Tm} B={root,LB,RB}
法二,森林直接变兄弟，再转为二叉树
（参见教材 P138图 6.17，两种方法都有转换示意图）
法一和法二得到的二叉树是完
全相同的、惟一的。
5
A
B C D
E
F
G
H
J
I
A
B C D
E
F
G
H
J
I
A
B
C
D
E
F G
H
J
I
森林转二叉树举例：
（用法二，森林直接变兄弟，再转为二叉树）
兄弟相连 长兄为父
头树为根 孩子靠左
6
A
B
C
D
E
F G
H
J
I
讨论 4：二叉树如何还原为森林？
要点,把最右边的子树变为森林，其余右子树变为兄弟
即 B={root,LB,RB} F={T1,T2,…,Tm}
A
B C D
E
F
G
H
J
I
E
F
A
B
C
D
G
H
J
I
7
7.8 树的遍历
树的遍历
例如,a
b
d
ec
先根序列：
后根序列：
a b c d e
b d c e a
深度优先遍历 （先根、后根）
广度优先遍历 （层次）
先根遍历
访问根结点；
按照从左到右依次先根遍
历根结点的每棵子树。
? 后根遍历
? 按照从左到右 依次后根遍
历根结点的每棵子树；
? 访问根结点。
树没有中序遍历（因
子树不分左右）
8
讨论：树若采用, 先转换，后遍历, 方式，结果是否一样？
a
b
d e
c
先序遍历：
后序遍历：
中序遍历：
d e c b a
a
b
d
ec
a b c d e
b d c e a
1,树的先根遍历与二叉树的 先序 遍历相同；
2,树的 后根 遍历相当于二叉树的 中序 遍历；
3,树没有中序遍历，因为子树无左右之分。
结论：
树的先根序列,a b c d e
树的后根序列,b d c e a
9
Void ABC(Bitree p,int l,int &h)
{ if p≠NIL then
{ l=l+1;
if l>h then h=l;
ABC(p->Lchild,l,h);
ABC(p->Rchild,l,h);
}
}
法 1：从根开始向下计算层次 (比从叶子往上计算更简单 )
l,h分别表示二叉树的层次
数和深度。
想一想,l和 h的初始值应设
为多少？
开始调用时，应当用 ABC
（ p,0,0）
若去掉 h形参中的,&”号，则 h不
变化，算出的更深层数不能正确
返回,h将永远为 0。
附 1：求二叉树的深度的算法
10
int BTreeDepth(Btree *BT) //*BT为二叉树某结点的指针
{ int leftdep,rightdep; //设左右两个深度 /层次计数器
if(BT==NULL) return(0); //当前结点指针为空则立即返回
else
{ leftdep= BTreeDepth(BT->left); //遍历当前结点左子树
rightdep=BTreeDepth(BT->right); //遍历当前结点右子树
if( leftdep>rightdep)return(leftdep+1); //从叶子起计数
else return(rightdep+1);
}
} //BTreeDepth
法 2：递归时从叶子开始向上计数，层深者保留。
11
void LayerOrder(Bitree T)//层序遍历二叉树
{ InitQueue(Q); //建一个空队 （ 初始化队列 ）
EnQueue(Q,T); //将一个结点插入队尾的函数
while( !QueueEmpty(Q) )
{ DeQueue(Q,&p); //队首结点出队 (送入 p)
visit(p);
if(p->lchild) EnQueue(Q,p->lchild); //p的左孩子入队
if(p->rchild) EnQueue(Q,p->rchild);//p的右孩子入队
}
}//LayerOrder
附 2：层次遍历算法 (需要利用队列 )
当孩子为空时不要
将空指针入队
12
附 3：判别给定二叉树是否为完全二叉树
int IsFull_Bitree(Bitree T)//是完全二叉树返回 1,否则返 0
{ InitQueue(Q); //建队 （ 初始化队列 ）
flag=0; //标志初始化
EnQueue(Q,T); //结点 T入队 （ 空指针也要入队 ）
while(!QueueEmpty(Q))
{ DeQueue(Q,&p); //队首结点出队 (送入 p)
if(!p) flag=1; //队首结点为空则标志变, 但也许是队尾
else if(flag)return 0; //下一轮才能确定是不是完全二叉树
else
{ EnQueue(Q,p->lchild);//不管孩子是否为空,都入队列
EnQueue(Q,p->rchild);
}
}//while
return 1; //执行至此必为队空且中间无空指针, 完全二叉
}//IsFull_Bitree
13
Status InOrderTrav( BiTree T,Status(*Visit)(TElemType e) )
{ //此处 Visit意思是对元素 e的一种操作
InitStack（ S）； p=T; //初始化栈
while( p || !StackEmpty(S) ) //树不空或栈不空则开始遍历
{ if( p ){Push(S,p);p=p->lchild;} //根指针进栈, 遍历左子树
else{
Pop(S,p)； //根指针退栈
if(! Visit(p->data))return ERROR;//访问根结点
p=p->rchild; //遍历右子树
} //else
} //while
return OK;
} //InOrderTrav
附 4：中序遍历的非递归算法 (或称迭代算法 )
