二叉树遍历2
二叉树遍历2
0x00 层序遍历
层序遍历是用一个队列
0将根节点进队列
1从队列拿出一个节点,打印该节点,
2将该节点左右节点进队列
3重复1,2步一直到队列空
void traversal(qnode* p){
Queue q=createQueue(100);
AddQ(q,p);
while(!isEmpty(q)){//都为NULL说明队列空
p=Delete(q);
printf("(%d) ",p->data);
if(p->left){
AddQ(q,p->left);
}
if(p->right){
AddQ(q,p->right);
}
}
return;
}
0x01 求二叉树高度
二叉树高度是二叉树的最大层次,最大深度。根据定义用递归的方式求树高 树高=max(左子树高度,右子树高度)+1
0x02 两种遍历序列确定一棵二叉树
两种遍历序列中必须要有一个是中序,不然前序后续无法分清楚如下情况