数据结构-前序，中序后续序历算法（c语言）

喜欢ヅ旅行 2022-05-26 10:20 159阅读 0赞

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    //二叉链表示法
    typedef struct BiTNode
    {
    	int data;//数据域
    	struct BiTNode *lchild;//指针域,存放指向左孩子的指针
    	struct BiTNode *rchild;//指针域,存放指向右孩子的指针
    }BiTNode, *BiTree;
    /*
    
    调用preOrder(t1),t1是根结点,不为NULL,执行printf("%d\t",root->data);打印出来1
    调用preOrder(root->lchild);访问了根节点(t1)的左孩子(t2),不为NULL,执行printf("%d\t",root->data);打印出来2
    递归调用preOrder(root->lchild);访问了t2结点的左孩子(t4),不为NULL,执行printf("%d\t",root->data);打印出来4
    递归调用preOrder(root->lchild);访问了t4结点的左孩子,为NULL,返回此函数,此时递归调用preOrder(root->rchild);访问t4的右孩子,发现还是为NULL，于是函数执行完毕,返回上一级递归的函数
    也就是(打印t2结点函数),调用preOrder(root->rchild);访问t2的右孩子,为NULL,在返回到上一级递归函数(打印根节点t1函数),调用preOrder(root->rchild);访问根节点的右孩子
    也就是t3,不为NULL,故执行printf("%d\t",root->data);打印出来3,递归调用preOrder(root->lchild);访问了t3结点的左孩子(t5),不为NULL,执行printf("%d\t",root->data);打印出来5
    调用preOrder(root->lchild);访问t5的左孩子,为NULL,在返回到上一级递归函数(打印根节点t3函数),
    调用preOrder(root->rchild);访问t3的右孩子,为NULL,在返回到上一级递归函数(打印根节点t1函数)
    之后所以递归函数调用结束,前序遍历算法函数调用结束
    */
    void preOrder(BiTNode *root)
    {
    	if (NULL == root)
    	{
    		return;
    	}
    
    	printf("%d\t",root->data);
    
    	//遍历左子树
    	preOrder(root->lchild);
    
    	//遍历右子树
    	preOrder(root->rchild);
    
    }
    int main()
    {
    	//创建节点
    	BiTNode t1, t2, t3, t4, t5;
    	memset(&t1,0,sizeof(BiTNode));
    	memset(&t2, 0, sizeof(BiTNode));
    	memset(&t3, 0, sizeof(BiTNode));
    	memset(&t4, 0, sizeof(BiTNode));
    	memset(&t5, 0, sizeof(BiTNode));
    
    	t1.data = 1;
    	t2.data = 2;
    	t3.data = 3;
    	t4.data = 4;
    	t5.data = 5;
    
    	//建立联系
    	t1.lchild = &t2;
    	t1.rchild = &t3;
    	t2.lchild = &t4;
    	t3.lchild = &t5;
    
    	//树的遍历
    	//前序遍历算法
    	printf("preOrder\n");
    	preOrder(&t1);
    
    	system("pause");
    	return 0;
    }

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    //二叉链表示法
    typedef struct BiTNode
    {
    	char data;//数据域
    	struct BiTNode *lchild;//指针域,存放指向左孩子的指针
    	struct BiTNode *rchild;//指针域,存放指向右孩子的指针
    }BiTNode, *BiTree;
    /*
    
    调用preOrder(t1),t1是根结点,不为NULL,执行printf("%d\t",root->data);打印出来1
    调用preOrder(root->lchild);访问了根节点(t1)的左孩子(t2),不为NULL,执行printf("%d\t",root->data);打印出来2
    递归调用preOrder(root->lchild);访问了t2结点的左孩子(t4),不为NULL,执行printf("%d\t",root->data);打印出来4
    递归调用preOrder(root->lchild);访问了t4结点的左孩子,为NULL,返回此函数,此时递归调用preOrder(root->rchild);访问t4的右孩子,发现还是为NULL，于是函数执行完毕,返回上一级递归的函数
    也就是(打印t2结点函数),调用preOrder(root->rchild);访问t2的右孩子,为NULL,在返回到上一级递归函数(打印根节点t1函数),调用preOrder(root->rchild);访问根节点的右孩子
    也就是t3,不为NULL,故执行printf("%d\t",root->data);打印出来3,递归调用preOrder(root->lchild);访问了t3结点的左孩子(t5),不为NULL,执行printf("%d\t",root->data);打印出来5
    调用preOrder(root->lchild);访问t5的左孩子,为NULL,在返回到上一级递归函数(打印根节点t3函数),
    调用preOrder(root->rchild);访问t3的右孩子,为NULL,在返回到上一级递归函数(打印根节点t1函数)
    之后所以递归函数调用结束,前序遍历算法函数调用结束
    */
    void preOrder(BiTNode *root)
    {
    	if (NULL == root)
    	{
    		return;
    	}
    
    	printf("%c\t",root->data);
    
    	//遍历左子树
    	preOrder(root->lchild);
    
    	//遍历右子树
    	preOrder(root->rchild);
    
    }
    /*
    中序遍历算法
    调用inOrder(A),根节点不为NULL,于是调用inOrder(root->lchild);继续调用inOrder(B),访问B,当前指针不为NULL,
    继续调用inOrder(D),不为NULL,继续调用inOrder(root->lchild);访问H,H不为NULL,继续调用inOrder(root->lchild),H无左孩子,为空,返回上一级递归函数中,执行打印函数	printf("%c\t", root->data);得到H
    接着调用inOrder(root->rchild);访问H的右孩子K，发现不为NUL,因为K无左孩子,执行完inOrder(root->lchild);直接执行printf("%c\t", root->data);打印K
    因为K无右孩子,所以返回,直接返回到调用函数到字母D,打印D,继续调用inOrder(root->rchild);但是D无右孩子，返回上一级递归函数B,打印B,
    之后调用inOrder(root->rchild);访问E,不为NULL,执行完inOrder(root->lchild);因E无左孩子,直接打印出来E,接着访问E的右孩子,发现没有,则返回到根节点位置
    打印A,然后继续调用inOrder(root->rchild);访问C,不为NULL,调用inOrder(root->lchild);访问F,不为NULL,继续inOrder(root->lchild);访问I
    I不为NULL,继续调用inOrder(root->lchild);因为I没有左孩子,返回到I,打印I,继续调用inOrder(root->rchild);发现I无右孩子
    返回到F,打印F,F无右孩子,返回到C,打印C,接着调用inOrder(root->rchild);访问G,G不为NULL,调用inOrder(root->lchild);因G无左孩子,打印G,继续调用inOrder(root->rchild);访问J,因为J无左孩子，直接打印J,无右孩子,返回,递归调用结束
    
    
    */
    //先左子树 然后根 最后右子树
    void inOrder(BiTNode *root)
    {
    	if (NULL == root)
    	{
    		return;
    	}
    
    
    	//遍历左子树
    	inOrder(root->lchild);
    
    	printf("%c\t", root->data);
    
    	//遍历右子树
    	inOrder(root->rchild);
    
    }
    
    //先左子树-右子树-根
    void postOrder(BiTNode *root)
    {
    	if (NULL == root)
    	{
    		return;
    	}
    
    
    	//遍历左子树
    	postOrder(root->lchild);
    
    
    
    	//遍历右子树
    	postOrder(root->rchild);
    
    	printf("%c\t", root->data);
    }
    int main()
    {
    	//创建节点
    	BiTNode A, B, C, D, E,F,G,H,I,J,K;
    	memset(&A,0,sizeof(BiTNode));
    	memset(&B, 0, sizeof(BiTNode));
    	memset(&C, 0, sizeof(BiTNode));
    	memset(&D, 0, sizeof(BiTNode));
    	memset(&E, 0, sizeof(BiTNode));
    	memset(&F, 0, sizeof(BiTNode));
    	memset(&G, 0, sizeof(BiTNode));
    	memset(&H, 0, sizeof(BiTNode));
    	memset(&I, 0, sizeof(BiTNode));
    	memset(&J, 0, sizeof(BiTNode));
    	memset(&K, 0, sizeof(BiTNode));
    
    	A.data = 'A';
    	B.data = 'B';
    	C.data = 'C';
    	D.data = 'D';
    	E.data = 'E';
    	F.data = 'F';
    	G.data = 'G';
    	H.data = 'H';
    	I.data = 'I';
    	J.data = 'J';
    	K.data = 'K';
    
    	//建立联系
    	A.lchild = &B;
    	A.rchild = &C;
    	B.lchild = &D;
    	B.rchild = &E;
    	D.lchild = &H;
    	H.rchild = &K;
    
    	C.lchild = &F;
    	C.rchild = &G;
    	F.lchild = &I;
    	G.rchild = &J;
    
    
    	//树的遍历
    	//前序遍历算法
    	printf("前序遍历算法\n");
    	preOrder(&A);
    
    	printf("\n中序遍历算法\n");
    	inOrder(&A);
    
    	printf("\n后遍历算法\n");
    	postOrder(&A);
    
    	system("pause");
    	return 0;

\}

