数据结构课程设计二叉树遍历C++语言

淮阴工学院实践报告数据结构课程设计

设计题目：二叉树遍历

系别：计算机工程学院

专业：软件工程

班级：软件1111

学生姓名: 周淼学号: 1111315217

起止日期: 2012年12月24日~2012年12月30日指导教师：寇海洲

摘要：

现代社会生活中，计算机扮演着重要角色，而随着计算机运行速度的不断加快，对数据的处理能力也日益增强，因此，程序所涉及的数据成爆发式增长。随之而来的问题就是如何科学有效的对数据进行操作，使得计算机的时间和空间利用率最高。针对这样的问题，我选择了二叉树对数据的各种操作作为我的课程设计主题，希望通过课程设计来提高对数据的处理能力，促进对数据结构课程的理解，在日后面向对象的程序设计中科学的规划数据结构。在本次课程设计中，二叉树的建立使用了递归算法，遍历则同时使用了递归与非递归的算法，同时，在遍历算法的实现中使用了栈结构与队列结构，这大大方便了二叉树的遍历。在前序、中序、后续遍历算法中，分别实现了递归与非递归算法，从实际应用中体验了递归这一算法的优越性。

关键词：二叉树建立，递归与非递归，遍历，栈，队列

编号：47

淮阴工学院软件工程专业

数据结构课程设计答辩记录课题名称：二叉树的算法

班级软件1111 学号1111315217 姓名周淼

记录人：寇海洲2012 年12 月28日

目录

1需求分析 (6)

1.1二叉树与树结构 (6)

1.2面向对象的程序设计 (6)

1.3二叉树遍历的应用 (6)

1.4软件运行环境：Visual C++ 6.0版本 (6)

2概要设计 (7)

2.1 总体功能结构 (7)

2.2数据结构部分设计 (7)

2.2.1结点结构 (7)

2.2.2 二叉树结构 (8)

3详细设计 (13)

3.1建立二叉树 (13)

3.1.1功能描述 (13)

3.1.2算法原理 (13)

3.1.3 具体程序 (13)

3.2 前序遍历 (14)

3.2.1 功能原理 (14)

3.2.2 算法原理 (14)

3.2.3 具体程序 (14)

3.3 中序遍历 (15)

3.3.1 功能原理 (15)

3.3.2 算法原理 (15)

3.3.3 具体程序 (15)

3.4 后序遍历 (16)

3.4.1功能原理 (16)

3.4.2 算法原理 (16)

3.4.3 具体程序 (17)

3.5层次序非递归遍历 (18)

3.5.1 功能原理 (18)

3.5.2 算法原理 (18)

3.5.3 具体程序 (18)

3.6 栈结构 (19)

3.6.1 功能原理 (19)

3.6.2算法原理 (19)

3.6.3 具体程序 (19)

3.7 队列结构 (20)

3.7.1 功能原理 (20)

3.7.2 算法原理 (20)

3.7.3 具体程序 (20)

4调试与操作说明 (21)

致谢 (24)

参考文献 (25)

附录： (26)

1需求分析

1.1二叉树与树结构

树结构的是建立在数据逻辑结构基础上的数据结构类型，二叉树则是树结构中最常见和使用最多的类型。通过对二叉树的操作，可以实现多种数据操作，如排序、查找等。

一个好的二叉树遍历算法应包含以下功能：

1）以递归和非递归方法建立二叉树或完全二叉树；

2）实现二叉树的前序遍历、中序遍历、后序遍历；

3）每种遍历算法皆以递归和非递归方法实现；

4）在具体实现时应用其他数据结构类型对数据进行操作，如：栈，队列，数组。

1.2面向对象的程序设计

在面向对象的程序设计中，模板的使用很普遍，因此，如何在程序设计中使用模板使得方法的实现与定义分开，程序模块化，既方便了程序设计者，又为程序的后期维护带来便利。

1.3二叉树遍历的应用

当数据以数组或文档形式存储在内存时，其数据之间虽有逻辑联系，却过于分散，因此，建立二叉树以存储数据并且遍历该二叉树，可以从逻辑上理顺数据之间的关系，使得原本分数的数据排列的有序且可靠。一个好的二叉树应用算法其空间复杂度与时间复杂度必然最低，这样给程序带来时间和空间上的极大优化。

1.4软件运行环境：Visual C++ 6.0版本

2概要设计

2.1 总体功能结构

二叉树的遍历，主要包含以下功能：

1）建立二叉树：递归方法、非递归方法

2）中序遍历：递归方法、非递归方法

3）前序遍历：递归方法、非递归方法

4）后序遍历：递归方法、非递归方法

5）栈结构使用：遍历时输入临时变量以保存

6）队列结构使用：完全二叉树遍历时用以存储数据

2.2数据结构部分设计

2.2.1结点结构

二叉树结点结构中包数据域（data），指针域（*leftChild，*rightChild）。结点结构的代码如下：

struct BinTreeNode{ //树结点

T data;

BinTreeNode *leftChild;

BinTreeNode *rightChild;

BinTreeNode():leftChild(NULL), rightChild(NULL){}

BinTreeNode(T x, BinTreeNode *l = NULL, BinTreeNode *r = NULL)

:leftChild(l), rightChild(r){

data = x;

}

栈结构结点包含数据域（data），指针域（*link），实现代码如下：

struct StackNode{ //栈结点

T data;

StackNode *link;

StackNode(T d = 0, StackNode *next = NULL):link(next),data(d){}

};

队列结构结点包含数据域（data），指针域（*link），实现代码如下：struct LinkNode{

T data;

LinkNode *link;

LinkNode(LinkNode *ptr=NULL){

link = ptr;

}

LinkNode(const T &item, LinkNode *ptr = NULL){

data = item; link = ptr;

}

};

};

2.2.2 二叉树结构

二叉树包含了递归、非递归建树过程，递归、非递归的前序遍历、中序遍历、后续遍历过程。二叉树的类定义包含各种操作，实现代码如下：

