每日学习-2月18日

知识点：二叉树

中序遍历算法：

void InOrderTraverse(BiTree T)
{
if(T==NULL)
return;
InOrderTraverse(T->lchild);
printf("%c",T->data);
InOrderTraverse(T->rchild);
}

算法过程：

(1)调用InOrderTraverse(T)，T的根结点不为null，于是调用InOrderTraverse(T->lchild);访问结点B。当前指针不为null，继续调用InOrderTraverse(T->lchild);访问结点D。不为null，继续调用InOrderTraverse(T->lchild);访问结点H。继续调用 InOrderTraverse(T->lchild);访问结点H的左孩子，发现当前指针为null，于是返回。打印当前结点H,如下图所示。

+

(2)然后调用InOrderTraverse(T->rchild);访问结点H的右孩子K，因结点K无左孩子，所以打印K，如下图所示。

(3)因为结点K没有右孩子，所以返回。打印结点H，函数执行完毕，返回。打印字母D，如下图所示。

(4)结点D无右孩子，此函数执行完毕，返回。打印字母B，如下图所示

(5)调用InOrderTraverse(T->rchild);访问结点B的右孩子E，因结点E无左孩子，所以打印E，如下图所示。

(6)结点E无右孩子，返回。结点B的递归函数执行完毕，返回到了最初我们调用 InOrderTraverse的地方，打印字母A，如下图所示。

(7)再调用InOrderTraverse(T->rchild);访问结点A的右孩子C，再递归访问结点C的左孩子F，结点F的左孩子I。因为I无左孩子，打印I，之后分别打印F、C、G、J。步骤省略。