计算机考研专业课复习科目包括数据结构、操作系统、计算机组成原理、计算机网络四门课程。其中数据结构这一科目兼具理论与实践，要求同学们在复习过程中不仅要对教材的基本概念进行记忆，同时还要结合知识点掌握相应的实际操作知识。为帮助同学们在计算机专业课复习上卓有成效，中公考研将为同学们整理全面的考点梳理，今天为大家带来的是数据结构的相关内容，请同学们适当参考，结合自身实际在全面复习的基础上进行重点理解记忆。
凡是对二叉树中各结点进行一次处理的问题，都可以用遍历算法来完成。
1.利用遍历算法对二叉树中各类结点计数
设二叉树中出度=0、1、2的结点数分别为n0、 n1 和n2 ，初值均为0。
套用遍历算法(前序、中许、后序均可)，扫描到树中某p结点时，若：
if ((p->Lchild==NULL)&&(p->Rchild==NULL))
n0++; //p为叶子//
else if((p->Lchild)&&(p->Rchild))
n2++; //p为出度=2的结点//
else n1++; // p为出度=1的结点//
如：只要把遍历算法在遍历时稍微改变一下。
n0=n1=n2=0;
void preorder( BTptr T) //对当前根结点指针为T的二叉树按前序遍历//
{
if (T) { // visit(T); 访问T所指结点 //
if ((T->Lchild==NULL)&&(T->Rchild==NULL))
n0++; //p为叶子//
else if((T->Lchild)&&(T->Rchild))
n2++; //p为出度=2的结点//
else
n1++; // p为出度=1的结点//
preorder(T–>Lchild); //前序遍历T之左子树//
preorder(T–>Rchild); //前序遍历T之右子树//
}
}
2.前序遍历算法交换二叉树中各结点左、右子树(递归的交换)，对每一个结点都只需要一次访问就够了，所以用遍历算法稍微改一下，把VISIT改成我们要做的事就OK了
void preexchange (BTpfr T)
{
BTptr p;
if(T)
{ p=T->Lchild;T->Lchild=T->Rchild;T->Rchild = p;//交换当前T的左右子树//
preexchage(T->Lchild); //处理左子树//
preexchage(T->Rchild); //处理右子树//
}
}
例题1：一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足( )【南开大学 2000 一、2】
A.所有的结点均无左孩子B.所有的结点均无右孩子C.只有一个叶子结点D.是任意一棵二叉树
前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树，所以本题的A和B均对，单支树的特点是只有一个叶子结点，故C是最合适的，选C。A或B都不全。
例题2：某二叉树的前序序列和后序序列正好相反，则该二叉树一定是()的二叉树。【武汉大学2000二、4】
A.空或只有一个结点 B.任一结点无左子树 C.高度等于其结点数 D.任一结点无右子树
和上题类似的BD都可以但是是单选题就只能选C了
例题3：在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序( )
A.都不相同 B.完全相同 C.先序和中序相同，而与后序不同
D.中序和后序相同，而与先序不同
说明：和前序不一样，这里的栈保存的是根结点的地址(因为中序遍历先访问左子树，而根结点没有被访问到。而前序遍历不一样，他一开始就访问根结点，所以他不保存根结点的地址而是保存右子树的地址，因为右子树还没有被访问。总之，用栈就是为了帮我们保存还没有被访问的地址，以便将来我们能找到返回的地址)
数据结构在计算机学科专业基础综合试卷中占有较高的分值比重，因此是计算机专业课复习的重点科目，中公考研建议考生们在复习过程中能够广泛参考复习资料，同时结合自身的复习情况，找准方法，取得复习的超高效率和良好效果。