template class BinaryTree{ //二叉树类定义

public:

BinaryTree():root(NULL){}

BinaryTree(T value):root(NULL){

RefValue = value;

}

BinaryTree(BinaryTree &s){

if (this != &s){

root=Copy(s.root);

}

}

~BinaryTree(){

destroy(root);

}

BinTreeNode *Parent(BinTreeNode *t){

return (root == NULL || root == t)?NULL:Parent(root, t);

}

BinTreeNode *LeftChild(BinTreeNode *t){

return (t != NULL)?t->leftChild:NULL;

}

BinTreeNode *RightChild(BinTreeNode *t){

return (t != NULL)?t->rightChild:NULL;

}

void PreOrder(void (*visit)(BinTreeNode *t)){

PreOrder(root, visit);

}

void InOrder(void (*visit)(BinTreeNode *t)){

InOrder (root, visit);

}

void PostOrder(void (*visit)(BinTreeNode *t)){

PostOrder(root, visit);

}

void CreateCompBinTree(T *CBT, int num){//建立完全二叉树CreateCompBinTree(CBT, num, 0, root);

}

void levelOrder(void (*visit)(BinTreeNode *t)); //层次序遍历

void PreOrder1(void (*visit) (BinTreeNode *t)); //非递归前序遍历

void InOrder1(void (*visit) (BinTreeNode *t)); //非递归中序遍历

void PostOrder1(void (*visit) (BinTreeNode *t)); //非递归后序遍历

friend istream& operator >> (istream &in, BinaryTree &Tree){//输入二叉树

Tree.CreateBinTree(in, Tree.root);

return in;

}

栈结构的定义中，包含了对数据的入栈、出栈、清空等基本操作，实现代码如下

template

class LinkedStack{

private:

StackNode *top;

public:

LinkedStack():top(NULL){} //无头结点

~LinkedStack(){

makeEmpty();

}

void Push(const T &x);

bool Pop(T &x);

bool IsEmpty()const{

return top==NULL;

}

bool IsFull()const{

return false;

void makeEmpty();

friend ostream& operator << (ostream &os, LinkedStack &s) { os<<"Stack Size: "<

StackNode *p=s.top;

int i=0;

while (p){

os<<++i<<": "<data<

p=p->link;

}

return os;

}

};

template

void LinkedStack::makeEmpty(){

StackNode *p;

while (top){

p=top;

top=top->link;

delete p;

}

}

队列的类定义，实现了对数据的入队、出队操作，实现代码如下：

template class LinkedQueue{ //无头结点

public:

LinkedQueue(){

rear = NULL;

front = NULL;

~LinkedQueue(){

makeEmpty();

}

bool EnQueue(const T &x);

bool DeQueue(T &x);

void makeEmpty();

bool IsEmpty()const{

return front == NULL;

}

friend ostream& operator << (ostream &os, LinkedQueue &Q){ LinkNode *p = Q.front;

int i = 0;

while (p){

os << "#" << ++i << ": " << p->data << endl;

p = p->link;

}

os << "Queue Size: " << Q.getSize() << endl;

return os;

}

void output();

protected:

LinkNode *front, *rear;

};

3详细设计

3.1建立二叉树

3.1.1功能描述

二叉树是程序的核心，如何合理的建立至关重要。本实例中使用递归和非递归方法分别建立二叉树，二叉树的数据来源于程序开始时建立的数组。建立后的二叉树保存，并且留作之后的遍历使用。

3.1.2算法原理

本实例使用的是完全二叉树，首先建立头结点，并且保存数据，然后根据递归方法，分别建立其左右孩子结点，且左右孩子结点的指针域指向空。

3.1.3 具体程序

以递归方式建立二叉树，每次建立一个结点后，将其左右孩子指针域置空，成为叶子结点。具体实现代码如下：

template void BinaryTree::CreateBinTree(istream &in, BinTreeNode *& subTree){

T item;

if (in >> item){

if (item != RefValue){

subTree = new BinTreeNode(item); //Create Root

assert(subTree);

CreateBinTree(in, subTree->leftChild); // Create left child tree

CreateBinTree(in, subTree->rightChild); // Create reght child tree

}

else

{

subTree = NULL;

}

}

}

//建立完全二叉树

templatevoid BinaryTree::CreateCompBinTree(T *CBT, int num, int rt, BinTreeNode *& subTree){

if (rt >= num) {

subTree = NULL;

}

else{

subTree = new BinTreeNode(CBT[rt]);

}

CreateCompBinTree(CBT, num, 2*rt+1, subTree->leftChild);

CreateCompBinTree(CBT, num, 2*rt+2, subTree->rightChild);

}

}

3.2 前序遍历

3.2.1 功能原理

通过前序遍历，将二叉树中的数据按照前序遍历的结果输出，达到前序便利的目的，方便数据的使用。

3.2.2 算法原理

前序遍历使用了递归与非递归两种方法，在程序头文件中定义了两个函数分别实现其功能。递归时，输出第一个结点数据时，找到数据，然后找到其后面的数据，然后依次递归输出。非递归时，使用栈和队列结构，将部分数据保存在栈或队列中，等待将数据放到合适位置。

3.2.3 具体程序

1）递归算法实现：

template void BinaryTree::PreOrder(BinTreeNode* subTree, void (*visit)(BinTreeNode *t)){

if (subTree != NULL){

visit(subTree);

PreOrder(subTree->leftChild, visit);

PreOrder(subTree->rightChild, visit);

}

}

2）非递归算法实现：

template void BinaryTree::PreOrder1(void (*visit) (BinTreeNode *t) ) {

LinkedStack*> S;

BinTreeNode *p = root;

S.Push (NULL);

while (p!=NULL) {

visit(p); //访问结点

if (p->rightChild != NULL)

S.Push (p->rightChild); //预留右指针在栈中

if (p->leftChild != NULL)

p=p->leftChild; //进左子树

else S.Pop(p); //左子树为空，由堆栈弹出

}

}

3.3 中序遍历

3.3.1 功能原理

通过中序遍历，将二叉树中的数据按照中序序遍历的结果输出，达到中序遍历的目的，实现数据的最优，方便数据的使用。

3.3.2 算法原理

中序遍历使用了递归与非递归两种方法，在程序头文件中定义了两个函数分别实现其功能。递归时，输出第一个结点数据时，找到数据，然后依次找到其后面的数据，然后依次递归输出。非递归时，使用栈和队列结构，将部分数据保存在栈与队列中，等待将数据放到合适位置。

3.3.3 具体程序

1）递归算法实现：

template void BinaryTree::InOrder(BinTreeNode *subTree,

void (*visit)(BinTreeNode *t)){

if (subTree != NULL){

InOrder(subTree->leftChild, visit);

visit(subTree);

InOrder(subTree->rightChild, visit);

}

}

2）非递归算法实现：

template void BinaryTree::InOrder1(void (*visit) (BinTreeNode *t)) {//非递归中序遍历

LinkedStack*> S;

BinTreeNode *p = root;

while(p!=NULL || !S.IsEmpty ()){

while (p!= NULL) { //遍历指针向左下移动

S.Push (p); //该子树沿途结点进栈

p=p->leftChild;

}

if (!S.IsEmpty()) { //栈不空时退栈

S.Pop(p); visit (p); //退栈, 访问

p=p->rightChild; //遍历指针进到右子女

}

}

}

3.4 后序遍历

3.4.1功能原理

通过后序遍历，将二叉树中的数据按照后序遍历的结果输出，达到后序遍历的目的，实现数据的最优，方便数据的使用。

3.4.2 算法原理

后序遍历使用了递归与非递归两种方法，在程序头文件中定义了两个函数分别实现其功能。递归时，输出第一个结点数据时，找到数据，然后依次找到其后面的数据，然后依次递归输出。非递归时，使用栈和队列结构，将部分数

据保存在栈与队列中，等待将数据放到合适位置。

3.4.3 具体程序

1）递归算法实现：

template void BinaryTree::PostOrder(BinTreeNode *subTree, void (*visit)(BinTreeNode *t)){

if (subTree != NULL ){

PostOrder(subTree->leftChild, visit);

PostOrder(subTree->rightChild, visit);

visit (subTree);

}

}2）非递归算法实现：

template void BinaryTree::PostOrder1(void (*visit) (BinTreeNode *t)){

//非递归后序遍历

LinkedStack > S;

stkNode w;

BinTreeNode *p=root; //p是遍历指针

do {

while (p != NULL) {

w.ptr = p;

w.tag = stkNode::L;

//枚举类型定义在struct stkNode中，如定义为全局性就简单了

S.Push (w);

p = p->leftChild;

}

int continue1 = 1;

while (continue1 && !S.IsEmpty ()) {

S.Pop (w); p = w.ptr;

switch (w.tag) { //判断栈顶的tag标记

case stkNode::L: w.tag = stkNode::R;

S.Push (w);

continue1 = 0;

p = p->rightChild; break;

case stkNode::R: visit (p); break;

}

}

} while (!S.IsEmpty()); //继续遍历其他结点

cout << endl;

}

3.5层次序非递归遍历

3.5.1 功能原理

层次序非递归遍历，依据的是递归原理，每次遍历一个结点后，同时让其左右孩子入队，以便达到层次序的目的。

3.5.2 算法原理

每次遍历完一个结点后，检查该结点是否为叶子结点，如果是叶子结点则继续下一结点的遍历，否则其左右孩子入队，继续遍历。

3.5.3 具体程序

template void BinaryTree::levelOrder (void (*visit) (BinTreeNode *t)) {//层次序遍历

if (root == NULL) return;

LinkedQueue *> Q;

BinTreeNode *p=root;

visit(p); Q.EnQueue(p);

while (!Q.IsEmpty ()) {

Q.DeQueue (p);

if (p->leftChild != NULL) {

visit (p->leftChild);

Q.EnQueue (p->leftChild);

}

if (p->rightChild != NULL) {

visit (p->rightChild);

Q.EnQueue(p->rightChild);

}

}

}

3.6 栈结构

3.6.1 功能原理

运用栈结构，在非递归算法中，未输出的数据暂时存入栈中，依据先进后出原则，方便了二叉树的遍历。

3.6.2算法原理

二叉树的结点信息，保存在栈中。第一个入栈的数据元素保存在栈底，后进栈的在上方，现出栈。

3.6.3 具体程序

template

void LinkedStack::Push(const T &x){

top = new StackNode(x, top);

}

template

bool LinkedStack::Pop(T &x){

if (IsEmpty()){

return false;

}

StackNode *p = top;

top=top->link;

x=p->data;

delete p;

return true;

}

3.7 队列结构

3.7.1 功能原理

运用队列结构，在层次序遍历算法中，未输出的数据暂时存入队列中，依据先进先出原则，方便了二叉树的遍历。

3.7.2 算法原理

层次序遍历二叉树信息时，二叉树的结点信息保存在队列中。第一个入队的数据元素保存队首，后入队的元素依次连接上，先入队的先出队。

3.7.3 具体程序

template void LinkedQueue::makeEmpty(){

LinkNode *p;

while (front){

p = front;

front = front->link;

delete p;

}

}

template bool LinkedQueue::EnQueue(const T &x){ if (!front){

front = rear = new LinkNode(x);

if (!front) return false;

}

else{

rear->link = new LinkNode(x);

if (!(rear->link)) return false;

rear = rear->link;

}

return true;

}

template bool LinkedQueue::DeQueue(T &x){

创建一个二叉树并输出三种遍历结果

实验报告 课程名称数据结构 实验项目实验三--创建一个二叉树并输出三种遍历结果 系别■计算机学院 _________________ 专业_______________ 班级/学号_____________ 学生姓名___________ 实验日期— 成绩______________________________ 指导 教师

实验题目：实验三创建一个二叉树并输出三种遍历结果 实验目的 1）掌握二叉树存储结构； 2）掌握并实现二叉树遍历的递归算法和非递归算法; 3）理解树及森林对二叉树的转换; 4）理解二叉树的应用一哈夫曼编码及WPL计算。 实验内容 1）以广义表或遍历序列形式创建一个二叉树，存储结构自选； 2）输出先序、中序、后序遍历序列； 3）二选一应用题：1）树和森林向二叉树转换；2）哈夫曼编码的应用问题。 题目可替换上述前两项实验内容） 设计与编码 1）程序结构基本设计框架 （提示：请根据所选定题目，描述程序的基本框架，可以用流程图、界面描述图、 框图等来表示） 2）本实验用到的理论知识遍历二叉树，递归和非递归的方法 （应用型

(提示：总结本实验用到的理论知识，实现理论与实践相结合。总结尽量简明扼要，并与本次实验密切相关，要求结合自己的题目并阐述自己的理解和想法) 3) 具体算法设计 1) 首先，定义二叉树的存储结构为二叉链表存储，每个元素的数 据类型Elemtype,定义一棵二叉树，只需定义其根指针。 2) 然后以递归的先序遍历方法创建二叉树，函数为CreateTree()，在输 入字符时要注意,当节点的左孩子或者右孩子为空的时候,应当输入一 个特殊的字符(本算法为“ #”),表示左孩子或者右孩子为空。 3) 下一步,创建利用递归方法先序遍历二叉树的函数,函数为 PreOrderTreeQ,创建非递归方法中序遍历二叉树的函数，函数为 InOrderTree()，中序遍历过程是：从二叉树的根节点开始，沿左子树 向下搜索，在搜索过程将所遇到的节点进栈；左子树遍历完毕后，从 栈顶退出栈中的节点并访问；然后再用上述过程遍历右子树，依次类 推，指导整棵二叉树全部访问完毕。创建递归方法后序遍历二叉树的 函数，函数为LaOrderTree()。 (提示：该部分主要是利用C、C++ 等完成数据结构定义、设计算法实现各种操作，可以用列表分步形式的自然语言描述，也可以利用流程图等描述) 4) 编码 #include #include #include typedef char DataType; #define MaxSize 100 typedef struct Node { DataType data; struct Node *lchild; struct Node *rchild; } *BiTree,BitNode;

数据结构——二叉树的操作(遍历及树形输出)

/*实验三：二叉树遍历操作验证*/ #include #include #include #include #include

if(T) //若非空 { if(T->data) { //输出 printf("%c",T->data); } preOrderTraverse(T->lchild); preOrderTraverse(T->rchild); } } //递归方法中序遍历二叉树 void inOrderTraverse(BiTree T) { if(T) //若非空 { preOrderTraverse(T->lchild); if(T->data) { //输出 printf("%c",T->data); } preOrderTraverse(T->rchild); } } //递归方法后序遍历二叉树 void postOrderTraverse(BiTree T) { if(T) //若非空 { preOrderTraverse(T->lchild); preOrderTraverse(T->rchild); if(T->data) { //输出 printf("%c",T->data); } } } //层序遍历二叉树 void LevelTraverse(BiTree T) { queue q;//建队 q.push(T);//根节点入队

二叉树的建立及其应用程序代码

#include #include #include #include typedef char elemtype; typedef struct tree //二叉树结构体 { elemtype data; struct tree *lchild; struct tree *rchild; }TREE; TREE *createbitree() //递归建立二叉树{ char ch; TREE *p; ch=getchar(); if (ch=='#') p=NULL; else { p=(TREE *)malloc(sizeof(TREE)); p->data=ch; p->lchild=createbitree(); p->rchild=createbitree(); } return p; } void preorder(TREE *p) //前序遍历 { if(p!=NULL) { printf("%c ",p->data); preorder(p->lchild); preorder(p->rchild); } } void inorder(TREE *p) //中序遍历 { if (p!=NULL)

{ inorder(p->lchild); printf("%c ",p->data); inorder(p->rchild); } } void postorder(TREE *p) //后序遍历 { if (p!=NULL) { postorder(p->lchild); postorder(p->rchild); printf("%c ",p->data); } } void shu(TREE *p,int len) //数的形状{ if (p!=NULL) { shu(p->lchild,len+1); for (int i=1;i<=4*len;i++) { printf(" "); } printf("%c",p->data); printf("------\n"); shu(p->rchild,len+1); } } int shendu(TREE *p) //计算深度 { int l,r; if (p==NULL) { return 0; } l=shendu(p->lchild)+1; r=shendu(p->rchild)+1; if (l>=r) //左右子树比较return l; else