口诀：  
DLR—先序遍历，即先根再左再右  
  
LDR—中序遍历，即先左再根再右

LRD—后序遍历，即先左再右再根

发表评论取消回复

表情：

评论列表（有 0 条评论，159人围观）

还没有评论，来说两句吧...

相关阅读

相关【数据结构C/C++】根据前序中序和中序后续遍历结果生成二叉树

文章目录前序和中序遍历结果生成二叉树中序遍历和后续遍历构造二叉树 408考研各数据结构C/C++代码（Continually updating）

梦里梦外;/ 2024年03月01日 08:35/ 0 赞/ 4 阅读

相关 C语言二叉树前序、中序、后序、层序遍历

知识点整理： 1、前序遍历：根-左-右 2、中序遍历：左-根-右 3、后序遍历：左-右-根 4、层序遍历：从树根出发一层一层从左往右遍历代码展示： inc

一时失言乱红尘/ 2023年10月11日 17:40/ 0 赞/ 69 阅读

相关 Morris前序、中序、后序遍历

Morris前序遍历算法过程 > 1.如果cur无左孩子，cur向右移动（cur=cur.right） > 2.如果cur有左孩子，找到cur左子树上最右的节

刺骨的言语ヽ痛彻心扉/ 2023年10月06日 21:36/ 0 赞/ 77 阅读

