二叉树的非递归后序遍历

二叉树的非递归后序遍历

文章目录

• 二叉树的非递归后序遍历
• 前言
• 一、树和队列的结构和初始化
• 二、后序遍历
• • 1.获取栈顶的节点
  • 2.后序遍历函数
  • 3.测试代码
• 总结

前言

二叉树的非递归后序遍历

一、树和队列的结构和初始化

typedef struct TreeNode									//树的结构
{char data;											//数据域char类型struct TreeNode* Lchild;							//左孩子struct TreeNode* Rchild;							//右孩子int flag;
}TreeNode;typedef struct stackNode								//队列的结构
{TreeNode* data;										//data使用指针更好指向树的节点struct stackNode* next;								//next下一指针域
}stackNode;void creatTree(TreeNode** node, char* data, int* index)
{char temp;temp = data[*index];*index += 1;if (temp == '#'){*node = NULL;}else{*node = (TreeNode*)malloc(sizeof(TreeNode));(*node)->data = temp;(*node)->flag = 0;creatTree(&((*node)->Lchild), data, index);creatTree(&((*node)->Rchild), data, index);}
}stackNode* initStack(void)
{stackNode* stack = (stackNode*)malloc(sizeof(stackNode));	//开辟对stack空间stack->data = NULL;											//data指向的节点为NULLstack->next = NULL;											//next下一指针域也是nULLreturn stack;
}

二、后序遍历

1.获取栈顶的节点

代码如下（示例）：

stackNode* getTop(stackNode* stack)
{if (isEmplt(stack)){return NULL;}else{stackNode* node = stack->next;						//进栈前判断不为空，创建node，node指向stack的nextreturn node;}
}

2.后序遍历函数

代码如下（示例）：

void lastOrder(TreeNode* tree)								//后序遍历
{	TreeNode* node = tree;									//node获取treestackNode* stack = initStack();							//初始化队列stackwhile (node || !isEmplt(stack))							//判断node是否为空或队列是否为空{if (node)											//如果node不为空{push(node, stack);								//入栈node = node->Lchild;							//node指向node的左孩子}else{TreeNode* top = getTop(stack)->data;			//初始化top节点获取栈顶部data指向的树的节点位置if (top->Rchild && top->Rchild->flag == 0)		//如果此时的top节点的右孩子不为空并且top的右孩子节点的状态没有被访问过{top = top->Rchild;							//top指向top的右孩子push(top,stack);							//入栈top = top->Lchild;							//top指向top的左孩子}else{top = pop(stack)->data;						//如果top的右孩子为NULL，则出栈printf("%c", top->data);					//打印出栈节点的datatop->flag = 1;								//并且对此节点的flag值置一}}}
}

3.测试代码

代码如下（示例）：

#include 
#include typedef struct TreeNode									//树的结构
{char data;											//数据域char类型struct TreeNode* Lchild;							//左孩子struct TreeNode* Rchild;							//右孩子int flag;
}TreeNode;typedef struct stackNode								//队列的结构
{TreeNode* data;										//data使用指针更好指向树的节点struct stackNode* next;								//next下一指针域
}stackNode;void creatTree(TreeNode** node, char* data, int* index)
{char temp;temp = data[*index];*index += 1;if (temp == '#'){*node = NULL;}else{*node = (TreeNode*)malloc(sizeof(TreeNode));(*node)->data = temp;(*node)->flag = 0;creatTree(&((*node)->Lchild), data, index);creatTree(&((*node)->Rchild), data, index);}
}stackNode* initStack(void)
{stackNode* stack = (stackNode*)malloc(sizeof(stackNode));	//开辟对stack空间stack->data = NULL;											//data指向的节点为NULLstack->next = NULL;											//next下一指针域也是nULLreturn stack;
}void push(TreeNode* treedata, stackNode* stack)
{stackNode* node = (stackNode*)malloc(sizeof(stackNode));	//开创一个node节点node->data = treedata;										//队列node的data指针指向树的节点node->next = stack->next;									//node的next指向stack的nextstack->next = node;											//stack的next指向node
}int isEmplt(stackNode* stack)
{if (stack->next == NULL){return 1;}else{return 0;}
}stackNode* pop(stackNode* stack)
{if (isEmplt(stack)){return NULL;}else{stackNode* node = stack->next;						//进栈前判断不为空，创建node，node指向stack的nextstack->next = node->next;							//stack的next指向node的next，即指向node的next的nextreturn node;}
}stackNode* getTop(stackNode* stack)
{if (isEmplt(stack)){return NULL;}else{stackNode* node = stack->next;						//进栈前判断不为空，创建node，node指向stack的nextreturn node;}
}void lastOrder(TreeNode* tree)								//后序遍历
{	TreeNode* node = tree;									//node获取treestackNode* stack = initStack();							//初始化队列stackwhile (node || !isEmplt(stack))							//判断node是否为空或队列是否为空{if (node)											//如果node不为空{push(node, stack);								//入栈node = node->Lchild;							//node指向node的左孩子}else{TreeNode* top = getTop(stack)->data;			//初始化top节点获取栈顶部data指向的树的节点位置if (top->Rchild && top->Rchild->flag == 0)		//如果此时的top节点的右孩子不为空并且top的右孩子节点的状态没有被访问过{top = top->Rchild;							//top指向top的右孩子push(top,stack);							//入栈top = top->Lchild;							//top指向top的左孩子}else{top = pop(stack)->data;						//如果top的右孩子为NULL，则出栈printf("%c", top->data);					//打印出栈节点的datatop->flag = 1;								//并且对此节点的flag值置一}}}
}void main(void)
{char data[] = "ABD#F##E##C##";int index = 0;TreeNode* tree;creatTree(&tree, data, &index);lastOrder(tree);printf("\n");
}

总结

上述若有错误麻烦请指出，谢谢啦。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！