树和二叉树习题数据结构

习题六树和二叉树一、单项选择题 1．以下说法错误的是 ( ) A．树形结构的特点是一个结点可以有多个直接前趋B．线性结构中的一个结点至多只有一个直接后继 C．树形结构可以表达(组织)更复杂的数据 D．树(及一切树形结构)是一种"分支层次"结构 E．任何只含一个结点的集合是一棵树 2．下列说法中正确的是 ( ) A．任何一棵二叉树中至少有一个结点的度为2 B．任何一棵二叉树中每个结点的度都为2 C．任何一棵二叉树中的度肯定等于2 D．任何一棵二叉树中的度可以小于2 3．讨论树、森林和二叉树的关系，目的是为了（）A．借助二叉树上的运算方法去实现对树的一些运算B．将树、森林按二叉树的存储方式进行存储

C．将树、森林转换成二叉树 D．体现一种技巧，没有什么实际意义 4．树最适合用来表示 ( ) A．有序数据元素 B．无序数据元素 C．元素之间具有分支层次关系的数据 D．元素之间无联系的数据5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9 B．11 C．15 D．不确定 6．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。 A．M1 B．M1+M2 C．M3 D．M2+M3 7．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（） A． 250 B． 500 C．254 D．505 E．以上答案都不对 8. 设给定权值总数有n 个，其哈夫曼树的结点总数为( ) A．不确定 B．2n C．2n+1 D．2n-1 9．二叉树的第I层上最多含有结点数为（） A．2I B． 2I-1-1 C． 2I-1 D．2I -1

