数据结构上机实验三：二叉树

100 阅读 0 评论 66 点赞

我是靠谱客的博主英俊往事，最近开发中收集的这篇文章主要介绍数据结构上机实验三：二叉树，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

目录：

上机题目
题目要求和程序测试的一些问题
知识点总结
代码（未完继续）

正文：

老师给出的题目如下：

这里写图片描述

题目要求和程序测试的一些问题：

注意应该使用非递归的方法进行遍历
输出二叉树的时候注意格式

知识点总结：

二叉树的定义和创建（递归）（边输入边创建）
二叉树的各种遍历（递归）（非递归一般都是用队列来实现）
二叉树的括弧表示、括弧表述法建树、树输出括号表示法
左右儿子互换（一般是用递归方式实现）
二叉树的输出（1.用满二叉树（空值为#）的方法替代要输出层数的问题）(2.获取二叉树的高度，采用的是递归的方式)

代码：
代码1：括号表达式建树、各种遍历、c++

#include <iostream>
#include<string.h>
#include<stack> 
using namespace std;
typedef struct node
{
char data;
struct node *lchild,*rchild;
}BinTree;
typedef struct node1
{
BinTree *btnode;
bool isFirst;
}BTNode;
void creatBinTree(char *s,BinTree *&root)
//创建二叉树，s为形如A(B,C(D,E))形式的字符串 
{
int i;
bool isRight=false;
stack<BinTree*> s1;
//存放结点 
stack<char> s2;
//存放分隔符
BinTree *p,*temp;
root->data=s[0];
root->lchild=NULL;
root->rchild=NULL;
s1.push(root);
i=1;
while(i<strlen(s))
{
if(s[i]=='(')
{
s2.push(s[i]);
isRight=false;
}
else if(s[i]==',')
{
isRight=true;
}
else if(s[i]==')')
{
s1.pop();
s2.pop();
}
else if(isalpha(s[i]))
{
p=(BinTree *)malloc(sizeof(BinTree));
p->data=s[i];
p->lchild=NULL;
p->rchild=NULL;
temp=s1.top();
//每次进来一个字母的时候，就将指针指向上一个根节点，每次进来一个反括号的时候就通过top指向更高层次
if(isRight==true)
{
temp->rchild=p;
cout<<temp->data<<"的右孩子是"<<s[i]<<endl;
}
else
{
temp->lchild=p;
cout<<temp->data<<"的左孩子是"<<s[i]<<endl;
}
if(s[i+1]=='(')
s1.push(p);
}
i++;
}
}
void display(BinTree *root)
//显示树形结构 
{
if(root!=NULL)
{
cout<<root->data;
if(root->lchild!=NULL)
{
cout<<'(';
display(root->lchild);
}
if(root->rchild!=NULL)
{
cout<<',';
display(root->rchild);
cout<<')';
}
}
}
void preOrder1(BinTree *root)
//递归前序遍历 
{
if(root!=NULL)
{
cout<<root->data<<" ";
preOrder1(root->lchild);
preOrder1(root->rchild);
}
}
void inOrder1(BinTree *root)
//递归中序遍历
{
if(root!=NULL)
{
inOrder1(root->lchild);
cout<<root->data<<" ";
inOrder1(root->rchild);
}
}
void postOrder1(BinTree *root)
//递归后序遍历
{
if(root!=NULL)
{
postOrder1(root->lchild);
postOrder1(root->rchild);
cout<<root->data<<" ";
}
}
void preOrder2(BinTree *root)
//非递归前序遍历 
{
stack<BinTree*> s;
BinTree *p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
cout<<p->data<<" ";
s.push(p);
p=p->lchild;
}
if(!s.empty())
{
p=s.top();
s.pop();
p=p->rchild;
}
}
}
void inOrder2(BinTree *root)
//非递归中序遍历
{
stack<BinTree*> s;
BinTree *p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
s.push(p);
p=p->lchild;
}
if(!s.empty())
{
p=s.top();
cout<<p->data<<" ";
s.pop();
p=p->rchild;
}
}
}
void postOrder2(BinTree *root)
//非递归后序遍历
{
stack<BTNode*> s;
BinTree *p=root;
BTNode *temp;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
//沿左子树一直往下搜索，直至出现没有左子树的结点 
{
BTNode *btn=(BTNode *)malloc(sizeof(BTNode));
btn->btnode=p;
btn->isFirst=true;
s.push(btn);
p=p->lchild;
}
if(!s.empty())
{
temp=s.top();
s.pop();
if(temp->isFirst==true)
//表示是第一次出现在栈顶 
{
temp->isFirst=false;
s.push(temp);
p=temp->btnode->rchild;
}
else
//第二次出现在栈顶 
{
cout<<temp->btnode->data<<" ";
p=NULL;
}
}
}
}
void postOrder3(BinTree *root)
//非递归后序遍历
{
stack<BinTree*> s;
BinTree *cur;
//当前结点 
BinTree *pre=NULL;
//前一次访问的结点 
s.push(root);
while(!s.empty())
{
cur=s.top();
if((cur->lchild==NULL&&cur->rchild==NULL)||
(pre!=NULL&&(pre==cur->lchild||pre==cur->rchild)))
{
cout<<cur->data<<" ";
//如果当前结点没有孩子结点或者孩子节点都已被访问过 
s.pop();
pre=cur;
}
else
{
if(cur->rchild!=NULL)
s.push(cur->rchild);
if(cur->lchild!=NULL)
s.push(cur->lchild);
}
}
}
int main(int argc, char *argv[])
{
char s[100];
while(scanf("%s",s)==1)
{
BinTree *root=(BinTree *)malloc(sizeof(BinTree));
creatBinTree(s,root);
display(root);
cout<<endl;
preOrder2(root);
cout<<endl;
inOrder2(root);
cout<<endl;
postOrder2(root);
cout<<"非递归后序遍历非"<<endl;
postOrder3(root);
cout<<endl;
}
return 0;
}

