实验3完整代码_笑霸fianl的博客

#include<iostream>
#include<Windows.h>
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 = 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;
}