//非递归后序遍历 void postOrder2(BiTree& T){ SqStack Stack; initSqStack(Stack); BiTNode * p = T,*r =NULL; while (p!=NULL||!isEmpty(Stack)){ if(p!=NULL){ push(Stack,p); p = p->lchild; } else{ getStackTop(Stack,p); if(p->rchild!=NULL&&p->rchild!=r){ p = p->rchild; } else{ //访问结点 pop(Stack,p); printf("%d ",p->data); r = p; p=NULL; } } } }算法时间复杂度和空间复杂度

该算法的时间复杂度为 $O(n)$，其中 $n$ 为二叉树中的结点数。

该算法的空间复杂度为 $O(h)$，其中 $h$ 为二叉树的高度，即最长路径上的结点数。在最坏情况下，二叉树为单链表，高度为 $n-1$，此时空间复杂度为 $O(n)$。在最好情况下，二叉树为满二叉树，高度为 $\log_2(n+1)$，此时空间复杂度为 $O(\log_2(n+1))$。

相关问题

己知链式二叉树的结点定义如下： typedef char ElemType; typedef struct BitNode { ElemType data; struct BitNode *Ichild,*rchild; }BTNode; 请写出先序、中序、后序遍历的递归算法。void PreOrder(BTNode *T) { } void InOrder(BTNode *t)//中序遍历 } void PostOrder(BTNode *t)//后序遍历

好的，以下是先序、中序、后序遍历的递归算法：

先序遍历：

void PreOrder(BTNode *T) {
if(T) {
printf("%c ", T->data); //先访问根节点
PreOrder(T->Ichild); //递归遍历左子树
PreOrder(T->rchild); //递归遍历右子树
}
}

中序遍历：

void InOrder(BTNode *T) {
if(T) {
InOrder(T->Ichild); //递归遍历左子树
printf("%c ", T->data); //访问根节点
InOrder(T->rchild); //递归遍历右子树
}
}

后序遍历：

void PostOrder(BTNode *T) {
if(T) {
PostOrder(T->Ichild); //递归遍历左子树
PostOrder(T->rchild); //递归遍历右子树
printf("%c ", T->data); //访问根节点
}
}

void creat(BiTree &Tree)//构建二叉树 void PostOrder(BiTree Tree)//输出后缀表达式

好的，我可以为你提供一个C++的实现。

首先，我们需要定义二叉树的节点结构体。

struct TreeNode {
    char val; // 节点的值，这里假设是字符类型
    TreeNode* left; // 左子节点
    TreeNode* right; // 右子节点
    TreeNode(char x) : val(x), left(nullptr), right(nullptr) {}
};

然后，我们可以按照前缀表达式的顺序构建二叉树。

void creat(TreeNode* &Tree) {
    char val;
    cin >> val;
    if (val == '#') { // 如果输入的是 #，表示这个节点是空节点
        Tree = nullptr;
    } else {
        Tree = new TreeNode(val); // 创建一个新的节点
        creat(Tree->left); // 构建左子树
        creat(Tree->right); // 构建右子树
    }
}

最后，我们可以按照后序遍历的顺序输出后缀表达式。

void PostOrder(TreeNode* Tree) {
    if (Tree == nullptr) {
        return;
    }
    PostOrder(Tree->left); // 输出左子树的后缀表达式
    PostOrder(Tree->right); // 输出右子树的后缀表达式
    cout << Tree->val << " "; // 输出根节点的值
}

完整的代码如下：

#include <iostream>
using namespace std;

struct TreeNode {
    char val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char x) : val(x), left(nullptr), right(nullptr) {}
};

void creat(TreeNode* &Tree) {
    char val;
    cin >> val;
    if (val == '#') {
        Tree = nullptr;
    } else {
        Tree = new TreeNode(val);
        creat(Tree->left);
        creat(Tree->right);
    }
}

void PostOrder(TreeNode* Tree) {
    if (Tree == nullptr) {
        return;
    }
    PostOrder(Tree->left);
    PostOrder(Tree->right);
    cout << Tree->val << " ";
}

int main() {
    TreeNode* root;
    creat(root);
    PostOrder(root);
    return 0;
}

当你输入前缀表达式并按回车键后，程序会输出后缀表达式。注意，输入的表达式中操作数必须是单个字符，操作符可以是加减乘除等常见的运算符，但是不支持括号。