B树

class BTreeNode { public: BTreeNode(int i) : lchild(NULL), rchild(NULL) {} public: int value; BTreeNode *lchild; BTreeNode *rchild; };

递归遍历

递归式遍历的前序、中序、后序，总体结构一致，只在于处理方法调用的时机。 记得检查NULL就好。

void preorder_rec(BTreeNode *node) { if (node) { // do something ... // 前序，在左右child之前处理 preorder_rec(node->lchild); preorder_rec(node->rchild); } } void inorder_rec(BTreeNode *node) { if (node) { inorder_rec(node->lchild); // do something ... // 中序，在lchild之后rchild之前处理 inorder_rec(node->rchild); } } void postorder_rec(BTreeNode *node) { if (node) { postorder_rec(node->lchild); postorder_rec(node->rchild); // do something ... // 后序，在左右child之后处理 } }

非递归遍历

前序、中序

这两者的结构类似，区别只在于对当前node处理的时机

void preorder(BTreeNode *node) { stack<BTreeNode *> st; // 循环条件：1. 初始node不为空；OR 2. stack中还有未遍历到的node while (node || !st.empty()) { while (node) { // do something ... st.push(node); node = node->lchild; } node = st.top(); st.pop(); node = node->rchild; } } void inorder(BTreeNode *node) { stack<BTreeNode *> st; // 循环条件：1. 初始node不为空；OR 2. stack中还有未遍历到的node while (node || !st.empty()) { while (node) { st.push(node); node = node->lchild; } node = st.top(); st.pop(); // do something ... node = node->rchild; } }

后序

说明

非递归后序遍历中，只在stack中保存节点指针是不够的，否则在从stack中取到某node时，无法分辨是“遍历完lchild后出栈的”还是“遍历完rchild后出栈的”。

即需要用额外的数据对该节点的“访问状态”进行编码，这就是为什么非递归后序遍历处理起来较为复杂的原因。

void postorder(BTreeNode *node) { stack<BTreeNode *> st; bool visited[TREE_NODE_MAX_NUM]; // 入栈root到最左leaf上的所有node while (node) { st.push(node); visited[st.size()] = false; node = node->lchild; } while (!st.empty()) { // 取栈顶node，此时该node的lchild已遍历完毕，待遍历rchild node = st.top(); // 第二个条件用来区分是lchild还是rchild遍历完回到的node while (node->rchild && visited[st.size()] == false) { node = node->rchild; visited[st.size()] = true; // 标记该node已遍历过rchild while (node) { // 入栈最左线的所有node st.push(node); visited[st.size()] = false; node = node->lchild; } node = st.top(); // 开始遍历该node的rchild } node = st.top(); // 此时node的rchild已遍历完毕 st.pop(); // do something ... } }

层序

说明

层序遍历用非递归的方式实现较为简单，使用queue依次保存左右child即可。 queue中的所有元素都处在同一层。

void levelorder(BTreeNode *node) { queue<BTreeNode *> q; if (node) q.push(node); while (!q.empty()) { node = q.front(); q.pop(); // do something ... if (node->lchild) q.push(node->lchild); if (node->rchild) q.push(node->rchild); } }

参考

http://biaobiaoqi.github.io/blog/2013/04/27/travsal-binary-tree/