第6章-6.3-遍历二叉树（开放存取权限）

经典数据结构“抽象数据类型”—二叉树（使用二叉链表表示），理解起来有点难，用起来也难，颇有“DLDU”之称

二叉树:单节点分支不超过2

操作前提之概念1–顺序遍历、中序遍历、后序遍历

1.顺序遍历

• 访问根节点
• 先序遍历左子树
• 先序遍历右子树

注意：这里的理解“概念”，请务必读懂，何为L-D-R

1.1—访问根节点A

1.2—2，4，5，8，9，10为左子树，且3，6，7为右子树，左子树优先

1.3—访问根节点B

1.4—4，8，9为左子树，5，10为右子树，左子树优先

1.5—访问根节点D

1.6—8为左子树，9为右子树，左子树优先

……（依此规律）

先序遍历：A\B\D\H\I\E\J\C\F\G

2.中序遍历

• 中序遍历左子树
• 访问根节点
• 中序遍历右子树

2.1—2，4，5，8，9，10为左子树，1为根节点，3，6，7为右子树

2.2—（左子树1，A，右子树1）

2.3—左子树1的左子树为4，8，9，根节点为B，右子树为5，10

2.4—（左子树2，B，右子树2，A，右子树1）

2.5—左子树2的左子树为H，根节点D，右子树I

……

中序遍历结果为：H\D\I\B\J\E\A\F\C\G

PS:中序遍历有个快速的方式，你直接将二叉树横放（掰开即可）🤣

3.后续遍历

• 后续遍历左子树
• 后续遍历右子树
• 访问根节点

注意优先级，仿照1、2就可以知道如何实现后序遍历

后序遍历：H\I\D\J\E\B\F\G\C\A

能遍历？—能够实现创建、预览修改等诸多操作

编码（Coding C++ L）

1.创建（先序顺序创建）{递归算法在二叉树操作中的重要作用}

Status CreateBiTree(BiTree& T)
{
	TElemType ch;
	cin >> ch;
	if (ch == '#')
	{
		T = NULL;
	}
	else
	{
		if (!(T = (BiTree)malloc(sizeof(BiTNode))))
		{
			exit(OVERFLOW);
		}
		T->data = ch;
		CreateBiTree(T->lchild);
		CreateBiTree(T->rchild);
	}
	return OK;
}

仔细品味先序的规则就能理解，此外，注意，递归操作的连带、嵌套、回退性质等，对于实现创建二叉树，妙不可言！

注意程序性质，‘#’为空指针—{null-pointer}

输入时，请务必注意分析树的结构，再规范输入！

输入：A\B\#\D\#\#\C\E\#\#\F\#\#

2.先序遍历、中序、后序

2.1先序（以此为主，中序、后序、代码微调整）

Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
{
	if (T)
	{
		Visit(T->data);
		PreOrderTraverse(T->lchild, Visit);
		PreOrderTraverse(T->rchild, Visit);
	}
	return OK;
}

函数指针，务必注意使用，实际上，函数指针能很大程度上加强程序设计的高效性，以及简化程序逻辑

中序、后序遍历—改动一下程序的运行逻辑即可：

调整这三个语句的位置即可，😀，递归的强大性质，如何，体验的淋漓尽致，如果是其它逻辑，需要不少代码！

3.校验树—（very useful method）

如果你想检验一棵树，是否正确的建立了，那么，这个绝对适合，查看“二叉树”内部任何一个位置的Data，方便，暴躁，耐操

Status Especially_End(BiTree T, TElemType& e)
{
	BiTree p;
	p = T->lchild;
	e = p->data;
	return OK;
}

“森林”了解一下🤣