《数据结构》课程设计 报告样本 001(2)

数据结构课程设计

root=new BiNode; root->data=item; creat(root->lchild); creat(root->rchild);

}

}

2、非递归前序遍历

template void BiTree::PreOrder() { PreOrder(rootptr);

}

template

void BiTree::PreOrder(BiNode* root) { stack *> s; while(root!=NULL||!s.empty()) { while(root) { cout<data; s.push(root); root=root->lchild;

}

if(!s.empty()) { root=s.top(); s.pop();

root=root->rchild; }

}

}

3、非递归后序遍历

template void BiTree::PostOrder() { PostOrder(rootptr);

}

template

void BiTree::PostOrder(BiNode *root) {

stack*> s;//定义栈，节点类型为TreeNode BiNode *p = root;

BiNode *pre = NULL;//pre表示最近一次访问的结点

5

数据结构课程设计

while(p||!s.empty()) {

//沿着左孩子方向走到最左下。 while(p) {

s.push(p); p = p->lchild; }

//get the top element of the stack p = s.top();

//如果p没有右孩子或者其右孩子刚刚被访问过 if(p->rchild== NULL|| p->rchild == pre) {

//visit this element and then pop it cout <data; s.pop(); pre = p; p = NULL; } else {

p = p->rchild; }

}//end of while(p || st.size()!=0) }

4、求二叉树的高度

template int BiTree::depth() { return depth(rootptr);

}

template

int BiTree::depth(BiNode *root) { int rdep,ldep; if(root==NULL) return 0; else

{ ldep=depth(root->lchild); rdep=depth(root->rchild); return (rdep>ldep?rdep:ldep)+1; }

}

6

数据结构课程设计

5、 求二叉树每一层的结点数

template void BiTree::LevelNum() { LevelNum(rootptr);

}

template

void BiTree::LevelNum(BiNode * root) { queue *> q;

int front,rear,first,last,level; front=rear=first=0; last=level=1; if(root) { q.push(root); rear++;

while(frontlchild) { q.push(root->lchild); rear++;

}

if(root->rchild) { q.push(root->rchild); rear++;

}

if(front==last) { cout<<\第\<

}

}

}

}

6、求两节点最近共同祖先

7

数据结构课程设计

template

T BiTree::leastCommanAncestor(T n1, T n2){ }

template

T BiTree::leastCommanAncestor(BiNode * root, T n1, T n2) {

if(root == NULL || root->data == n1 || root->data == n2)

return -1;

(root->rchild->data == n1 || root->rchild->data == n2)) return root->data;

(root->lchild->data == n1 || root->lchild->data == n2)) return root->data; return root->data;

return leastCommanAncestor(root->lchild, n1, n2); return leastCommanAncestor(root->rchild, n1, n2); if((root->rchild!= NULL) &&

return leastCommanAncestor(rootptr,n1,n2);

if((root->lchild != NULL) &&

if(root->data > n1 && root->data < n2) if(root->data > n1 && root->data > n2)

if(root->data < n1 && root->data < n2) }

6、算法流程图

用户输入选择

创建二叉树 遍历二叉树

程序初始化 用户交互 求深度 求每层结点求共同祖先 处理并输出结果 结束 8

数据结构课程设计

六、程序测试与实现

1、函数之间的调用关系 main()

创建 遍历 求节点数深度

Creat() Depth() Count()

Preorder() Inorder() Postorder()

2、主程序

void main() {

BiTree Tree(1); while(1){

cout<<\欢迎使用本系统！！ \<>x; switch(x){

case 1:{

cout<<\请输入二叉树的前序遍历：\<

每层结点数 求LCA Levelnum() LCA() 9