二叉树遍历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 两种遍历序列确定一棵二叉树

TIM截图20200203170941

两种遍历序列中必须要有一个是中序,不然前序后续无法分清楚如下情况

TIM截图20200203171140