浙大数据结构mooc知识点总结
数据结构
线性结构
线性表
堆栈
队列
树
树的定义
二叉树及存储结构
n0+n1+n2=0*n0+1*n1+2*n2+1化简得n0=n2+1
二叉树的遍历
后序遍历：对于任一结点P，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，此时该结点出现在栈顶，但是此时不能将其出栈并访问， 因此其右孩子还为被访问。所以接下来按照相同的规则对其右子树进行相同的处理，当访问完其右孩子时，该结点又出现在栈顶，此时可以将其出栈并访问。这样就 保证了正确的访问顺序。可以看出，在这个过程中，每个结点都两次出现在栈顶，只有在第二次出现在栈顶时，才能访问它。因此需要多设置一个变量标识该结点是 否是第一次出现在栈顶。
void postOrder2(BinTree *root) //非递归后序遍历
{
stack<BTNode*> s;
BinTree *p=root;
BTNode *temp;
while(p!=NULL||!s.empty())
{
while(p!=NULL) //沿左子树一直往下搜索，直至出现没有左子树的结点
{
BTNode *btn=(BTNode *)malloc(sizeof(BTNode));
btn->btnode=p;
btn->isFirst=true;
s.push(btn);
p=p->lchild;
}
if(!s.empty())
{
temp=s.top();
s.pop();
if(temp->isFirst==true) //表示是第一次出现在栈顶
{
temp->isFirst=false;
s.push(temp);
p=temp->btnode->rchild;
}
else //第二次出现在栈顶
{
cout<<temp->btnode->data<<" ";
p=NULL;
}
}
}
}
由两种遍历序列确定二叉树，必须要有中序遍历才行。
判别二叉树同构
给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2，则我们称两棵树是“同构”的。
二叉搜索树
平衡二叉树
堆
完全二叉树实现的优先队列
哈夫曼树
并查集
图
如何表示图
图的遍历
最短路径问题
最小生成树MST
拓扑排序
排序
简单排序
稳定性：任意两个相等的数据，排序前后的相对位置不发生改变