题目示例👇

1. 实现二叉树前序、中序、后序遍历的递归算法；
2. 计算二叉树的深度（递归和非递归算法）；
3. 统计二叉树度为1的节点个数（递归和非递归算法）；

代码示例👇

#include<iostream>
#include<queue>
using namespace std;

//结点类
template<class T>
class BinaryTreeNode {
	//友元类声明
	template<class T>
	friend class BinaryTree;
private:
	T data;
	BinaryTreeNode<T>* leftchild;
	BinaryTreeNode<T>* rightchild;
public:
	//构造函数
	BinaryTreeNode() {
		leftchild = NULL;
		rightchild = NULL;
	}
	BinaryTreeNode(const T& dataValue) {
		data = dataValue;
		leftchild = NULL;
		rightchild = NULL;
	}
	BinaryTreeNode(const T& dataValue, BinaryTreeNode<T>* leftchildValue, BinaryTreeNode<T>* rightchildValue) {
		data = dataValue;
		leftchild = leftchildValue;
		rightchild = rightchildValue;
	}
	//析构函数
	~BinaryTreeNode() {
		leftchild = NULL;
		rightchild = NULL;
	}
	//取左结点
	BinaryTreeNode<T>* getLeft() {
		return leftchild;
	}
	//取右结点
	BinaryTreeNode<T>* getRight() {
		return rightchild;
	}
	//访问结点
	void VisitNode() {
		cout << data << " ";
	}
	//判断结点度是否为1
	bool isAlone() {
		if (leftchild == NULL && rightchild != NULL) {
			return true;
		}
		else if(leftchild != NULL && rightchild == NULL){
			return true;
		}
		else {
			return false;
		}
	}
};

//二叉树类
template<class T>
class BinaryTree {
private:
	BinaryTreeNode<T>* root;
public:
	//构造函数
	BinaryTree() {
		root = NULL;
		cout << "Now start to construct the BinaryTree" << endl;
		CreateNode(root);
	}
	//析构函数
	~BinaryTree() {
		root = NULL;
	}
	//前序构建二叉树
	void CreateNode(BinaryTreeNode<T>* &treeNode) {
		cout << "Please enter a value or '#' to stop:";
		T dataValue;
		cin >> dataValue;
		treeNode = new BinaryTreeNode<T>(dataValue);
		if (treeNode->data == '#') {
			delete treeNode;
			treeNode = NULL;
		}
		else {
			CreateNode(treeNode->leftchild);
			CreateNode(treeNode->rightchild);
		}
	}
	//取根节点
	BinaryTreeNode<T>* getRoot() {
		return root;
	}
	//递归前序遍历
	void PreOrder(BinaryTreeNode<T>* treeNode) {
		if (treeNode != NULL) {
			treeNode->VisitNode();
			PreOrder(treeNode->getLeft());
			PreOrder(treeNode->getRight());
		}
	}
	//递归中序遍历
	void InOrder(BinaryTreeNode<T>* treeNode) {
		if (treeNode != NULL) {
			InOrder(treeNode->getLeft());
			treeNode->VisitNode();
			InOrder(treeNode->getRight());
		}
	}
	//递归后序遍历
	void PostOrder(BinaryTreeNode<T>* treeNode) {
		if (treeNode != NULL) {
			PostOrder(treeNode->getLeft());		
			PostOrder(treeNode->getRight());
			treeNode->VisitNode();
		}
	}
	//递归算法求二叉树深度
	int CaculateTreeDepth1(BinaryTreeNode<T>* treeNode) {
		if (treeNode == NULL){
			return 0;
		}
		int depth = 0;
		int leftDepth = CaculateTreeDepth1(treeNode->getLeft());//求左子树的深度		
		int rightDepth = CaculateTreeDepth1(treeNode->getRight());//求右子树的深度
		depth = leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;//求二叉树的深度
		return depth;
	}
	//非递归算法求二叉树深度
	int CaculateTreeDepth2(BinaryTreeNode<T>* treeNode) {
		queue<BinaryTreeNode<T>*> q;
		if (treeNode == NULL) {
			return 0;
		}
		q.push(treeNode);
		int depth = 0;
		while (!q.empty()) {
			depth++;
			for (int size = q.size(); size > 0; size--) {
				BinaryTreeNode<T>* p = q.front();
				q.pop();
				if (p->getLeft()) {
					q.push(p->getLeft());
				}
				if (p->getRight()) {
					q.push(p->getRight());
				}
			}
		}
		return depth;
	}
	//递归统计二叉树度为1的节点个数
	int CaculateAlone1(BinaryTreeNode<T>* treeNode) {
		int count = 0;
		if (treeNode != NULL) {
			if (treeNode->isAlone()) {
				count++;
			}
			count += CaculateAlone1(treeNode->getLeft());
			count += CaculateAlone1(treeNode->getRight());
		}
		return count;
	}
	//非递归统计二叉树度为1的节点个数
	int CaculateAlone2(BinaryTreeNode<T>* treeNode) {
		int count = 0;
		if (treeNode != NULL) {
			queue<BinaryTreeNode<T>*> q;
			q.push(treeNode);
			while (!q.empty()) {
				for (int size = q.size(); size > 0; size--) {
					BinaryTreeNode<T>* p = q.front();
					q.pop();
					if (p->isAlone()) {
						count++;
					}
					if (p->getLeft()) {
						q.push(p->getLeft());
					}
					if (p->getRight()) {
						q.push(p->getRight());
					}
				}
			}
		}
		return count;
	}
};
int main() {
	//前序构建二叉树
	BinaryTree<char> test;
	//遍历二叉树
	cout << endl << "前序遍历结果：";
	test.PreOrder(test.getRoot());
	cout << endl << "中序遍历结果：";
	test.InOrder(test.getRoot());
	cout << endl << "后序遍历结果：";
	test.PostOrder(test.getRoot());
	//求二叉树深度
	cout << endl << "递归求得深度：";
	cout << test.CaculateTreeDepth1(test.getRoot());
	cout << endl << "非递归求得深度：";
	cout << test.CaculateTreeDepth2(test.getRoot());
	//统计二叉树度为1的节点个数
	cout << endl << "递归求得度为1的节点个数：";
	cout << test.CaculateAlone1(test.getRoot());
	cout << endl << "非递归求得度为1的节点个数：";
	cout << test.CaculateAlone2(test.getRoot());
}

运行效果👇