数据结构课程设计_线索二叉树的生成及其遍历

数据结构课程设计 题目: 线索二叉树的生成及其遍历 学院： 班级： 学生姓名： 学生学号： 指导教师： 2012 年12月5日

课程设计任务书

摘要 针对以二叉链表作为存储结构时，只能找到结点的左、右孩子的信息，而得不到结点的前驱与后继信息，为了使这种信息只有在遍历的动态过程中才能得到。增设两个指针分别指示其前驱和后继，但会使得结构的存储密度降低；并且利用结点的空链域存放（线索链表），方便。同时为了记下遍历过程中访问结点的先后关系，附设一个指针pre始终指向刚刚访问过的结点，若指针p 指向当前访问的结点，则 pre指向它的前驱。由此得到中序遍历建立中序线索化链表的算法 本文通过建立二叉树，实现二叉树的中序线索化并实现中序线索二叉树的遍历。实现对已生成的二叉树进行中序线索化并利用中序线索实现对二叉树的遍历的效果。 关键词二叉树，中序线索二叉树，中序线索二叉树的遍历

目录 摘要 ............................................ 错误！未定义书签。第一章,需求分析................................. 错误！未定义书签。第二章,概要设计 (1) 第三章,详细设计 (2) 第四章,调试分析 (5) 第五章,用户使用说明 (5) 第六章,测试结果 (5) 第七章,绪论 (6) 第八章,附录参考文献 (7)

