程序：第05章：树 程序设计经典教案.docx

PAGE1

程序设计经典教案

程序设计经典教案

树

程序5.1二叉树结点类

templateclassT

structBTNode

{

BTNode(){lChild=rChild=NULL;}

BTNode(constTx)

{

element=x;lChild=rChild=NULL;

}

BTNode(constTx,BTNodeT*l,BTNodeT*r)

{

element=x;lChild=l;rChild=r;

}

Telement;

BTNodeT*lChild,*rChild;

};

程序5.2二叉树类

templateclassT

classBinaryTree

{

public:

BinaryTree(){root=NULL;}

~BinaryTree(){Clear();}

boolIsEmpty()const;

voidClear();

boolRoot(Tx)const;

voidMakeTree(constTe,BinaryTreeTleft,BinaryTreeTright);

voidBreakTree(Te,BinaryTreeTleft,BinaryTreeTright);

voidPreOrder(void(*Visit)(Tx));

voidInOrder(void(*Visit)(Tx));

voidPostOrder(void(*Visit)(Tx));

protected:

BTNodeT*root;

private:

voidClear(BTNodeT*t);

voidPreOrder(void(*Visit)(Tx),BTNodeT*t);

voidInOrder(void(*Visit)(Tx),BTNodeT*t);

voidPostOrder(void(*Visit)(Tx),BTNodeT*t);

};

程序5.3部分二叉树运算

templateclassT

boolBinaryTreeT::Root(Tx)const

{

if(root){

x=root-element;returntrue;

}

elsereturnfalse;

}

templateclassT

voidBinaryTreeT::MakeTree(constTx,BinaryTreeTleft,BinaryTreeTright)

{

if(root||left==right)return;

root=newBTNodeT(x,left.root,right.root);

left.root=right.root=NULL;

}

templateclassT

voidBinaryTreeT::BreakTree(Tx,BinaryTreeTleft,BinaryTreeTright)

{

if(!root||left==right||left.root||right.root)return;

x=root-element;

left.root=root-lChild;right.root=root-rChild;

deleteroot;root=NULL;

}

程序5.4main函数

voidmain(void)

{

BinaryTreechara,b,x,y,z;图5.9(a)

y.MakeTree(E,a,b);

z.MakeTree(F,a,b);图5.9(b)

x.MakeTree(C,y,z);图5.9(c)

y.MakeTree(D,a,b);图5.9(d)

z.MakeTree(B,y,x);图5.9(e)

z.PreOrder(Visit);

z.BreakTree(e,y,x);

x.PreOrder(Visit);y.PreOrder(Visit);