《数据结构实验与实训教程（第4版）》程序代码(9)

int sl[]={0,5,11,18,26,35,45,56,68,81,95,110,126,143,161, 180,200,221,243,266,290,315,341,345,348,350}; printf( \正文内容为:\\n\\n\ for( i=0; i<26; i++ ) { sprintf( form, \ printf( form, &str[sl[i]] ); }

printf( \排版后输出内容为:\\n\\n\ ); paiban( str, 26, sl, sn );

}

40

实验7 二叉树的基本操作

四、参考程序

程序1：题1 二叉树的基本操作函数 typedef struct tree { /* 定义树的结构 */ int data; /* 假定树的元素类型为int */ struct tree *lchild; /* 左孩子*/

struct tree *rchild; /* 右孩子*/ }TREE;

typedef struct stack { /* 定义链接栈结构 */

TREE *t; /* 栈结点元素为指向二叉树结点的指针 */ int flag; /* 后序遍历时用到该标志 */ struct stack *link; /* 栈节点链接指针 */

}STACK;

void push( STACK **top, TREE *tree ) /* 树结点入栈 */ {

STACK *p; /* 工作指针 */ p = (STACK *)malloc( sizeof(STACK) ); /* 申请栈结点 */ p->t = tree; /* 根结点进栈 */ p->link = *top; /* 新栈结点指向栈顶 */

*top = p; /* 栈顶为新结点 */ }

void pop( STACK **top, TREE **tree ) /* 出栈, 栈内元素赋值给树结点 */ { STACK *p; /* 工作指针 */ if( *top == NULL ) /* 空栈 */ *tree = NULL; else { /* 栈非空 */ *tree = (*top)->t; /* 栈顶结点元素赋值给树结点 */ p = *top; *top = (*top)->link; /* 栈顶指向下一个链接, 完成出栈 */ free( p ); /* 释放栈顶结点空间 */ }

}

41

void SearchNode( TREE *tree, /* 查找树根结点 */ int key, /* 查找键值 */ TREE **pkpt, /* 返回键值为key结点的父节点的指针 */ TREE **kpt ) /* 返回键值为key结点的指针 */ { *pkpt = NULL; /* 初始化为查找结点不存在 */

*kpt = tree; /* 从根结点开始查找 */ while( 1 ) { if( 2 == key ) /* 找到 */

return; *pkpt = *kpt; /* 当前结点作为key键值的父结点, 继续查找 */ if( key < (*kpt)->data ) /* 键值小于当前结点, 查左子树 */ 3 ; else /* 键值大于当前结点, 查右子树 */ 4 ; } }

int InsertNode( TREE **tree, int key )

/* 查找树上插入新结点, 返回1:该键值结点已存在, -1:内存申请失败 */ { TREE *p, *q, *r; SearchNode( *tree, key, &p, &q ); if( 5 ) /* 找到相同键值的结点, 不插入 */ return 1; }

if( (r = (TREE *)malloc( sizeof(TREE) ) ) == NULL ) /* 申请新结点空间 */ return -1; 6 ;

r->lchild = r->rchild = NULL; /* 新结点的左右子树为空 */ if( p == NULL ) /* 如果为空树, 新结点为查找树的根结点 */ *tree = r;

else if( p->data > key ) /* 父结点键值大于新结点 */ 7 ; /* 新结点为左孩子 */ else 8 ; return 0;

/* 新结点为右孩子 */

int DeleteNode( TREE **tree, int key ) 不存在 */ {

/* 查找树上删除结点, 返回1:该键值结点

42

TREE *p, *q, *r;

SearchNode( *tree, key, &p, &q ); if( q == NULL ) /* 该键值结点不存在 */ return 1; if( p == NULL ) /* 被删结点为父结点 */ if( q->lchild == NULL ) /* 被删结点无左子数, 则其右子树作为根结点 */

*tree = 9 ; else { /* 被删结点有左子树, 则将其左节点作为根结点 */ *tree = 10 ;

r = q->lchild;

while( r->rchild != NULL )

/* 寻找被删结点左子树按中序遍历的最后结点 */ r = r->rchild; 11 ; /* 被删结点右子树作为找到结点的右子数 */

/* 被删结点不是根结点, 且无左子树 */

}

else if( __12______ ) if( q == p->lchild )

/* 被删结点为其父结点的左子结点,将其右子树作为父结点的左子树 */ p->lchild = q->rchild; else /* 被删结点为其父结点的右子结点,将其右子树作为父结点的右子树 */ _____13_________; else { /* 被删结点不是根结点, 且有左子树 */ r = q->lchild; while( r->rchild != NULL )

/* 寻找被删结点左子树按中序遍历的最后结点 */ r = r->rchild; _____14_______; /* 被删结点右子树作为找到结点的右子数 */ if(____15_____)

/* 被删结点是其父结点的左子结点,将其左子树作为父结点的左子树 */ p->lchild = q->lchild; else

/* 被删结点为其父结点的右子结点,将其右子树作为父结点的右子树 */

p->rchild = q->lchild; } free( q ); /* 释放被删结点内存空间 */ return 0;

}

程序2：题3 层次遍历打印二叉树 void OutputTree( TREE *tree )

43

{

/* 层次打印树结点, 中序遍历, 采用链接栈的迭代方法 */

STACK *top; /* 栈顶指针 */

int deep=0, no=0, maxdeep=0; /* 初始化树深度和遍历序号为0 */ top = NULL; /* 初始化为空栈 */

while(___1____ ) { /* 循环条件为二叉树还未遍历完, 或则栈非空 */

while( tree != NULL ) { /* 二叉树还未遍历完 */ ___2____; /* 树结点入栈 */ top->flag = ++deep; }

if( maxdeep < deep ) maxdeep = deep; ___3______; /* 沿左子树前进, 将经过的结点依次进栈 */ }

if( top != NULL ) { /* 左子数入栈结束, 且栈非空 */ deep = _____4___; no++; ___5_____; /* 树结点出栈 */

gotoxy( no * 4, deep + 2 ); printf( ____6____ ); /* 访问根结点 */ fflush( stdout ); ____7_____; /* 向右子树前进 */ } }

gotoxy( 1, maxdeep + 3 ); printf( \任意键继续\\n\getch();

程序3：题2 主函数

/* 本程序实现了二叉查找数的建立, 查找结点, 删除结点, 以及中序遍历, 前序遍历, 后序遍历的递归和迭代方法 */ #include #include #include void main() {

TREE *t; /* 定义树 */ int op=-1, i, ret; t = NULL; /* 初始化为空树 */ while( op != 0 )

44