线索二叉树的生成及其遍历 第一章需求分析 以二叉链表作为存储结构时，只能找到结点的左、右孩子的信息，而得不到结点的前驱与后继信息，为了使这种信息只有在遍历的动态过程中才能得到。增设两个指针分别指示其前驱和后继，但会使得结构的存储密度降低；并且利用结点的空链域存放（线索链表），方便。同时为了记下遍历过程中访问结点的先后关系，附设一个指针pre始终指向刚刚访问过的结点，若指针p 指向当前访问的结点，则 pre指向它的前驱。由此得到中序遍历建立中序线索化链表的算法 本文通过建立二叉树，实现二叉树的中序线索化并实现中序线索二叉树的遍历。实现对已生成的二叉树进行中序线索化并利用中序线索实现对二叉树的遍历的效果。主要任务： 1.建立二叉树； 2.将二叉树进行中序线索化； 3.编写程序，运行并修改； 4.利用中序线索遍历二叉树 5.书写课程设计论文并将所编写的程序完善。 第二章概要设计 下面是建立中序二叉树的递归算法，其中pre为全局变量。 BiThrNodeType *pre; BiThrTree InOrderThr(BiThrTree T) { /*中序遍历二叉树T，并将其中序线索化，pre为全局变量*/ BiThrTree head; head=(BitThrNodeType *)malloc（sizeof（BiThrType））;/*设申请头结点成功*/ head->ltag=0;head->rtag=1;/*建立头结点*/ head->rchild=head;/*右指针回指*/ if(！T)head->lchild=head;/*若二叉树为空，则左指针回指*/ else{head->lchild=T;pre=head; InThreading(T);/*中序遍历进行中序线索化*/ pre->rchild=head; pre->rtag=1;/*最后一个结点线索化*/ head->rchild=pre; }; return head; } void InThreading(BiThrTree p) {/*通过中序遍历进行中序线索化*/ if(p)

二叉树的遍历和应用

内蒙古科技大学 本科生课程设计说明书 题目：数据结构课程设计 ——二叉树的遍历和应用 学生姓名： 学号： 专业： 班级： 指导教师： 2013年5月29日

内蒙古科技大学课程设计说明书 内蒙古科技大学课程设计任务书 I

内蒙古科技大学课程设计说明书 目录 内蒙古科技大学课程设计任务书..............................................................错误！未定义书签。目录....................................................................................................................................II 第一章需求分析 (3) 1.1课程设计目的 (3) 1.2任务概述 (3) 1.3课程设计内容 (3) 第二章概要设计 (5) 2.1设计思想 (5) 2.2二叉树的遍历 (5) 2.3运行界面设计 (6) 第三章详细设计 (7) 3.1二叉树的生成 (7) 3.2二叉树的先序遍历 (7) 3.3 二叉树的中序遍历 (8) 3.4二叉树的后续遍历 (8) 3.5主程序的设计 (8) 第四章测试分析 (11) 4.1二叉树的建立 (11) 4.2二叉树的先序、中序、后序遍历 (11) 第五章课程设计总结 (12) 附录：程序代码 (13) 致谢 ···········································································································错误！未定义书签。 II

数据结构C语言实现二叉树三种遍历

实验课题一：将下图中得二叉树用二叉链表表示： 1用三种遍历算法遍历该二叉树，给出对应得输出结果; 2写一个函数对二叉树搜索,若给出一个结点，根据其就是否属于该树，输出tｒｕe或者f ａｌse。 3写函数完成习题4、31(Ｃ＋+版)或4、2８（C版教科书）。 #iｎclｕde "stdio、h＂ ＃incluｄe”mallｏc、h" typedｅfｓtruct BｉTＮode ｛ cｈar data; sｔrucｔBiTＮode *lｃｈild,*rｃhiｌd; }ＢiTＮodｅ，*BiTrｅe； BｉＴree Creaｔe（BｉTｒeｅT) ｛ char ch； ch=getchａｒ(）; ｉｆ(ch=='#’） T=NULL; elｓe { T=(BiＴNode *）maｌloc(sｉｚｅｏf（ＢiTNｏｄe)）; Ｔ-〉data=ｃh； Ｔ-＞lｃｈiｌd=Creaｔe(T—〉lchilｄ); T—〉rchild=Creａte(Ｔ－〉rchｉld）； ｝ retuｒn Ｔ； } ｉnt node(BiＴrｅe Ｔ) { int sum1=0，a,b; ?iｆ（T) ｛ if（Ｔ！=ＮUＬL） ??sｕm1++;

?ａ=ｎode（Ｔ->lchiｌd); sｕm1＋=ａ； b=node(T—>rchｉld)； sum1+=b; ?} ｒetｕrn sum1； } int mｎode（BiTree T） { ?int sum２=0,ｅ，ｆ； if（T) { ?ｉf（（T->lcｈiｌd!=NULL）&＆(T－〉rchild!=NULL）)?sum2++； ?e=ｍnoｄｅ（Ｔ－〉lchild); suｍ2＋=e; f＝mnoｄｅ（T－〉rchｉｌd)； sum２+=f； ?｝ retｕrn sum2; ｝ void Preorｄer（BiTree T) { ｉf(Ｔ） { pｒintf（＂%c”，T－>daｔa)； Ｐreoｒder(Ｔ—>lchiｌｄ）； Ｐreorder（T－〉rchｉld）； ｝ } iｎt Sumｌeaｆ（BiTｒｅe T) { int suｍ=0,m，n; if（T） { if((！T-〉lchild）&&（!T-〉rｃhiｌd)) sum++； m=Ｓuｍleaf（T－>lchｉld)； suｍ+=m； n=Sumleaf(T—＞rｃhｉｌd); suｍ+＝ｎ； ｝ retuｒn ｓum； }

数据结构树和二叉树习题

树与二叉树 一.选择题 1.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结 点数为（）个。 A．15B．16C．17D．47 2.按照二叉树的定义，具有3个结点的不同形状的二叉树有（）种。 A. 3 B. 4 C. 5 D. 6 3.按照二叉树的定义，具有3个不同数据结点的不同的二叉树有（）种。 A. 5 B. 6 C. 30 D. 32 4.深度为5的二叉树至多有（）个结点。1 A. 16 B. 32 C. 31 D. 10 5.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的 结点数至少为（）。 A. 2h B. 2h-1 C. 2h+1 D. h+1 6.对一个满二叉树2，m个树叶，n个结点，深度为h，则（）。 A. n=h+m3 B. h+m=2n C. m=h-1 D. n=2 h-1 1深度为n的二叉树结点至多有2n-1 2满二叉树是除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树7.任何一棵二叉树的叶结点在先序.中序和后序遍历序列中的相对次序（）。 A.不发生改变 B.发生改变 C.不能确定 D.以上都不对 8.如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉 树的后序为（）。 A. uwvts B. vwuts C. wuvts D. wutsv 9.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是 dgbaechf，则其后序遍历的结点访问顺序是（）。 A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca 10.在一非空二叉树的中序遍历序列中，根结点的右边（）。 A. 只有右子树上的所有结点 B. 只有右子树上的部分结点 C. 只有左子树上的部分结点 D. 只有左子树上的所有结点 11.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为 先序遍历.中序遍历和后序遍历。这里，我们把由树转化得到的二叉树4叫做这棵数对应的二叉树。结论（）是正确的。 A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同 3对于深度为h的满二叉树，n=20+21+…+2h-1=2h-1，m=2h-1。故而n=h+m。 4树转化为二叉树的基本方法是把所有兄弟结点都用线连起来，然后去掉双亲到子女的连线，只留下双亲到第一个子女的连线。因此原来的兄弟关系就变为双亲与右孩子的关系。 1/ 9

二叉树的随机生成及其遍历

叉树的随机生成及其遍历 张 zhaohan 10804XXXXX 2010/6/12 问题重述 利用随机函数产生50个(不大于1 00且各不相同的)随机整数，用这些整数来生成一棵二叉树，分别对二叉树 进行先根遍历，中根遍历和后根遍历并输出树中结点元素序列。 程序设计 (一) 需求分析： ?问题的定义与要求： 1 、产生50个不大于100且各不相同的随机整数 (由系统的随机函数生成并 对100取模)；2、先根遍历并输出结果；3、中根遍历并输出结果；4、后根遍历并输出结果；按层次浏览二叉树结 5、点； 6、退出程序。 ?俞入：所需功能，选项为1?6。 ?输出：按照用户功能选择输出结果。 ?限制：输入的功能选择在1?6之间，否则无回应。 ?模块功能及要求： RandDif(): 生成50个随机不大于100的整数，每次生成不同随机整数。 CreateBitree(): 给数据结点生成二叉树，使每个结点的左右儿子指针指向左右儿子。 NRPreOrder(): 非递归算法的先根遍历。 inOrderTraverse(): 递归算法的中根遍历。 P ostOrderTraverseO：递归算法的后根遍历。 Welcome(): 欢迎窗口。 Menu()：菜单。 Goodbye()：再见窗口。 (二) 概要设计：

首先要生成二叉树，由于是对随机生成的50个数生成二叉树，故可以采取顺序存储的方式，对结点的左右儿子进行赋值。生成的二叉树是完全二叉树。 先根遍历的非递归算法： 1、根结点进栈 2、结点出栈，被访问 3、结点的右、左儿子（非空）进栈 4、反复执行2、3 ，至栈空为止。 先根遍历的算法流程图：根结点进栈( a[0]=T->boot,p=a[0] ) 访问结点printf(*p) 右儿子存在则进栈a[i]=(*p).rchild; i++; 左儿子存在则进栈a[i]=(*p).rchild; i++; 栈顶降低top--：i--;p=a[i]; 栈非空while(i>-1) 返回 中根遍历的递归算法流程图： T为空 Return; inOrderTraverse(T->lchild) Printf(T->data) inOrderTraverse(T->rchild) 返回

二叉树遍历课程设计心得【模版】

目录 一．选题背景 (1) 二．问题描述 (1) 三．概要设计 (2) 3.1.创建二叉树 (2) 3.2.二叉树的非递归前序遍历示意图 (2) 3.3.二叉树的非递归中序遍历示意图 (2) 3.4.二叉树的后序非递归遍历示意图 (3) 四．详细设计 (3) 4.1创建二叉树 (3) 4.2二叉树的非递归前序遍历算法 (3) 4.3二叉树的非递归中序遍历算法 (4) 4.4二叉树的非递归后序遍历算法 (5) 五．测试数据与分析 (6) 六．源代码 (6) 总结 (10) 参考文献: (11)

一．选题背景 二叉树的链式存储结构是用指针建立二叉树中结点之间的关系。二叉链存储结构的每个结点包含三个域，分别是数据域，左孩子指针域，右孩子指针域。因此每个结点为 由二叉树的定义知可把其遍历设计成递归算法。共有前序遍历、中序遍历、后序遍历。可先用这三种遍历输出二叉树的结点。 然而所有递归算法都可以借助堆栈转换成为非递归算法。以前序遍历为例，它要求首先要访问根节点，然后前序遍历左子树和前序遍历右子树。特点在于所有未被访问的节点中，最后访问结点的左子树的根结点将最先被访问，这与堆栈的特点相吻合。因此可借助堆栈实现二叉树的非递归遍历。将输出结果与递归结果比较来检验正确性。。 二．问题描述 对任意给定的二叉树（顶点数自定）建立它的二叉链表存贮结构，并利用栈的五种基本运算（置空栈、进栈、出栈、取栈顶元素、判栈空）实现二叉树的先序、中序、后序三种遍历，输出三种遍历的结果。画出搜索顺序示意图。

三．概要设计 3.1.创建二叉树 3.2.二叉树的非递归前序遍历示意图 图3.2二叉树前序遍历示意图3.3.二叉树的非递归中序遍历示意图 图3.3二叉树中序遍历示意图

数据结构第六章树和二叉树习题及答案

习题六树和二叉树 一、单项选择题 1．以下说法错误的是（） A. 树形结构的特点是一个结点可以有多个直接前趋 B. 线性结构中的一个结点至多只有一个直接后继 C. 树形结构可以表达（组织）更复杂的数据 D. 树（及一切树形结构）是一种”分支层次”结构 E. 任何只含一个结点的集合是一棵树 2. 下列说法中正确的是（） A. 任何一棵二叉树中至少有一个结点的度为2 B. 任何一棵二叉树中每个结点的度都为2 C. 任何一棵二叉树中的度肯定等于2 D. 任何一棵二叉树中的度可以小于2 3. 讨论树、森林和二叉树的关系，目的是为了（） A. 借助二叉树上的运算方法去实现对树的一些运算 B. 将树、森林按二叉树的存储方式进行存储 C. 将树、森林转换成二叉树 D. 体现一种技巧，没有什么实际意义4．树最适合用来表示（） A. 有序数据元素 B .无序数据元素 C.元素之间具有分支层次关系的数据 D .元素之间无联系的数据 5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9 B ．11 C ．15 D ．不确定 6. 设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1, M2和M3与森林F 对应的二叉树根结点的右子树上的结点个数是（）。 A．M1 B ．M1+M2 C ．M3 D ．M2+M3 7．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（） A．250 B ．500 C ．254 D ．505 E ．以上答案都不对 8. 设给定权值总数有n 个，其哈夫曼树的结点总数为（） A. 不确定 B . 2n C . 2n+1 D . 2n-1 9．二叉树的第I 层上最多含有结点数为（） I I-1 I-1 I A．2I B ．2 I-1 -1 C ．2 I-1 D ．2 I -1 10．一棵二叉树高度为h, 所有结点的度或为0，或为2，则这棵二叉树最少有（）结点A．2h B ．2h-1 C ．2h+1 D ．h+1 11. 利用二叉链表存储树，则根结点的右指针是（）。 A.指向最左孩子 B .指向最右孩子 C .空D .非空 12．已知一棵二叉树的前序遍历结果为为（）。 A．CBEFDA B ．FEDCBA 13．已知某二叉树的后序遍历序列是（）。 ABCDEF中序遍历结果 为 C ．CBEDFA D dabec, 中序遍历序列是 CBAEDF则后序遍历的结 果 ．不定 debac , 它的前序遍历是

二叉树的建立及几种简单的遍历方法

#include "stdio.h" #include "stdlib.h" #define STACK_INIT_SIZE 100 //栈存储空间初始分配量 #define STACKINCREMENT 10 //存储空间分配增量 //------二叉树的存储结构表示------// typedef struct BiTNode{ int data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; //-----顺序栈的存储结构表示------// typedef struct{ BiTree *top; BiTree *base; int stacksize; }SqStack; //*************************************************** //构造一个空栈s SqStack *InitStack(); //创建一颗二叉树 BiTree CreatBiTree(); //判断栈空 int StackEmpty(SqStack *S); //插入元素e为新的栈顶元素 void Push(SqStack *S,BiTree p); //若栈不为空，则删除s栈顶的元素e，将e插入到链表L中void Pop(SqStack *S,BiTree *q); //非递归先序遍历二叉树 void PreOrderTraverse(BiTree L); //非递归中序遍历二叉树 void InOrderTraverse(BiTree L); //非递归后序遍历二叉树 void PostOrderTraverse(BiTree L); //递归后序遍历二叉树 void PostOrder(BiTree bt); //递归中序遍历二叉树 void InOrder(BiTree bt); //递归先序遍历二叉树 void PreOrder(BiTree bt); //***************************************************

数据结构二叉树的创建及遍历

课程名称：数据结构实验 实验项目：二叉树的创建及遍历 姓名： 专业：计算机科学与技术 班级： 学号： 计算机科学与技术学院 20 17年11 月22 日

哈尔滨理工大学计算机科学与技术学院实验报告 实验项目名称：二叉树的建立及遍历 一、实验目的 1.熟悉掌握课本二叉树相关理论知识 2.实践与理论相结合，掌握二叉树的应用程序 3.学会二叉树的创建，遍历等其他基本操作的代码实现 二、实验内容 1.二叉树的创建代码实现 2.二叉树先序、中序、后序遍历代码实现 三、实验操作步骤 1.二叉树的建立 （1）树节点的定义 由于每个节点都由数据域和指左子树和右子树的指针，故结构体封装如下： typedef struct node { int data; struct node *left; struct node *right; }Tree,*bitree; （2）建立 采用递归的思想，先建立根再建立左子树，再建立右子树。递归截止条件子树为空，用-1代表树空 *T=(struct node *)malloc(sizeof(struct node));

(*T)->data=a; printf("%d的左节点",a); create(&(*T)->left); printf("%d的右节点",a); create(&(*T)->right); 2.三种遍历的实现 （1）先序遍历 依旧采用递归的思想，先遍历根后遍历左子树再遍历右子树。 printf("%d ",T->data); Pro(T->left); Pro(T->right); （2）中序遍历 先遍历左子树再遍历根最后遍历右子树 Mid(T->left); printf("%d ",T->data); Mid(T->right); （3）后序遍历 先遍历左子树再遍历右子树最后遍历根 Later(T->left); Later(T->right); printf("%d ",T->data); （4）按层遍历 按层遍历采用队列的思想，先将第一个节点入队然后在将其出队将其左右孩子入队。依

实验四 二叉树的遍历和应用04

江南大学通信与控制工程学院标准实验报告 （实验）课程名称：计算机软件技术基础实验名称：二叉树的遍历和应用 班级：自动化 姓名：李玉书 学号：03 指导教师：卢先领 江南大学通信与控制学院

江南大学 实验报告 学生姓名：张晓蔚学号：0704090304 实验地点：信控机房实验时间：90分钟 一、实验室名称：信控学院计算中心 二、实验项目名称：二叉树的遍历和应用 三、实验学时：4学时 四、实验原理： 二叉树的遍历和应用 五、实验目的： 1、掌握二叉树的数据类型描述及特点。 2、掌握二叉树的存储结构（二叉链表）的建立算法。 3、掌握二叉链表上二叉树的基本运算的实现。 六、实验内容： 阅读后面的程序，并将其输入到计算机中，通过调试为下面的二叉树建立二叉链表，并用递归实现二叉树的先序、中序、后序三种遍历。 七、实验器材（设备、元器件）： 计算机 八、实验步骤： 1、输入示例程序 2、构建按序插入函数实现算法 3、用C语言实现该算法 4、与源程序合并，编译，调试 5、测试，查错，修改

6、生成可执行文件，通过综合测试，完成实验 九、实验数据及结果分析： 测试用例 初始数据：ABDH,,I,,EJ,,K,,CFL,,,G,, 测试结果 十、实验结论： 该程序可以完成线性表的常规功能，且增加了异常处理，在异常情况下，例如： 表空，删除结点号不合法或出界，删除数值未找到等，这些情况下都能作出处理。可以通过边界测试。 十一对本实验过程及方法、手段的改进建议： 对书中程序的几点错误做了改正，见源程序。 附：源程序 #include typedef struct bitree { char data ; bitree *lchild; bitree *rchild;

树与二叉树习题解析(答)

习题五树与二叉树 一、选择题 1、一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足。 A、所有的结点均无左孩子 B、所有的结点均无右孩子 C、只有一个叶子结点 D、是任意一棵二叉树 2、一棵完全二叉树上有1001个结点，其中叶子结点的个数是。 A、250 B、500 C、254 D、505 E、以上答案都不对 3、以下说法正确的是。 A、若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树后序遍历序列中的最后一个结点 B、若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树中序遍历序列中的最后一个结点 C、在二叉树中，具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女结点 D、在二叉树中，具有一个子女的父结点，在中序遍历序列中，它没有后继子女结点 4、以下说法错误的是。 A、哈夫曼树是带权路径长度最短得数，路径上权值较大的结点离根较近 B、若一个二叉树的树叶是某子树中序遍历序列中的第一个结点，则它必是该子树后序 遍历序列中的第一个结点 C、已知二叉树的前序遍历和后序遍历并不能唯一地确定这棵树,因为不知道树的根结 点是哪一个 D、在前序遍历二叉树的序列中,任何结点其子树的所有结点都是直接跟在该结点之后 的 5、一棵有124个叶结点的完全二叉树，最多有个结点。

A、247 B、248 C、249 D、250 E、251 6、任何一棵二叉树的叶结点在前（先）序、中序和后序遍历序列中的相对次序。 A、不发生变化 B、发生变化 C、不能确定 7、设a、b为一棵二叉树上的两个结点。在中序遍历时，a在b前面的条件是。 A、a在b的右方 B、a在b的左方 C、a是b的祖先 D、a是b的子孙 8、设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含的结点总数为。 A、不确定 B、2k C、2k-1 D、2k+1 9、设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有个结点。 A、13 B、12 C、26 D、25 10、下面几个符号串编码集合中，不是前缀编码的是。 A、{0，10，110，1111} B、{11，10，001，101，0001} C、{00，010，0110，1000} D、{b,c,aa,ac,aba,abb,abc} 11、欲实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳的方案是二叉树采用存储结构。 A、三叉链表 B、广义表 C、二叉链表 D、顺序表 12、以下说法错误的是。 A、存在这样的二叉树，对它采用任何次序遍历其结点访问序列均相同 B、二叉树是树的特殊情形 C、由树转换成二叉树，其根结点的右子树总是空的 D、在二叉树只有一棵子树的情况下也要明确指出该子树是左子树还是右子树 13、树的基本遍历策略可分为先根遍历和后根遍历，二叉树的基本遍历策略可分为先序、中序和后序三种遍历。我们把由树转化得到的二叉树称该树对应的二叉树，则下面是正确的。 A、树的先根遍历序列与其对应的二叉树先序遍历序列相同

二叉树的建立及遍历

数据结构实验五 课程数据结构实验名称二叉树的建立及遍历第页 专业班级学号 姓名 实验日期:年月日评分 一、实验目的 １．学会实现二叉树结点结构和对二叉树的基本操作。 ２．掌握对二叉树每种操作的具体实现,学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。 二、实验要求 1．认真阅读和掌握和本实验相关的教材内容。 2．编写完整程序完成下面的实验内容并上机运行。 3.整理并上交实验报告。 三、实验内容 1.编写程序任意输入二叉树的结点个数和结点值，构造一棵二叉树,采用三种递归遍历算法（前序、中序、后序）对这棵二叉树进行遍历并计算出二叉树的高度。 2 .编写程序生成下面所示的二叉树,并采用先序遍历的非递归算法对此二叉 树进行遍历。 四、实验步骤 （描述实验步骤及中间的结果或现象。在实验中做了什么事情，怎么做的,发生的现象和中间结果) 第一题 #ｉnｃlude "sｔdafx.ｈ" #include＂ｉoｓtｒeam.h" #inclｕde"sｔｄliｂ.h"

