1.树的有关定义和术语
1.术语
1.树(tree):
树是n(n≥0)个结点的有限集T,
当n=0时,T为空树;
当n>0时,
(1)有且仅有一个称为T的根的结点,
(2)当n>1时,余下的结点分为m...Left ) AddQ( Q, T->Left );
if ( T->Right ) AddQ( Q, T->Right );
}
}
//source:ZJU
3.中序遍历的非递归实现...思路就是先找到最左的结点,把经过的根结点都保存了,后来左子树遍历完了就找上面根结点的右子树,再把右子树看成个树遍历,遍历完了就返回上一级(退栈),相当于更大的左子树访问完了
后面就不截图了
4.先序遍历的非递归实现...一样的,只不过不同的是,这里入栈就输出
5.后序遍历的非递归实现
注意,由于后序遍历需要遍历一遍左子树,在遍历一遍右子树,所以说保存根结点是十分必要的,所以说这里退栈就不会真退,仅仅是访问而已,如果右子树能能和之前访问过的结点匹配的话...左子树存进栈里
弹出根结点,如果结点有左孩子话,tag为0,没有的话记为1,注意保存一个pre,保存序列上一个结点的内容,总之很抽象,需要好好研读
当然了,带个头指针在指向二叉树本身的操作也是被允许的
这下非递归的遍历就很方便了