Catalog
  1. 1. 如题,王世林不要看了,你学不会的。
数据结构实验五之二叉树相关操作

如题,王世林不要看了,你学不会的。

OK,我们先把头文件拽过来

#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
#define MAX_SIZE 1024
typedef char TElemType;
typedef char SeqTree[MAX_SIZE];//顺序二叉树的定义
typedef struct BiNode {//链式二叉树的定义
TElemType data;
struct BiNode* lchild, *rchild;
}*Bitree, BiTnode;
#define STACK_INIT_SIZE 100
#define STACKINCREASEMENT 10
#define OK 1

typedef struct {//栈的定义
Bitree* base;
Bitree* top;
int stacksize;
}SqStack;

接下来是函数体,有点长的亚子。

void CreatSeqTree(SeqTree tree , int i)
{
char ch;
cin >> ch;
if(ch == 'N'){
//tree[i] = '\0';
return;
}
tree[i] = ch;

CreatSeqTree(tree , 2 * i );
CreatSeqTree(tree , 2 * i + 1);
}



SqStack InitStack(SqStack& S) {
S.base = (Bitree*)malloc(sizeof(Bitree) * STACK_INIT_SIZE);
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return S;
}

Bitree GetTop(SqStack S, Bitree &e) {
if (S.top == S.base) {
cout << "遍历结束";
exit(OVERFLOW);
}
e = *(S.top - 1);
return e;
}

bool Push(SqStack& S, Bitree &e){
if (S.top - S.base >= S.stacksize) {
S.base = (Bitree*)realloc(S.base, (S.stacksize + STACKINCREASEMENT) * sizeof(Bitree));
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREASEMENT;
}
*S.top++ = e;
return 1;
}
Bitree Pop(SqStack &S, Bitree &e) {
if (S.top == S.base) return 0;
e = *--S.top;
return e;
}

void CreateBitree(Bitree &T) {

char c;
cin >> c;
if (c == 'N') T = NULL;
else {
if (!(T = (BiNode*)malloc(sizeof(BiNode)))) exit(OVERFLOW);
T->data = c;
CreateBitree(T->lchild);
CreateBitree(T->rchild);
}
}

bool PreOrder_print(Bitree T) {
//前序遍历输出
if (T) {
cout << T->data << " ";
if (PreOrder_print(T->lchild))
if (PreOrder_print(T->rchild))
return true;
return false;
}
else
return true;
}

void InOrder_print(Bitree T, SqStack S) {//算法1
Bitree P = T;
Push(S, P);
while (!(S.top - S.base == 0)) {
while (GetTop(S, P) && P) Push(S,P->lchild);
Pop(S, P);
if (!(S.top - S.base == 0)) {
Pop(S, P);
cout << P->data <<" ";
Push(S, P->rchild);
}

}


}

void InOrder_print2(Bitree T,SqStack S) {//算法2
Bitree P = T;
while (P || !(S.top - S.base == 0))
{
if (P) { Push(S, P); P = P->lchild; }
else {
Pop(S, P);
cout << P->data <<" ";
P = P->rchild;
}
}
}

void InOrderTravel(Bitree T)
{//常规中续遍历
if (T == NULL)
return;
InOrderTravel(T->lchild);
printf("%c ", T->data);
InOrderTravel(T->rchild);

}

void TailOrderTravel(Bitree T)
{//常规后续遍历
if (T == NULL)
return;
TailOrderTravel(T->lchild);
TailOrderTravel(T->rchild);
printf("%c ", T->data);
}

void preOrder(char *BT, int i) //先序遍历(递归法)
{
if (BT[i] != 0)
{
printf("%c ", BT[i]);
preOrder(BT, 2 * i );
preOrder(BT, 2 * i + 1);
}
}

最后,主函数

int main() {
Bitree T,T4,T5;
SqStack S;
cout << "-------前序遍历二叉树-------" << endl;
cout << "先序输入二叉树(空用N表示)"<< endl;
CreateBitree(T);
PreOrder_print(T);
cout << endl;
cout << "-------中序遍历二叉树-------" << endl;
cout << "先序输入二叉树(空用N表示)" << endl;
CreateBitree(T4);
InOrderTravel(T4);
cout << endl;

cout << "-------后序遍历二叉树-------" << endl;
cout << "先序输入二叉树(空用N表示)" << endl;
CreateBitree(T5);
TailOrderTravel(T5);
cout << endl;
Bitree T2;
cout << "-------栈的方式(算法1)中序遍历二叉树-------" << endl;
cout << "先序输入二叉树(空用N表示)" << endl;
CreateBitree(T2);
InitStack(S);
InOrder_print(T2,S);
cout << endl;
cout << "-------栈的方式(算法2)中序遍历二叉树-------" << endl;
cout << "先序输入二叉树(空用N表示)" << endl;
Bitree T3;
SqStack S3;
InitStack(S3);
CreateBitree(T3);
InOrder_print2(T3, S3);
cout << endl;
cout << "----------------------------以下是顺序二叉树--------------------------" << endl;
SeqTree tree;
InitSeqTree(tree);
printf("请先序输入二叉树:\n");
CreatSeqTree(tree,1);
cout << "先序遍历结果为:";
preOrder(tree, 1);
}



//A B C N N D E N G N N F N N N

运行结果如下:

Author: superzhaoyang
Link: http://yoursite.com/2019/11/04/数据结构实验五之二叉树相关操作/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Donate
  • 微信
  • 支付宝
��