＃incｌudｅ"ｓｔdiｏ.ｈ" #includelchiｌd）; int n＝depth(T->ｒchild); ?ｒeturn （m＞n?m:n)+1; } ｝ //先序,中序建树 sｔrucｔnodｅ*cｒeaｔe(chａr ＊pre,char *orｄ,int n) { ?struct node*T； intｍ; T=NUＬL; ?ｉｆ(n<=０) ?{ ?retuｒｎＮULL； ｝ ?elsｅ ?{ ?m=0; ??T＝nｅw(ｓtruct ｎode); Ｔ->ｄaｔａ=*pre; ?T－>lchild=T->rcｈilｄ=NULL; ?wｈile(ｏrd［ｍ]！＝*ｐre) ?ｍ++； T－>lcｈiｌd=create(prｅ＋1,ord，ｍ); ?Ｔ-＞rｃhild=ｃｒｅatｅ(pre+m＋１,orｄ+ｍ＋１，n-m-１）;

实验八：二叉树的遍历与应用

实验8 二叉树的遍历与应用 一、实验目的 1.进一步掌握指针变量的含义。 2.掌握二叉树的结构特征，理解并熟悉掌握创建二叉树和实现二叉树的三种遍历。 3.学会编写实现二叉树基本操作的递归算法，领会递归的实质。 二、实验要求 1. 给出程序设计的基本思想、原理和算法描述。 2. 源程序给出注释。 3. 保存和打印出程序的运行结果，并结合程序进行分析。 三、实验题目 1.编写算法，按层输出一棵顺序存储的二叉树所有结点的值。 /**********level.c************/ #include #define VirNode 0 /*虚结点值*/ #define MAXSIZE 100 /*一维数组的容量*/ typedef int TElemType; /*二叉树结点值的类型*/ typedef TElemType SqBitTree[MAXSIZE]; /*SqBitTree：顺序存储的二叉树类型名*/ void leveltree(SqBitTree bt) { } void main() {SqBitTree bb={15,1,2,3,4,5,0,0,8,0,0,11,0,0,0,0}; ; } 2.以二叉链表为存储结构实现二叉树的三种遍历（先序、中序、后序）的递归算法。将tree.h 和tree.c文件补充完整。 3.编写算法，按层次遍历一棵二叉链表。 4.编写算法，输出二叉树中所有度为2的结点。 void printdata(BitTree bt) 5.编写算法，求二叉树中结点的最大值。假设结点为整型。 int maxvalue(BitTree bt) 6.编写递归算法，求二叉树中以元素值为x的结点为根的子树的深度。(首先在遍历过程中找到值为x结点，然后调用Get_Depth()，求得值为x的结点为根的子树的深度)。 注意：后面有算法的过程与步骤，请填空。 7.编写算法，实现二叉链表的先序非递归遍历。 void PreOrderBiTree(BitTree T)

