- 首页 > it技术 > >
1024程序员节|实验3完整代码
数据结构深度优先1024程序员节
#include
#include
using namespace std;
//创建二叉树结构体；
typedef struct BiTNode {
int data;
struct BiTNode *lchild, *rchild;
//左右孩子指针
}BiTNode, *BiTree;
//构建一个循环队列
typedef struct Qnode {
BiTNode *base;
int front;
//头
int rear;
//尾
}sqQueue;
class tree {
private:
BiTree root;
sqQueue q;
public: tree() {
CreatBiTree(root);
}
BiTree get_root() {//得到root节点；
return root;
}
//创建一个循环队列
void InitQueue(sqQueue &q) {
q.base = new BiTNode[5];
q.front = q.rear = 0;
}
//创建二叉树
BiTree CreatBiTree(BiTree &t) {
int val;
cin >> val;
getchar();
if (val <= 0) t = NULL;
else {
t = new BiTNode;
t->data = https://www.it610.com/article/val;
CreatBiTree(t->lchild);
CreatBiTree(t->rchild);
}
return t;
}
//先序遍历
void PreOrderTraverse(BiTree &t) {
if (!t) return;
else {
cout << t->data << " ";
PreOrderTraverse(t->lchild);
PreOrderTraverse(t->rchild);
}
}
//中序排序
void InOrderTraverse(BiTree &t) {
if (!t) return;
else {
InOrderTraverse(t->lchild);
cout << t->data << " ";
InOrderTraverse(t->rchild);
}
}
//后序遍历
void PostOrderTraverse(BiTree &t) {
if (!t) return;
else {
PostOrderTraverse(t->lchild);
PostOrderTraverse(t->rchild);
cout << t->data << " ";
}
}
//层序遍历
void LevelOrderTraverse(BiTree &t) {
if (!t)return;
else {
InitQueue(q);
q.base[q.rear] = *t;
q.rear = (q.rear + 1) % 5;
}
while (q.front != q.rear) {
BiTNode temp = q.base[q.front];
cout << temp.data << " ";
if (temp.lchild) {
q.base[q.rear] = *temp.lchild;
q.rear = (q.rear + 1) % 5;
}
if (temp.rchild) {
q.base[q.rear] = *temp.rchild;
q.rear = (q.rear + 1) % 5;
}
q.front = (q.front + 1) % 5;
}
}
//统计节点的数目
void Count_TreeEnds(BiTree &t, int &n) {
if (t) {
if (!t->lchild && !t->rchild)
n++;
Count_TreeEnds(t->lchild, n);
Count_TreeEnds(t->rchild, n);
} }
//交换左右子树
BiTree Exchange(BiTree &t) {
if (!t)return NULL;
BiTree lchild = Exchange(t->rchild);
BiTree rchild = Exchange(t->lchild);
t->lchild = lchild;
t->rchild = rchild;
return t;
}
//5. 计算并输出该二叉树的深度。
int Depth(BiTree &t) {
int l = 0, r = 0;
if (t == NULL) return 0;
l = Depth(t->lchild) + 1;
r = Depth(t->rchild) + 1;
return l > r ? l : r;
}};
int main() {
tree T;
int n = 0;
//叶子结点
int deep;
//深度
BiTree PT = T.get_root();
cout << "先序遍历:";
T.PreOrderTraverse(PT);
cout << endl;
cout << "中序遍历:";
T.InOrderTraverse(PT);
cout << endl;
cout << "后序遍历:";
T.PostOrderTraverse(PT);
cout << endl;
cout << "层序遍历:";
T.LevelOrderTraverse(PT);
cout << endl;
cout << "叶子节点数：";
T.Count_TreeEnds(PT, n);
cout << n << endl;
BiTree exT;
exT = T.Exchange(PT);
cout << "交换后的先序遍历:";
T.PreOrderTraverse(exT);
cout << endl;
cout << "该二叉树的深度:";
deep = T.Depth(exT);
cout << deep << endl;
system("pause");
return 0;
}
推荐阅读
