一、二叉树遍历
这里不细说原理了，如果不懂原理，赶紧去找Googe Baidu吧！别让他们等太久了 🏃！ 接下来直接上代码了 GitHub
二、Code
typedef struct BinaryNode{
char value;
struct BinaryNode *lChild;
struct BinaryNode *rChild;
}BinaryNode,*BinaryTree;
1.前序遍历
//前序遍历
//递归实现
void PreorderRecursionTraversal(BinaryTree T){
if (NULL != T) {
printf("%c ",T->value);
PreorderRecursionTraversal(T->lChild);
PreorderRecursionTraversal(T->rChild);
}
}
//非递归实现
void PreorderTraversal(BinaryTree T){
std::stack<BinaryTree> stack;
BinaryTree p=T;
while (NULL!=p || !stack.empty()) {
if (NULL != p) {
stack.push(p);
printf("%c ",p->value);
p=p->lChild;
}else{
p=stack.top();
stack.pop();
p=p->rChild;
}
}
}
2.中序遍历
//中序遍历
//递归实现
void InorderRecursionTraversal(BinaryTree T){
if (NULL != T) {
InorderRecursionTraversal(T->lChild);
printf("%c ",T->value);
InorderRecursionTraversal(T->rChild);
}
}
//非递归实现
void InorderTraversal(BinaryTree T){
std::stack<BinaryTree> stack;
BinaryTree p=T;
while (NULL!=p || !stack.empty()) {
if (NULL != p) {
stack.push(p);
p=p->lChild;
}else{
p=stack.top();
printf("%c ",p->value);
stack.pop();
p=p->rChild;
}
}
}
3.后序遍历
//后序遍历
//递归实现
void PostorderRecursionTraversal(BinaryTree T){
if (NULL != T) {
PostorderRecursionTraversal(T->lChild);
PostorderRecursionTraversal(T->rChild);
printf("%c ",T->value);
}
}
//非递归实现(完全想不到思路，参考网上的)
typedef struct BinaryAuxiliaryNode{
BinaryNode *node;
char flag;
}BinaryAuxiliaryNode,*BinaryAuxiliaryTree;
void PostorderTraversal(BinaryTree T){
std::stack<BinaryAuxiliaryTree> stack;
BinaryTree p=T;
BinaryAuxiliaryTree aTree;
while (NULL!=p || !stack.empty()) {
//遍历左子树
while (NULL != p) {
aTree=(BinaryAuxiliaryTree)malloc(sizeof(BinaryAuxiliaryNode));
aTree->node=p;
//访问过左子树
aTree->flag='L';
stack.push(aTree);
p=p->lChild;
}
//左右子树访问完毕，访问根结点
while (!stack.empty() && stack.top()->flag=='R') {
aTree=stack.top();
stack.pop();
printf("%c ",aTree->node->value);
}
//遍历右子树
if (!stack.empty()) {
aTree=stack.top();
//访问过右子树
aTree->flag='R';
p=aTree->node;
p=p->rChild;
}
}
}
三、测试
测试
四、总结
- 其实二叉树的遍历，只有后续遍历的非递归实现复杂一些，其他的实现代码都很简洁。
- 如果初学二叉树，可以拿出笔纸一步一步模拟代码的执行流程，写出遍历结果。
- 还有一点想提的就是要学会运用辅助空间来解决问题，当然根据实际情况也有不同，比如程序由于某些因素限制（比如内存...），无法使用辅助空间