习题6树和二叉树.docx

习题6树和二叉树 说明： 本文档中，凡红色字标出的题请提交纸质作业，只写题号和答案即可。 6.1单项选择题 1. 由于二叉树屮每个结点的度最大为2,所以二叉树是一种特殊的树，这种说法_B_。 A. 正确 B.错误 2. 假定在一棵二叉树屮，双分支结点数为15,单分支结点数为30个，则叶子结点数为 B_个。 A. 15 B. 16 C. 17 D. 47 3. 按照二叉树的定义，具有3个结点的不同形状的二叉树有_C_种。 A. 3 B.4 C. 5 D. 6 4. 按照二叉树的定义，具有3个不同数据结点的不同的二叉树有_C_种。 A.5 B.6 C. 30 D. 32 5. 深度为5的二叉树至多有_C_个结点。 A. 16 B. 32 C. 31 D. 10 6. 设高度为h 的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点 数至少为 B 。 A. 2h B. 2h-l C. 2h+l D. h+l 7. 对一个满二叉树，m 个树叶，n 个结点，深度为h,则_A_。 A. n=h+m B. h+m=2n C. m=h-1 D. n=2 h -l 8. 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序_A_。 A.不发生改变 B.发生改变 C.不能确定 D.以上都不对 9. 如杲某二叉树的前根次序遍历结果为stuwv,中序遍历为uwtvs,那么该二叉树的后 序为_C_。 A. uwvts B. vwuts C. wuvts D. wutsv 10. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法_A_。 A.正确 B.错误 11. 某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是 dgbaechf,则其后序遍历的结点访问顺序是_D_。 A. bdgcefha B. gdbecfha 12. 在一非空二叉树的中序遍历序列中, A.只有右子树上的所有结点 13. 如图6.1所示二叉树的中序遍历序列是_B_。 14. 一棵二叉树如图6.2所示，其中序遍历的序列为 B 。 A. abdgcefh B. dgbaechf C. gdbehfca D. abcdefgh C. bdgaechf D. gdbehfca 根结点的右边_A_。 B.只有右子树上的部分结点 C.只有左子树上的部分结点 D.只有左子树上的所有结点 A. abcdgef B. dfebagc C. dbaefcg D. defbagc 图6」