数据结构项目——二叉树实现

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

案例分析：

写出下面二叉树的先、中、后序遍历输出的结果：
注：先自己推算，然后用程序验算。

先序遍历的结果：A F H D C B J G E I K
中序遍历的结果：D H C F J B G A I E K
后序遍历的结果：D C H J G B F I K E A

代码如下：

#include "pch.h"
#include <iostream>
using namespace std;
int top = -1;
typedef struct Bitnode
{ 

char data;
Bitnode *lchild, *rchild;
}Bitnode,*bittree;
//创建一个二叉树
void Createbittree(bittree *t)
{ 

*t =(Bitnode *) malloc(sizeof(Bitnode));
(*t)->data = 'A';
(*t)->lchild= (Bitnode *)malloc(sizeof(Bitnode));
(*t)->rchild =(Bitnode *)malloc(sizeof(Bitnode));
(*t)->lchild->data = 'F';
(*t)->rchild->data = 'E';
(*t)->lchild->lchild = (Bitnode *)malloc(sizeof(Bitnode));
(*t)->lchild->rchild = (Bitnode *)malloc(sizeof(Bitnode));
(*t)->rchild->lchild = (Bitnode *)malloc(sizeof(Bitnode));
(*t)->rchild->rchild = (Bitnode *)malloc(sizeof(Bitnode));
(*t)->lchild->lchild->data = 'H';
(*t)->lchild->rchild->data = 'B';
(*t)->rchild->lchild->data = 'I';
(*t)->rchild->rchild->data = 'K';
(*t)->rchild->lchild->lchild= NULL;
(*t)->rchild->lchild->rchild= NULL;
(*t)->rchild->rchild->lchild = NULL;
(*t)->rchild->rchild->rchild = NULL;
(*t)->lchild->lchild->lchild = (Bitnode *)malloc(sizeof(Bitnode));
(*t)->lchild->lchild->lchild->lchild = NULL;
(*t)->lchild->lchild->lchild->rchild = NULL;
(*t)->lchild->lchild->rchild = (Bitnode *)malloc(sizeof(Bitnode));
(*t)->lchild->lchild->rchild->lchild = NULL;
(*t)->lchild->lchild->rchild->rchild = NULL;
(*t)->lchild->rchild->lchild = (Bitnode *)malloc(sizeof(Bitnode));
(*t)->lchild->rchild->lchild->lchild = NULL;
(*t)->lchild->rchild->lchild->rchild = NULL;
(*t)->lchild->rchild->rchild = (Bitnode *)malloc(sizeof(Bitnode));
(*t)->lchild->rchild->rchild->lchild = NULL;
(*t)->lchild->rchild->rchild->rchild = NULL;
(*t)->lchild->lchild->lchild->data = 'D';
(*t)->lchild->lchild->rchild->data = 'C';
(*t)->lchild->rchild->lchild->data = 'J';
(*t)->lchild->rchild->rchild->data = 'G';
}
//先序遍历入栈
void Push(Bitnode **a,Bitnode *elem)
{ 

a[++top] = elem;
}
//先序遍历出栈
void Pop()
{ 

if (top==-1)
{ 

return;
}
top--;
}
//获取栈顶元素
Bitnode *Get_top(Bitnode**a)
{ 

return a[top];
}
//输出节点数据
void Printelem(Bitnode *elem)
{ 

cout << elem->data << " ";
}
//实现先序遍历算法
void preorder(Bitnode*tree)
{ 

Bitnode *a[30];
Bitnode *p;
Push(a, tree);
while (top!=-1)
{ 

p = Get_top(a);
Pop();
while (p)
{ 

Printelem(p);
if (p->rchild)
{ 

Push(a,p->rchild);
}
p = p->lchild;
}
}
}
//中序遍历二叉树
void inorder(bittree tree)
{ 

Bitnode *a[30];	//定义一个顺序栈
Bitnode *p;		//临时指针
Push(a, tree);	//根节点入栈
while (top != -1)	//top！=-1来判定栈是否为空
{ 

while ((p=Get_top(a))&&p)//获取栈顶元素不为空
{ 

//左子树节点入栈，如果没有，null入栈
Push(a, p->lchild);
}
Pop();//跳出循环，栈顶元素是空，
if (top!=-1)
{ 

p = Get_top(a);//获取栈顶元素
Pop();
Printelem(p);
Push(a,p->rchild);//右子树节点入栈
}
}
}
//二叉树后序遍历（非递归法）
struct Snode
{ 

bittree p;
int tag;
};
//后序遍历的入栈函数
void PostPush(Snode*a, Snode sdata)
{ 

a[++top] = sdata;
}
//后序遍历
void PostOrder(bittree tree)
{ 

Snode a[20];
Bitnode*p;		//节点指针
int tag;
Snode sdata;
p = tree;
while (p||top!=-1)//用的或，这两种都行
{ 

while (p)
{ 

sdata.p = p;
sdata.tag = 0;//遍历左子树，设置标记位为0
PostPush(a, sdata);//入栈
p = p->lchild;//以该节点为根节点，遍历左子树
}
sdata=a[top];
Pop();
p = sdata.p;
tag = sdata.tag;
if (tag==0)//条件为真，左子树遍历完成，该节点需要遍历右子树
{ 

sdata.p = p;
sdata.tag = 1;
PostPush(a, sdata);//更改节点标志位，重新入栈
p = p->rchild;//将该节点的右子树设置为根节点，重新循环
}
else
{ 

Printelem(p);
p = NULL;
}
}
}
int main()
{ 

bittree tree;
Createbittree(&tree);
cout << "先序遍历的结果为：";
preorder(tree);
cout << endl;
cout << "中序遍历的结果为：";
inorder(tree);
cout << endl;
cout << "后序遍历的结果为：";
PostOrder(tree);
cout << endl;
return 0;
}

结果为：