二叉树（Binary Tree）

本文主要总结了数据结构关于二叉树的相关知识内容，其中包括定义、过程算法和完整实现代码。

二叉树（BiTree）

定义

二叉树的遍历(traversing binary tree)是指从根结点出发，按照某种次序一次访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。

过程及其算法

先序遍历：根左右

/* 先序遍历 */
void FirstOrder(BiTree T)
{
	if (T == NULL) {
		return;
	}
	cout << T->data;  // 进行输出结点数据的操作
	FirstOrder(T->lchild);  // 先序遍历左子树
	FirstOrder(T->rchild);  // 先序遍历右子树
}

中序遍历：左根右

// 初始条件：二叉树T存在
// 操作结果：中序递归遍历T，依次输出值
/* 中序遍历 */
void MidOrder(BiTree T)
{
	if (T == NULL) {
		return;
	}
	
	MidOrder(T->lchild);  // 中序遍历左子树
	cout << T->data;  // 进行输出结点数据的操作
	MidOrder(T->rchild);  // 中序遍历右子树
}

后序遍历：左右根

// 初始条件：二叉树T存在
// 操作结果：后续递归遍历T
/* 后序遍历 */
void EndOrder(BiTree T)
{
	if (T == NULL) {
		return;
	}
	EndOrder(T->lchild);  // 后序遍历左子树
	EndOrder(T->rchild);  // 后序遍历右子树
	cout << T->data;  // 进行输出结点数据的操作
}

拓展：求树的深度

int treeDepth(BiTree T) {
	if (T == NULL) {
		return 0;
	}
	else
	{
		int left = treeDepth(T->lchild);
		int right = treeDepth(T->rchild);
		if (left > right)//如果左边不大于右边就加一
		{
			return left + 1;
		}
		else
		{
			return right + 1;
		}
	}
}

层序遍历：（借助队列）

算法思想：

• 初始化一个辅助队列
• 根节点入队
• 若队列非空，则对头结点出队访问该节点，并将其左、右孩子插入队尾（如果有的话）
• 重复上步直至队列为空

/* 层序遍历 */
void LevelOrder(BiTree T)
{
	LinkQueue Q ;
	InitQueue(Q);
	BiTree p;
	p = new BiTNode;
	Push(Q, T);
	while (!IsEmpty(Q))//判断队列是否为空
	{
		Pop(Q, p);
		cout << p->data;
		if (p->lchild!=NULL)
		{
			Push(Q,p->lchild);
		}
		if (p->rchild != NULL)
		{
			Push(Q, p->rchild);
		}
	}
}

完整实现代码

#include<iostream>
#include<string>

using namespace std;

/*
	二叉树的层序遍历
*/

/* 二叉树链式存储 */
typedef struct BiTNode
{
	char data;
	struct BiTNode* lchild, * rchild;
}BiTNode,*BiTree;

/* 链式队列结点 */
typedef struct LinkNode
{
	BiTNode* data;
	struct LinkNode* next;
}LinkNode;

/* 队列头尾结点 */
typedef struct
{
	LinkNode* front,*rear;//队头队尾
}LinkQueue;

/* 按照先序创建树，#代表空 */
void createBiTree(BiTree &T)
{
	char ch;
	cin >> ch;
	if (ch == '#')
	{
		T = NULL;
	}
	else
	{
		T = new BiTNode;
		T->data = ch;
		createBiTree(T->lchild);
		createBiTree(T->rchild);
	}

}
/* 初始化树 */
void InitBiTree(BiTree& T)
{
	T->lchild = NULL;
	T->rchild = NULL;
	T->data = NULL;
}


/* 初始化队列 */
void InitQueue(LinkQueue &L)
{
	L.front = L.rear = new LinkNode;
	L.front->data = NULL;
	L.front->next =  NULL;//front和rear指向同一地址，所以rear就不用初始化了
}

/* 判断队列是否为空 */
int IsEmpty(LinkQueue Q)
{
	if (Q.front == Q.rear)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

//进队列(在队尾插入)
bool Push(LinkQueue& S, BiTree T)
{
	LinkNode* p = new LinkNode;
	p->data = T;
	p->next = NULL;
	S.rear->next = p; //修改后继指针
	S.rear = p;
	return true;
}

//出队列（在队头弹出）头结点的下一个
bool Pop(LinkQueue& S, BiTree& T)
{
	if (IsEmpty(S))
	{
		return false;
	}
	T = S.front->next->data;
	LinkNode* p = S.front->next;
	S.front->next = p->next;
	if (S.rear == p)
	{
		S.rear = S.front;
	}
	delete p;
	return true;
}

/* 先序遍历 */
void FirstOrder(BiTree T)
{
	if (T == NULL) {
		return;
	}
	cout << T->data;  // 进行输出结点数据的操作
	FirstOrder(T->lchild);  // 中序遍历左子树
	FirstOrder(T->rchild);  // 中序遍历右子树
}

/* 中序遍历 */
void MidOrder(BiTree T)
{
	if (T == NULL) {
		return;
	}
	
	MidOrder(T->lchild);  // 中序遍历左子树
	cout << T->data;  // 进行输出结点数据的操作
	MidOrder(T->rchild);  // 中序遍历右子树
}

/* 后序遍历 */
void EndOrder(BiTree T)
{
	if (T == NULL) {
		return;
	}
	EndOrder(T->lchild);  // 后序遍历左子树
	EndOrder(T->rchild);  // 后序遍历右子树
	cout << T->data;  // 进行输出结点数据的操作
}

/* 层序遍历 */
void LevelOrder(BiTree T)
{
	LinkQueue Q ;
	InitQueue(Q);
	BiTree p;
	p = new BiTNode;
	//InitBiTree(p);
	Push(Q, T);
	while (!IsEmpty(Q))
	{
		Pop(Q, p);
		cout << p->data;
		if (p->lchild!=NULL)
		{
			Push(Q,p->lchild);
		}
		if (p->rchild != NULL)
		{
			Push(Q, p->rchild);
		}
	}
}
/* 二叉树的深度 */
int treeDepth(BiTree T) {
	if (T == NULL) {
		return 0;
	}
	else
	{
		int left = treeDepth(T->lchild);
		int right = treeDepth(T->rchild);
		if (left > right)//如果左边不大于右边就加一
		{
			return left + 1;
		}
		else
		{
			return right + 1;
		}
	}
}

//主程序入口
int main()
{
	BiTree bt;
	createBiTree(bt);
	cout << "树的深度为："<< treeDepth(bt) << endl;
	cout << "树的先序遍历为：" << endl;
	FirstOrder(bt);
	cout << endl;
	cout << "树的中序遍历为：" << endl;
	MidOrder(bt);
	cout << endl;
	cout << "树的后序遍历为：" << endl;
	EndOrder(bt);
	cout << endl;
	cout<< "树的层次遍历为：" << endl;
	LevelOrder(bt);
	return 1;
}