1.如何转变，人的思考由计算机模仿
2.树中儿子-兄弟表示法(2叉树)
3.二叉树的遍历 （递归法和栈循环）
下面是2个循环的中序遍历
一：
中序遍历非递归遍历算法
遇到一个结点，就把它压栈，并去遍历它的左子树;
当左子树遍历结束后，从栈顶弹出这个结点并访问它;
然后按其右指针再去中序遍历该结点的右子树。
void InOrderTraversal( BinTree BT )
{
BinTree T=BT;
Stack S = CreatStack( MaxSize ); /*创建并初始化堆栈S*/
while( T || !IsEmpty(S) ){
while(T){ /*一直向左并将沿途结点压入堆栈*/
Push(S,T);
T = T->Left;
}
if(!IsEmpty(S)){
T = Pop(S); /*结点弹出堆栈*/
printf(“%5d”, T->Data); /*(访问)打印结点*/
T = T->Right; /*转向右子树*/
}
}
}
二：
void InOrderTraversal( BinTree BT )
{
BinTree T=BT;
Stack S = CreatStack( MaxSize ); /*创建并初始化堆栈S*/
while(T || !IsEmpty(S))
{
if(T && T.left)
{
// 如果有左节点就保存
Push(S,T)
T = T.left;
}
else
{
if(T == nil)
{
T = Pop(S); /*结点弹出堆栈*/
}
// 打印自己，并遍历右节点
printf(“%5d”, T->Data); /*(访问)打印结点*/
if(T.right)
{
T = T.right;
}
else
{
T = nil;
}
}
}
}
区别：
- 第一种是整体的思想，循环的点在print，打出一个点；第二种和递归类似，重点在单个节点的处理
2.第一种叶节点也入栈，第二种叶节点没有入栈（栈数量层级少1）
