二叉树遍历算法的应用.ppt

二叉树遍历算法的应用
1. 统计二叉树中结点总数numb
假设用中根遍历方法统计结点总个数，设计一个公有函数作为对外接口，调用同名的私有递归函数实现此功能。
//公有函数
void BiTree::injishu()
｛ int numb=0;
injishu( root, int &numb); // 调用私有函数
cout<<"\n numb="<<numb ; // 输出结果 }
算法
//私有函数
void BiTree::injishu(NodeType *t, int &m)
｛ if (t!=NULL)
｛ injishu(t->lch,m)； // 中根遍历左子树
cout<<t->data<<” ”； // 访问根结点
m++; // 结点记数
injishu(t->rch,m)； // 中根遍历右子树
｝｝
传世 为您整理
二叉树遍历算法的应用

首先看如下算法：
int BiTree::height(NodeType *p)
{ if (p == NULL) return 0;
else
{ int hl=height(p->lch);
int hr=height(p->rch);
return 1 + (hl>hr?hl:hr);
//1加上hl和hr的较大值
}
}
二叉树遍历算法的应用

假设已经有了一棵已经建立好的二叉树，怎样由它来复制另一个相同的二叉树？下列为私有递归函数，即复制二叉树的函数。
NodeType *BiTree::copy(NodeType *p)
{ NodeType *q;
if(p==NULL) return NULL;
else{
q=new NodeType;
q->data=p->data;
q->lch=copy(p->lch);
q->rch=copy(p->rch);
return q;
}
};
二叉树遍历算法的应用
线索二叉树
如果二叉树分别进行先根遍历中根遍历和后根遍历，。
有时为了运算方便，需要记下树中结点按某次序遍历下的前趋和后继结点。能否在二叉链表中保存这种信息呢？
二叉树遍历算法的应用
线索二叉树的基本概念
具有n个结点的二叉树，有n－1条边，正是这些边指向其左孩子、右孩子。这意味着在二叉链表的2n个孩子指针域中只用到了n+1个域，还有另外n+1个指针域为空，或被闲置。
现设法将这些空闲的指针域利用起来。
当某结点无左孩子时，令左指针指向它的前趋结点；当该结点无右孩子时，令右指针指向它的后继结点。
为了严格区分结点的孩子指针域究竟指向孩子结点还是指向前趋或后继结点，需在原结点结构中增加两个标志域。
二叉树遍历算法的应用
对一个已建好的二叉树的二叉链表进行线索化时规定（针对p结点）：
(1)p有左孩子时，则令左特征域p->ltag＝0；
(2)p无左孩子时，令p->ltag＝1；
并且让p->lch指向p的前趋结点；
(3)p有右孩子时，令p->rtag＝0；
(4)p无右孩子时，令p->rtag＝1；
并且让p->rch指向p的后继结点。
二叉树遍历算法的应用
A
D
H
I
F
E
C
B
G
A
D
H
I
F
E
C
B
G
A
D
H
I
F
E
C
B
G
A
D
H
I
F
E
C
B
G
NULL
NULL
(a)
(b)
(c)
(d)
（a）二叉树；（b）先根线索二叉树；（c）中根线索二叉树；（d