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

11共有(_b_)个空指针域。

二叉树的五种基本形态

① ②

①空树：bt==NULL ②左右子树均空：bt->lchild==NULL and bt->rchild==NULL ③右子树为空：bt->rchild==NULL ④左子树为空：bt->lchild==NULL

⑤左右子树均非空。

前两种常作为递归结束条件，后三者常需要递归。

遍历二叉树

ii) 常见有四种遍历方式

按层次遍历，先序遍历，中序遍历，后序遍历。 按层次遍历：“从上至下，从左至右”，利用队列。

先序遍历：DLR；中序遍历：LDR；后序遍历LRD。

例：写出a+b*(c-d)-e/f的前缀、中缀和后缀表达式。 画出二叉树，分别进行前序、中序、后序遍历即可得到。

前缀表达式：- + a * b - c d / e f

中缀表达式：a + b * c - d - e / f

后缀表达式：a b c d - * + e f / -

jj) 先序遍历算法

void Preorder ( BinTree bt )

{

if ( bt ) {

visit ( bt->data );

Preorder ( bt->lchild );

Preorder ( bt->rchild );

}

}

kk) 中序遍历算法

void Inorder ( BinTree bt )

{

if ( bt ) {

Inorder ( bt->lchild );

visit ( bt->data );

Inorder ( bt->rchild );

11 答案：(a) n+1 (b) n+2。提示：只有根结点没有双亲。

}

}

ll) 后序遍历

void Postorder ( BinTree bt )

{

if ( bt ) {

Postorder ( bt->lchild );

Postorder ( bt->rchild );

visit ( bt->data );

}

}

mm) 按层次遍历

思路：利用一个队列，首先将根（头指针）入队列，以后若队列不空则取队头元素p，如果p不空，则访问之，然后将其左右子树入队列，如此循环直到队列为空。

void LevelOrder ( BinTree bt )

{

// 队列初始化为空

InitQueue ( Q );

// 根入队列

EnQueue ( Q, bt );

// 队列不空则继续遍历

while ( ! QueueEmpty(Q) ) {

DeQueue ( Q, p );

if ( p!=NULL ) {

visit ( p->data );

// 左、右子树入队列

EnQueue ( Q, p->lchild );

EnQueue ( Q, p->rchild );

}

}

}

若队列表示为“数组q[] + 头尾 front, rear”有：

void LevelOrder ( BinTree bt )

{

const int MAXSIZE = 1024;

BinTree q[MAXSIZE];

int front, rear;

// 队列初始化为空

front = rear = 0;

// 根入队列

q[rear] = bt; rear = ( rear+1 ) % MAXSIZE;

// 队列不空则循环

while ( front != rear ) {

p = q[front]; front = ( front+1 ) % MAXSIZE;

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