二叉树遍历本质是什么?
本质是二维结构转换成一维结构的线性过程。树是二维的,遍历一次数,就是访问每个元素,这是一维。
这篇讲用队列实现层序遍历二叉树,如何用队列实现呢?方法:A入队,出队,A的左右结点入队,循环以方法,可得到层序遍历结查,如下图。
队列实现二叉树层序遍历代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
void LevelOrder(BinTree BT) { if (!BT) return; Queue Q; BinTree T; Q = CreatQueue(MaxSize); //创建变初始化队列 Add(Q,BT); while(!IsEmpty(Q)){ T = Delete(Q); printf("%d ", T->Data); //访问队列中的结点 if (T->Left) Add(Q,T->Left); if (T->Right) Add(Q,T->Right); } } |
如果对对队不是很熟,可以看这篇:链式存储单链如何实现队列 ?? ?顺序存储数组如何实现队列