文章目录

• • 链式二叉树（递归）
  • 顺序二叉树（递归）
  • 链式二叉树（非递归）
  • 顺序二叉树（非递归）

链式二叉树（递归）

#include<iostream>
#include<stack>
#include<queue>
using namespace std;
template<class T>
struct BiNode
{
	T data;
	BiNode<T>* lchild;
	BiNode<T>* rchild;
};
template<class T>
class BiTree
{
private:
	BiNode<T>* root;
	BiNode<T>* Create()
	{
		BiNode<T>* root;
		char ch;
		cin >> ch;
		if (ch == '#')
			return NULL;
		root = new BiNode<T>;
		root->data = ch;
		root->lchild = Create();
		root->rchild = Create();
		return root;
	}
	void PreOrder(BiNode<T>* root)
	{
		if (root == NULL)
			return;
		else
		{
			cout << root->data;
			PreOrder(root->lchild);
			PreOrder(root->rchild);
		}
	}
	void InOrder(BiNode<T>* root)
	{
		if (root == NULL)
			return;
		else
		{
			InOrder(root->lchild);
			cout << root->data;
			InOrder(root->rchild);
		}
	}
	void PostOrder(BiNode<T>* root)
	{
		if (root == NULL)
			return;
		else
		{
			PostOrder(root->lchild);
			PostOrder(root->rchild);
			cout << root->data;
		}
	}
	void LevelOrder(BiNode<T>* root)
	{
		queue<BiNode<T>*>q;
		if (root != NULL)
			q.push(root);
		while (!q.empty())
		{
			root = q.front();
			q.pop();
			cout << root->data;
			if (root->lchild != NULL)
				q.push(root->lchild);
			if (root->rchild != NULL)
				q.push(root->rchild);
		}
	}
	int Count(BiNode<T>* root)
	{
		if (root == NULL)
			return 0;
		return Count(root->lchild) + Count(root->rchild) + 1;
	}
	int LeafCount(BiNode<T>* root)
	{
		if (root == NULL)
			return 0;
		if (root->lchild == NULL && root->rchild == NULL)
			return 1;
		return LeafCount(root->lchild) + LeafCount(root->rchild);
	}
	int Depth(BiNode<T>* root)
	{
		if (root == NULL)
			return 0;
		if (Depth(root->lchild) > Depth(root->rchild))
			return Depth(root->lchild) + 1;
		else
			return Depth(root->rchild) + 1;
	}
	void SwapTree(BiNode<T>* root)
	{
		if (root == NULL)
			return;
		BiNode<T>* temp;
		temp = root->lchild;
		root->lchild = root->rchild;
		root->rchild = temp;
		SwapTree(root->lchild);
		SwapTree(root->rchild);
	}
public:
	BiTree() { root = Create(); }
	~BiTree() {}
	void PreOrder() { PreOrder(root); }
	void InOrder() { InOrder(root); }
	void PostOrder() { PostOrder(root); }
	void LevelOrder() { LevelOrder(root); }
	int Count() { return Count(root); }
	int LeafCount() { return LeafCount(root); }
	int Depth() { return Depth(root); }
	void SwapTree() { SwapTree(root); }
};
int main()
{
	BiTree<char>bt;
	cout << "前序遍历：";
	bt.PreOrder();
	cout << endl;
	cout << "中序遍历：";
	bt.InOrder();
	cout << endl;
	cout << "后序遍历：";
	bt.PostOrder();
	cout << endl;
	cout << "层序遍历：";
	bt.LevelOrder();
	cout << endl;
	cout << "Count=" << bt.Count() << endl;
	cout << "LeafCount=" << bt.LeafCount() << endl;
	cout << "Depth=" << bt.Depth() << endl;
	
	bt.SwapTree();
	cout << "前序遍历：";
	bt.PreOrder();
	cout << endl;
	cout << "中序遍历：";
	bt.InOrder();
	cout << endl;
	cout << "后序遍历：";
	bt.PostOrder();
	cout << endl;
	cout << "层序遍历：";
	bt.LevelOrder();
	cout << endl;
	return 0;
}

顺序二叉树（递归）

链式二叉树（非递归）

顺序二叉树（非递归）