//非递归后序遍历 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); //访问根节点
}
}

6-1 后缀式 分数 30 作者 YJ 单位 西南石油大学 本题要求实现一个函数，输出二叉树表示的表达式的后缀式。输入一个表达式的前缀形式（该表达式二叉树的扩展的先序序列），构造该二叉树，并输出其后序序列即为该表达式的后缀形式。 函数接口定义： void creat(BiTree &Tree)//构建二叉树 void PostOrder(BiTree Tree)//输出后缀表达式 其中 Tree 为用户传入的参数，指向根节点的指针。 裁判测试程序样例： #include<stdio.h> #include<malloc.h> #define len sizeof(struct BiTNode ) typedef struct BiTNode { char data; struct BiTNode *lchild; struct BiTNode *rchild; }BiTNode,*BiTree; void creat(BiTree &Tree);//构建二叉树 void PostOrder(BiTree Tree);//后序输出二叉树 int main() { BiTree Tree; creat(Tree);//创建二叉树 printf("后缀表达式为："); PostOrder(Tree);//后序变量 return 0; } /* 请在这里填写答案 */

下面是creat和PostOrder函数的实现：

void creat(BiTree &Tree)
{
char c;
scanf("%c", &c);
if(c == '#')//如果读入的是#，说明该节点为空
{
Tree = NULL;
}
else
{
Tree = (BiTree)malloc(len);//创建新节点
Tree->data = c;//存储节点数据
creat(Tree->lchild);//递归创建左子树
creat(Tree->rchild);//递归创建右子树
}
}

void PostOrder(BiTree Tree)
{
if(Tree)//如果该节点不为空
{
PostOrder(Tree->lchild);//后序遍历左子树
PostOrder(Tree->rchild);//后序遍历右子树
printf("%c", Tree->data);//输出节点数据
}
}