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

p = NULL; // 必须的，使下一步继续退栈

}

}

}

}

注：后序非递归遍历的过程中，栈中保留的是当前结点的所有祖先。这是和先序及中序遍历不同的。在某些和祖先有关的算法中，此算法很有价值。

oo) 三叉链表的遍历算法

下面以中序遍历为例。

// 中序遍历三叉链表存储的二叉树

void Inorder ( BinTree bt, VisitFunc visit )

{

if ( bt==NULL ) return; // 空树，以下考虑非空树

// 找到遍历的起点

p = bt; // Note: p!=null here

while ( p->lchild ) p = p->lchild;

// 开始遍历

while ( p ) {

// 访问结点

visit ( p );

// p转下一个结点

if ( p->rchild ) { // 右子树不空，下一个在右子树

p = p->rchild;

while ( p->lchild ) p = p->lchild; // 转右子树的最左下结点} else { // 右子树为空，下一个在上层

f = p->parent;

while ( p == f->rchild ) { // 若p是右子树则一直上溯

p = f; f = f->parent;

}

}

}

}

遍历二叉树的应用 pp) 写出遍历序列（前、中、后序）

qq) 根据遍历序列画出二叉树

(a) 已知前序和中序序列，唯一确定二叉树。 例：前序：ABDEGCFH，中序：DBGEAFHC，画出二叉树。

分析：前序序列的第一个是根，这是解题的突破口。

步骤：①前序序列的第一个是根 ②在中序序列中标出根，分成左右子树 ③在前序序列中标出左右子树(根据结点个数即可) ④分别对左右子树的前序和中序序列重复以上步骤直至完成。

(b) 已知后序和中序序列，唯一确定二叉树。

例：后序：DGEBHFCA，中序：DBGEAFHC，画出二叉树。

分析：后序序列的最后一个是根，这是解题的突破口。

步骤：①后序序列的最后一个是根 ②在中序序列中标出根，分成左右子树 ③在后序序列中标出左右子树(根据结点个数即可) ④分别对左右子树的后序和中序序列重复以上步骤直至完成。

(c) 已知前序和后序序列，不存在度为1的结点时能唯一确定二叉树。

例：前序：ABDEC，后序：DEBCA，画出二叉树。又前序AB，后序BA则不能唯一确定二叉树。

注：对于不存在度为1的结点的二叉树，首先确定根结点，然后总可以将其余结点序列划分成左右子树，以此类推即可确定二叉树。

说明：画出二叉树后可以进行遍历以便验证。

rr) 编写算法

思路：按五种形态(①--⑤)分析，适度简化。

例：求二叉树结点的个数。

分析：① 0; ② 1; ③ L+1; ④ 1+R; ⑤ 1+L+R。

简化：② 1+L=0+R=0 ③ 1+L+R=0 ④ 1+L=0+R ⑤ 1+L+R 可合并成⑤一种情况。

int NodeCount ( BinTree bt )

{

if ( bt==0 ) return 0;

else return 1 + NodeCount(bt->lchild) + NodeCount(bt->rchild);

}

例：求二叉树叶子结点的个数。

分析：① 0; ② 1; ③ L; ④ R; ⑤ L+R。简化：③④⑤可合并成⑤。

int LeafCount ( BinTree bt )

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