C语言二叉树链表的建立及四种遍历方法
C语言二叉树链表的建立及四种遍历方法
#include
#include
//定义一个二叉树结构
typedef struct binode
{
char data;
struct binode * lchild;
struct binode * rchild;
}BiTree;
//前序遍历递归法建立二叉树算法
BiTree * CreatBiTree()
{
BiTree *T;
char data;
fflush(stdin);
scanf("%c",&data);
if (data=='$'){ //输入$符号则退出
return;
}
if(data=='#')T=NULL;
else
{
T=(BiTree *)malloc(sizeof(BiTree));
T->data=data;
T->lchild=CreatBiTree();
T->rchild=CreatBiTree();
}
return T;
}
//按层遍历递归二叉树算法
void Layer_order(BiTree * TNode,BiTree ** F,BiTree ** R) //二级指针
{
*F=TNode; //将当前节点放入队列首指针所指位置
printf("%c",(*F)->data);
if((*F)->lchild!=NULL)
{
R=R+1;
*R=(*F)->lchild; //节点的左儿子放入队尾
}
if((*F)->rchild!=NULL)
{
R=R+1; //首指针向后移动一格
*R=(*F)->rchild; //节点的右儿子放入队尾
}
if(F!=R)
{
F=F+1;
Layer_order(*F,F,R);//递归
}
}
//前序遍历递归二叉树算法
void PreOrderTraverse(BiTree *T)
{
if(T==NULL)
return;
printf("%c", T->data); //显示结点数据,可以更改为其他对结点操作
PreOrderTraverse(T->lchild); //再先序遍历左子树
PreOrderTraverse(T->rchild); //最后先序遍历右子树
}
//中序遍历递归二叉树算法
void InOrderTraverse(BiTree *T)
{
if(T==NULL)
return;
InOrderTraverse(T->lchild); //中序遍历左子树
printf("%c", T->data); //显示结点数据,可以更改为其他对结点操作
InOrderTraverse(T->rchild); //最后中序遍历右子树
}
//后序遍历递归二叉树的算法
void PostOrderTraverse(BiTree *T)
{
if(T==NULL)
return;
PostOrderTraverse(T->lchild); //先后序遍历左子树
PostOrderTraverse(T->rchild); //再后续遍历右子树
printf("%c", T->data); //显示结点数据,可以更改为其他对结点操作
}
int main()
{
BiTree ** F; //队首指针 指向指针的指针,因为队列数组里的元素全是指针
BiTree ** R; //队尾指针 二级指针
BiTree * Queue[1024];//队列数组
F=Queue;
R=Queue; //开始时队首队尾指针重合
BiTree * root; //在main函数中建立一个二叉树根的指针
root=CreatBiTree(); //创建树
printf("按层遍历二叉树: \n");
Layer_order(root,F,R); //按层遍历树
printf("\n");
printf("前序遍历二叉树: \n");
PreOrderTraverse(root);
printf("\n");
printf("中序遍历二叉树: \n");
InOrderTraverse(root);
printf("\n");
printf("后序遍历二叉树: \n");
PostOrderTraverse(root);
printf("\n");
return 0;
}
二叉树模型图:
程序执行效果:
输出结果完全正确:
C语言二叉树链表的建立及四种遍历方法相关教程
[堆 二叉搜索树] 295. 数据流的中位数(排序法 → 二叉搜索树法
[堆 二叉搜索树] 295. 数据流的中位数(排序法 → 二叉搜索树法(手写BST+查找第k小元素)、大小顶堆法(设计出入堆规则)) [堆 二叉搜索树] 295. 数据流的中位数(排序法 → 二叉搜索树法(手写BST+BST上查找第k小元素)、大小顶堆法(设计出入堆规则)) 2
软件设计师考试 | 第二章 程序设计语言基础知识 | 语言处理程序
软件设计师考试 | 第二章 程序设计语言基础知识 | 语言处理程序基础 文章目录 (一)汇编程序基本原理 1.汇编语言 2.汇编程序 (二)编译程序基本原理 1.编译过程概述 2.文法和语言的形式描述 (1)字母表、字符串、字符串集合及运算 (2)文法和语言的形式描
【C语言】最大公约数
【C语言】最大公约数 vs #include stdio.h #include windows.h #pragma warning(disable:4996) int main(){ int m, n, temp, i; printf(“请输入两个整数\n”); scanf(%d%d\n, m, n);//这里也可以把scanf换成scanf_s,然后删掉上面#pragma warning那一句
剑指offer第34题 二叉树中和为某一值的路径
剑指offer第34题 二叉树中和为某一值的路径 文章目录 问题描述: 解题思路: 代码实现: 复杂度分析: 问题描述: 输入一棵二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。 示
C语言闰年
【C语言】闰年 首先明确闰年的概念: 普通闰年 :公历年份是4的倍数的,且不是100的倍数,为普通闰年(如、就是闰年)。 世纪闰年 :公历年份是整百数的,必须是400的倍数才是世纪闰年(如1900年不是世纪闰年,2000年是世纪闰年)。 也就是说:
Leetcode 530. 二叉搜索树的最小绝对差
Leetcode 530. 二叉搜索树的最小绝对差 本题与 783 https://leetcode-/problems/minimum-distance-between-bst-nodes/ 相同 给你一棵所有节点为非负值的二叉搜索树,请你计算树中任意两节点的差的绝对值的最小值。 思路:利用二叉搜索树的特性,中序遍
算法-10-二叉树LeetCode题
算法-10-二叉树LeetCode题 从二叉树学递归思想 原文labuladong 写递归算法的关键是要明确函数的「定义」是什么,然后相信这个定义,利用这个定义推导最终结果,绝不要试图跳入递归。 // 定义:count(root) 返回以 root 为根的树有多少节点int count(TreeNode
C语言学习篇(32)——为什么C语言不能函数重载
C语言学习篇(32)——为什么C语言不能函数重载 前言 在日常的开发中,我们有时会遇到根据不同情景,想通过传入不同类型的参数,而调用统一的函数接口,即函数重载。 在C++中原生支持了函数重载, 而在C语言中并不支持,只能通过一些技巧来变相解决, 如定义fla