二叉排序树的建立_怎么建立二叉排序树_二叉排序树的创建(17)

{

if ( bt==0 ) return 0;

else if ( bt->lchild==0 and bt->rchild==0 ) return 1;

else return LeafCount(bt->lchild) + LeafCount(bt->rchild);

}

例：求二叉树的深度。

分析：① 0; ② 1; ③ 1+L; ④ 1+R; ⑤ 1+max(L,R)。简化：②③④⑤可合并成⑤。 int Depth ( BinTree bt )

{

if ( bt==0 ) return 0;

else return 1 + max(Depth(bt->lchild), Depth(bt->rchild));

}

线索二叉树

ss) 线索

n个结点的二叉链表中有n+1个空指针，可以利用其指向前驱或后继结点，叫线索，同时需附加一个标志，区分是子树还是线索。

lchild 有左子树，则指向左子树，标志ltag == 0；

没有左子树，可作为前驱线索，标志ltag == 1。

rchild 有右子树，则指向右子树，标志rtag == 0；

没有右子树，可作为后继线索，标志rtag == 1。

tt) 线索化二叉树

利用空指针作为线索指向前驱或后继。左边空指针可以作为前驱线索，右边空指针可以作为后继线索，可以全线索化或部分线索化。

表 错误！文档中没有指定样式的文字。.7 线索化二叉树的类型

中序线索化 前序线索化 后序线索化

uu) 画出线索二叉树

思路：先写出遍历序列，再画线索。 步骤： 标出必要的空指针（前驱?左指针；后继?右指针，要点：“不要多标，也不要少标”）。 写出对应的遍历序列（前序，中序或后序）。 对照遍历结果画线索。

例：画出图中二叉树的后序后继线索。

步骤：先标出所有空的右指针(DGCH)；写出后序遍历结果：DGEBHFCA；标出后继线索：D?G, G?E,

C?A, H?F。如图。

vv) 遍历线索二叉树

反复利用孩子和线索进行遍历，可以避免递归。 树和森林

ww) 树的存储结构

双亲表示法，孩子表示法，孩子兄弟表示法。

特点：双亲表示法容易求得双亲，但不容易求得孩子；孩子表示法容易求得孩子，但求双亲麻烦；两者可以结合起来使用。孩子兄弟表示法，容易求得孩子和兄弟，求双亲麻烦，也可以增加指向双亲的指针来解决。 xx) 树与二叉树的转换

表 错误！文档中没有指定样式的文字。.8 树和二叉树的对应关系

前驱、后继线索 中序全线索 前序全线索 后序全线索

前驱线索 中序前驱线索 前序前驱线索 后序前驱线索

后继线索 中序后继线索 前序后继线索 后序后继线索

特点：由树转化成的二叉树，根结点没有右孩子 例：树转换成二叉树。

yy) 森林与二叉树的转换

森林中第1棵树的根作为对应的二叉树的根；其他的树看作第1棵树的兄弟；森林中的树转换成对应的二叉树。则森林转换成对应的二叉树。 例：将森林转换成对应的二叉树。参见课本P138。 zz) 树的遍历

树的结构：①根，②根的子树。

先根遍历：①②。例：ABCDEFGHIJK。 后根遍历：②①。例：CEDFBHGJKIA。 aaa) 遍历森林

森林的结构：①第一棵树的根，②第一棵树的根的子树森林，③ 其余树(除第一棵外)组成的森林。

先序遍历：①②③。例：ABCDEFGHIJ。 中序遍历：②①③。例：BDCEAGFIJH。 注：先序遍历森林，相当于依次先根遍历每一棵树；中根遍历森林相当于后根遍历每一棵树。

树的结构划

森林的结构划分

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-25557-17.html