代码2：（括号表达式建立二叉树）

#include<stdio.h>
#include<String.h>
struct BiTNode
{
char c;
BiTNode* left;
BiTNode* right;
};
int
FindComma( char s[], int len ) {
int
match = 0;
int i;
for(
i = 0; i < len; ++i ) {
if( s[i] == '(' ) ++match;
else if( s[i] == ')' ) --match;
if(match==0 && s[i]==',')
break;
}
return i;
}
void CreateBiTree(char s[], int len, BiTNode* & p)
{
if( len <= 0 ) return;
p = new BiTNode();
// p是指针类型，是按照引用传递进来的，这样改变p的值，函数外也能知晓，如果不是引用，例如CreateBiTree(char s[], int len, BiTNood* p)则不能这样做。
p->c = s[0];
if( len == 1 ) { p->left = p->right = NULL; }
// 这是叶节点
else {
// 这是枝干节点
int
commaPos = FindComma( s+2, len-2 ); // s+2是左子树开始位置，commaPos是相对于左子树的偏移
CreateBiTree( s+2, commaPos, p->left );
if( len-3-commaPos-1<=0)
{
p->right=NULL;
return;
}
CreateBiTree( s+2+commaPos+1, len-3-commaPos-1, p->right );
}
}
void priorder(BiTNode *p)
{
if(p != NULL)
{
printf("%c ",p->c);
priorder(p->left);
priorder(p->right);
}
}
int main()
{
char* s="a(b(d,e),)";
BiTNode* p =new BiTNode();
CreateBiTree(s,strlen(s),p);
priorder(p);
return 0;
}

实验三：（左右子树的交换）

#include <stdlib.h>

#include <iostream>

#include <Windows.h>

using namespace std;
typedef char element;
typedef struct bitree
{
element data;
struct bitree* lchild;
struct bitree* rchild;
}bitree;
//交换左右子树

void changechild(bitree* root)
{
//element eleTemp;

bitree* bitTemp;
if (root == NULL)
{
root = NULL;
}
else
{
bitTemp = root->lchild;
root->lchild = root->rchild;
root->rchild = bitTemp;
changechild(root->lchild);
changechild(root->rchild);
}
}
void CreateBiTree(bitree* &T)
{
char
ch;
cin>>ch;
if(ch=='#') T=NULL;
else
{
T=(bitree *)malloc(sizeof(bitree));
T->data=ch;
cout<<"put in '"<<T->data<<"' lchild"<<endl;
CreateBiTree(T->lchild);
cout<<"put in '"<<T->data<<"' rchild"<<endl;
CreateBiTree(T->rchild);
}
}//CreateBiTree

void PreTraversal(bitree* T)
{
if (T == NULL)
{
return;
}
else
{
printf("%c,",T->data);
PreTraversal(T->lchild);
PreTraversal(T->rchild);
}
}
int main()
{
bitree* b1 ;
b1= (bitree *)malloc(sizeof(bitree));
bitree*
broot;
broot = b1;
printf("enter # is over,put in root noden");
CreateBiTree(b1);
printf("created treen");
PreTraversal(b1);
changechild(b1);
printf("nafter change lchild ,rchildn");
PreTraversal(b1);
system("pause");
return 0;
}