计算机考研专业课复习科目包括数据结构、操作系统、计算机组成原理、计算机网络四门课程。其中数据结构这一科目兼具理论与实践，要求同学们在复习过程中不仅要对教材的基本概念进行记忆，同时还要结合知识点掌握相应的实际操作知识。为帮助同学们在计算机专业课复习上卓有成效，中公考研将为同学们整理全面的考点梳理，今天为大家带来的是数据结构的相关内容，请同学们适当参考，结合自身实际在全面复习的基础上进行重点理解记忆。

　　1.前序遍历二叉树的非递归算法

　　算法思路：设一存放结点指针的栈S。从根开始，每访问一结点后，按前序规则走左子树，但若该结点右子树存在，则右子指针进栈，以便以后能正确地遍历相应放回到该右子树上访问。

　　算法描述: void Preoder-1(BTptr T) //前序非递归遍历二叉树T//

　　{ BTptr p;stacktype s;

　　Clearstack(s);

　　push(s,T); //置栈S为空、根指针T进栈//

　　while (!Emptystack(s) )

　　{ p=pop(s); //出栈,栈顶=>P//

　　while (p)

　　{

　　visit (p); //访问p结点//

　　if (p–>Rchild) push(s,p–>Rchild); //右子存在时,进栈//

　　p=p–>Lchild;

　　} //向左走//

　　}

　　}

　　说明：内部循环是从P结点出发一直走到最左，走的过程中保存了每一个右子树的地址，(因为右子树还没有被访问)而且是先进后出的，即先保存的比后保存的更先被用作返回地址，所以是用栈。外循环正好是当内部循环不下去的时候，退一栈的情形。即换成他的右子树

　　2.中序遍历二叉树的非递归算法

　　算法思路：同前序遍历,栈S存放结点指针。对每棵子树(开始是整棵二叉树)，沿左找到该子树在中序下的第一结点(但寻找路径上的每个结点指针要进栈)，访问之;然后遍历该结点的右子树，又寻找该子树在中序下的第一结点，..….直到栈S空为止。

　　算法描述: void Inorder-1 (BTptr T) // 中序非递归遍历二叉树T//

　　{ BTptr p; stacktype s;

　　Clearstack(s);

　　push (s,T); //置栈S空、根指针进栈//

　　while (!Emptystack(s))

　　{

　　while ((p=Getstop (s))&& p) // 取栈顶且栈顶存在时//

　　push(s,p->lchild); //p之左子指针进栈//

　　p=pop(s); //去掉最后的空指针//

　　if (!Emptystack (s))

　　{ p=pop(s); //取当前访问结点的指针=>P//

　　visit(p); //访问P结点//

　　push(s,p-> Rchild); //遍历P之右子树//

　　}

　　}

　　}