相关二叉树前序，中序，后续，层次遍历统一的算法

public class TreeNode { //二叉树节点定义 int val; TreeNode left;

桃扇骨/ 2023年03月13日 05:15/ 0 赞/ 20 阅读

相关算法笔记_面试题_4.树的遍历(前序/中序/后续遍历）

目录题目解答递归的方法迭代的方法-前序遍历迭代的方法-中序遍历迭代方法-后续遍历最优解之一 -------------------- 题目

ゝ一纸荒年。/ 2023年02月20日 04:50/ 0 赞/ 17 阅读

相关数据结构中序后序求前序

include <stdio.h> include <stdlib.h> include <string.h> void pr

深藏阁楼爱情的钟/ 2022年09月19日 01:53/ 0 赞/ 177 阅读

相关数据结构前序中序求后序

include <stdio.h> include <stdlib.h> include <string.h> void Po

落日映苍穹つ/ 2022年09月19日 01:53/ 0 赞/ 163 阅读

相关输入前序遍历、中序遍历输出后续遍历

//二叉树输入前序遍历和中序遍历输出后续遍历 // by nby \include<iostream> using namespace std; void

太过爱你忘了你带给我的痛/ 2022年08月07日 08:42/ 0 赞/ 213 阅读

相关数据结构-前序，中序后续序历算法（c语言）

include <stdio.h> include <stdlib.h> include <string.h> //二叉链表示法

喜欢ヅ旅行/ 2022年05月26日 10:20/ 0 赞/ 160 阅读

相关 C++数据结构--二叉树的前序遍历，中序遍历，后序遍历

1.二叉树的抽象模型和相应的node对象表示 ![20130801080518843][] 2.遍历二叉树 Example：对下图给出的二叉树进行

旧城等待，/ 2021年11月26日 23:52/ 0 赞/ 356 阅读