赞
踩
二叉树后序遍历的实现思想是:
图 1 二叉树
以上图 1 为例,后序遍历的过程如下:
- 从根节点 1 开始,遍历该节点的左子树(以节点 2 为根节点)
- 遍历节点 2 的左子树(以节点 4 为根节点)
- 由于节点 4 既没有左子树,也没有右子树,此时访问该节点中的元素 4,并回退到节点 2 ,遍历节点 2 的右子树(以 5 为根节点)
- 由于节点 5 无左右子树,因此可以访问节点 5 ,并且此时节点 2 的左右子树也遍历完成,因此也可以访问节点 2
- 此时回退到节点 1 ,开始遍历节点 1 的右子树(以节点 3 为根节点)
- 遍历节点 3 的左子树(以节点 6 为根节点)
- 由于节点 6 无左右子树,因此访问节点 6,并回退到节点 3,开始遍历节点 3 的右子树(以节点 7 为根节点)
- 由于节点 7 无左右子树,因此访问节点 7,并且节点 3 的左右子树也遍历完成,可以访问节点 3;节点 1 的左右子树也遍历完成,可以访问节点 1
因此,图 1 中二叉树采用中序遍历得到的序列为:
先谈一下递归实现!!!
- #include <stdio.h>
- #include <stdlib.h>
-
- typedef struct MyBiTNode{
- int data; // 数据域
- struct MyBiTNode *lchild, *rchild; // 左右孩子指针
- } BiTNode;
-
- BiTNode *CreateBiTree(BiTNode *T){
- // 结点 1
- T = (BiTNode*)malloc(sizeof(BiTNode));
- T->data = 1;
- // 结点 2
- T->lchild = (BiTNode*)malloc(sizeof(BiTNode));
- T->lchild->data = 2;
- // 结点 3
- T->rchild = (BiTNode*)malloc(sizeof(BiTNode));
- T->rchild->data = 3;
- // 结点 4
- T->lchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));
- T->lchild->lchild->data = 4;
- T->lchild->lchild->lchild = NULL;
- T->lchild->lchild->rchild = NULL;
- // 结点 5
- T->lchild->rchild = (BiTNode*)malloc(sizeof(BiTNode));
- T->lchild->rchild->data = 5;
- T->lchild->rchild->lchild = NULL;
- T->lchild->rchild->rchild = NULL;
- // 结点 6
- T->rchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));
- T->rchild->lchild->data = 6;
- T->rchild->lchild->lchild = NULL;
- T->rchild->lchild->rchild = NULL;
- // 结点 7
- T->rchild->rchild = (BiTNode*)malloc(sizeof(BiTNode));
- T->rchild->rchild->data = 7;
- T->rchild->rchild->lchild = NULL;
- T->rchild->rchild->rchild = NULL;
- return T;
- }
-
- // 模拟操作结点元素的函数,输出结点本身的数值
- void displayElem(BiTNode* elem){
- printf("%d ", elem->data);
- }
-
- // 后序遍历
- void PostOrderTraverse(BiTNode *T){
- if(T){
- PostOrderTraverse(T->lchild); // 遍历左孩子
- PostOrderTraverse(T->rchild); // 遍历右孩子
- displayElem(T); // 调用操作结点数据的函数方法
- }
- // 如果结点为空,返回上一层
- return;
- }
-
- int main() {
- BiTNode *Tree = NULL; // 结构体指针指向空
- Tree = CreateBiTree(Tree); // 传入结构体指针
- printf("%d\n",Tree->rchild->lchild->data); // 4
-
- PostOrderTraverse(Tree);
- return 0;
- }
再谈一下非递归实现!!!
- #include <stdio.h>
- #include <stdlib.h>
-
- int top = -1; // top变量表示栈顶元素所在位置
-
- typedef struct MyBiTNode{
- int data; // 数据域
- struct MyBiTNode *lchild, *rchild; // 左右孩子指针
- } BiTNode;
-
- BiTNode *CreateBiTree(BiTNode *T){
- // 结点 1
- T = (BiTNode*)malloc(sizeof(BiTNode));
- T->data = 1;
- // 结点 2
- T->lchild = (BiTNode*)malloc(sizeof(BiTNode));
- T->lchild->data = 2;
- // 结点 3
- T->rchild = (BiTNode*)malloc(sizeof(BiTNode));
- T->rchild->data = 3;
- // 结点 4
- T->lchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));
- T->lchild->lchild->data = 4;
- T->lchild->lchild->lchild = NULL;
- T->lchild->lchild->rchild = NULL;
- // 结点 5
- T->lchild->rchild = (BiTNode*)malloc(sizeof(BiTNode));
- T->lchild->rchild->data = 5;
- T->lchild->rchild->lchild = NULL;
- T->lchild->rchild->rchild = NULL;
- // 结点 6
- T->rchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));
- T->rchild->lchild->data = 6;
- T->rchild->lchild->lchild = NULL;
- T->rchild->lchild->rchild = NULL;
- // 结点 7
- T->rchild->rchild = (BiTNode*)malloc(sizeof(BiTNode));
- T->rchild->rchild->data = 7;
- T->rchild->rchild->lchild = NULL;
- T->rchild->rchild->rchild = NULL;
- return T;
- }
-
- // 模拟操作结点元素的函数,输出结点本身的数值
- void displayElem(BiTNode* elem){
- printf("%d ", elem->data);
- }
-
- // 弹栈函数
- void pop(){
- if(top == -1){
- return;
- }
- top--;
- }
-
- // 后序遍历非递归算法
- typedef struct SNode{
- BiTNode *p;
- int tag;
- } SNode;
-
- // 后序遍历使用的进栈函数
- void postpush(SNode *a, SNode sdata){
- a[++top] = sdata;
- }
-
- // 后序遍历函数
- void PostOrderTraverse(BiTNode *Tree){
- SNode a[20];
- BiTNode *p;
- int tag;
- SNode sdata;
- p = Tree; // 根结点
- while(p || top!=-1) {
- while(p){
- sdata.p = p;
- sdata.tag = 0;
- postpush(a, sdata);
- // a[0] = {Tree, 0};a[1] = {Tree->lchild, 0};a[2] = {Tree->lchild->lchild, 0}
- // a[2] = {Tree->lchild->rchild, 0}
- p = p->lchild; // 指向左结点
- }
- sdata = a[top];
- // sadta = a[2] = {Tree->lchild->lchild, 0} -- 4
- // sadta = a[2] = {Tree->lchild->lchild, 1} -- 4
- // sadta = a[1] = {Tree->lchild, 0} -- 2
- // sadta = a[2] = {Tree->lchild->rchild, 0} -- 5
- pop(); // top == 1; top == 1; top == 0; top == 1
-
- p = sdata.p; // Tree->lchild->lchild;Tree->lchild->lchild;Tree->lchild;Tree->lchild->rchild
- tag = sdata.tag; // 0 1 0 0
- if(tag == 0) {
- sdata.p = p; // Tree->lchild->lchild;Tree->lchild
- sdata.tag = 1; // 1 1
- postpush(a, sdata); // a[2] = {Tree->lchild->lchild, 1};a[1] = {Tree->lchild, 1}
- p = p->rchild; // NULL Tree->lchild->rchild
- }else{
- displayElem(p); // 4
- p = NULL;
- }
- }
- }
-
- int main() {
- BiTNode *Tree = NULL; // 结构体指针指向空
- Tree = CreateBiTree(Tree); // 传入结构体指针
- printf("%d\n",Tree->rchild->lchild->data); // 4
-
- PostOrderTraverse(Tree);
- return 0;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。