数据结构小课堂（6.7讲师版）

45 45 40 22 48 80 22 40 48 80

78 四、编程题

1.根据函数的定义，利用递归完成计算二叉树大小和高度的函数。 （1）intBinaryTree :: Size ( constBinTreeNode *t ) const { if ( t == NULL ) return 0; else

return 1 + Size ( t→leftChild )

+ Size ( t→rightChild );

}

（2）intBinaryTree :: Depth ( constBinTreeNode *t ) const { if ( t == NULL ) return -1;

else return 1 + Max ( Depth ( t→leftChild ),

Depth ( t→rightChild ) ); }

2.实现在链表上进行插入操作的功能函数。 intList::Insert ( constintx, constinti ) {

// Insert a node with data equal to x after the i-1’th ListNode*p = first; intk = 0; while ( p != NULL && k

{ p = p→link; k++; } // Locate i-1’th element if ( i<0 || p == NULL&&i!=0) { cout<< “无效的插入位置!\\n”; return 0; }

ListNode *newnode= new ListNode(x, NULL); // Allocate memory for the new node if (i == 0 ) { //Insert in the front of list newnode→link = first; first = newnode; }

else { //else newnode→link = p→link; p→link = newnode;

}

if(newnode->link==NULL) last=newnode; return 1; }

3.借助栈，实现二叉树的中序遍历。

template void BinaryTree :: InOrderTraverse () { stack S; BiTreeNode * p;

S.makeEmpty( ); p = root; //初始化 do{

while ( p ) { S.push(p); p = p→leftChild; }

if ( !S.empty( ) ) { //栈非空

p = S.top( ); S.pop( ); //退栈 cout<

p = p→rightChild; //向右链走 }

} while ( p || !S.empty( ) ); }