线性表(不管是顺序存储还是链式存储)的元素之间的逻辑关系是线性的,这有时候并不能满足实际的要求,树形结构是另一种数据结构,它的元素之间的逻辑关系画成图的话形似一颗倒挂的树,故而得名。二叉树是树形结构中的特例,每个结点最多有两个孩子,就好像处于计划生育年代一样。
下面就是二叉树的一些基本操作,程序是用c语言写的。
#include <stdio.h>
#include <stdlib.h>
typedef struct _Node {
int data;
struct _Node *lchild, *rchild;
} Node, *Pnode;
Pnode CreateBT();
void Preorder(Pnode);
void Inorder(Pnode);
void Postorder(Pnode);
void ShowTree(Pnode, int);
int LeafNum(Pnode);
int NodeNum(Pnode);
int main()
{
Pnode head = NULL;
int x = 0;
printf("二叉树\n");
do {
printf("*************************\n");
if (head) {
printf("(二叉树已存在!)\n");
} else {
printf("(二叉树还未创建!)\n");
}
printf("* 请选择要执行的操作:\n");
printf("* [1] 创建二叉树\n");
printf("* [2] 先序遍历\n");
printf("* [3] 中序遍历\n");
printf("* [4] 后续遍历\n");
printf("* [5] 显示二叉树\n");
printf("* [6] 显示叶子数\n");
printf("* [7] 显示二叉树的结点数\n");
printf("* [9] 退出\n");
printf("*************************\n");
printf("你的选择:");
scanf("%d", &x);
switch (x) {
case 1:
printf("请输入根结点\n");
head = CreateBT();
break;
case 2:
Preorder(head);
printf("\n");
break;
case 3:
Inorder(head);
printf("\n");
break;
case 4:
Postorder(head);
printf("\n");
break;
case 5:
ShowTree(head, 1);
break;
case 6:
printf("叶子数是%d\n", LeafNum(head));
break;
case 7:
printf("结点数是%d\n", NodeNum(head));
break;
default:
break;
}
} while (x != 9);
printf("bye!\n");
return 0;
}
Pnode CreateBT() {
Pnode t = NULL;
int iput = 0;
scanf("%d", &iput);
if (iput==0) {
t = NULL;
} else {
t = (Pnode)malloc(sizeof(Node));
t->data = iput;
printf("请输入%d的左孩子\n", iput);
t->lchild = CreateBT();
printf("请输入%d的右孩子\n", iput);
t->rchild = CreateBT();
}
return t;
}
void Preorder(Pnode p) {
if (p) {
printf("%d ", p->data);
Preorder(p->lchild);
Preorder(p->rchild);
}
}
void Inorder(Pnode p) {
if (p) {
Inorder(p->lchild);
printf("%d ", p->data);
Inorder(p->rchild);
}
}
void Postorder(Pnode p) {
if (p) {
Postorder(p->lchild);
Postorder(p->rchild);
printf("%d ", p->data);
}
}
void ShowTree(Pnode p, int dep) {
if (p) {
for (int i = 0; i < dep; i++) {
printf(" ");
}
printf("%d**********\n", p->data);
ShowTree(p->lchild,dep+1);
ShowTree(p->rchild, dep+1);
}
}
int LeafNum(Pnode p) {
if ((!p->lchild) && (!p->rchild)) {
return 1;
} else if (!p->lchild) {
return LeafNum(p->rchild);
} else if (!p->rchild) {
return LeafNum(p->lchild);
} else {
return LeafNum(p->lchild)+LeafNum(p->rchild);
}
}
int NodeNum(Pnode p) {
if (!p) {
return 0;
}
return NodeNum(p->lchild) + NodeNum(p->rchild)+1;
}
分享到:
相关推荐
(2)先序、中序、后序遍历二叉树:递归算法。 (3)中序遍历二叉树:非递归算法(最好也能实现先序,后序非递归算法)。 (4)求二叉树的高度 。 (5)求二叉树的叶子个数。 (6)对于树中每一个元素值为x的结点...
建立一棵二叉树,试编程实现二叉树的如下基本操作: 1. 按先序序列构造一棵二叉链表表示的二叉树T; 2. 对这棵二叉树进行遍历:先序、中序、后序以及层次遍历,分别输出结点的遍历序列; 3. 求二叉树的深度/结点数目...
1、 定义链接存储的二叉树类。 2、 实验验证如下算法的正确性、各种功能及指标: 1) 创建一棵二叉树,并对其初始化; 2)先根、中根、后根遍历二叉树; 3) 在二叉树中搜索给定结点的父结点; 4) 搜索二叉树中符合...
编写程序实现二叉树的如下操作: 1) 建立二叉链表 2) 二叉树的先序、中序、后序遍历 3) 求解二叉树的叶子结点个数 4) 将二叉树中所有结点的左、右子树相互交换 输入: 扩展二叉树先序序列:ab#d##ce###。其中#...
数据结构试验3二叉树建立,遍历等操作代码及运行结果。 实验内容: 采用二叉链表存储,实现二叉树的创建、遍历(递归)、赫夫曼编码和译码等典型操作。 1. 编程实现如下功能: (1)假设二叉树的结点值是字符型,...
3 程序所能达到的功能:生成一个新的二叉树,实现对二叉树的先序,中序,后序和层次遍历,计算二叉树的深度,结点数,叶结点数,。 4 测式数据: A生成一个新的二叉树后,直接在键盘上按要求输入字符,可以依次输入...
如果给出了遍历二叉树的前序序列和中序序列,则可以构造出唯一的一棵二叉树。试编写实现上述功能的程序。 [基本要求] 已知一棵二叉树的前序和中序序列,试设计完成下列任务的一个算法: (1)构造一棵二叉树...
详细的树和二叉树的教程,还附有源代码 部分代码如下: 二叉树头文件.h //二叉树的二叉链表存储表示 typedef struct BiTNode {TElemType data; //二叉树结点数据域 struct BiTNode *lchild,*rchild; //左右孩子指针...
按先序序列构造一棵二叉链表表示的二叉树T,并输出该T的中序遍历序列。实现提示: 1) 按先序序列建立一棵二叉树时,先构造根结点,再构造根的左子树,然后构造右子树;每棵子树又都是二叉树,所以构造一棵子树的过程...
1.二叉树的基本操作实现【问题描述】建立一棵二叉树,用递归方法实现二叉树的如下基本操作:(1)按先序序列构造一棵二叉链表表示的二叉树T;(2)对这棵二叉树进行遍历:先序、中序、后序以及层次遍历,分别输出...
根据先序与中序遍历结果建立二叉树 输入为: 第一行:二叉树的先序遍历结果 第二行:二叉树的中序遍历结果 例如: ①输入aa则返回的指针指向的二叉树应该就是仅有一个节点,值为a. ②输入123213则返回的指针指向...
运用二叉链表实现二叉树的基本操作,包括:创建二叉树的存储结构、复制已有的二叉树、计算已有的二叉树的深度、先根序序列、中根序序列、后根序序列等。 输入格式:AB#C##D## 二、实验目的 掌握二叉链表及二叉树的...
1.采用二叉链表作为存储结构,创建一棵二叉树; 2.用递归及非递归算法对二叉树实现先序遍历; 3.用递归及非递归算法对二叉树实现中序遍历; 4.用递归及非递归算法对二叉树实现后序遍历。 5.用递归遍历算法中的访问...
一)建立二叉树+判空+遍历 (1)以二叉链表作为存储结构,从键盘以先序次序输入各个结点(空格字符表示空树)建立一棵二叉树; (2)对(1)中生成的二叉树进行判空; (3)对(1)中生成的二叉树进行遍历(分别实现...
二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树
一、实验名称:二叉树的遍历方法 二、实验目的: (1)熟悉C语言的上机环境,进一步掌握C语言的结构特点; (2)掌握二叉树的储存结构的定义及C语言实现; (3)掌握二叉树的三种遍历方法,即先序遍历,中序遍历,...
4.掌握计算二叉树的结点个数、二叉树的深度、二叉树的叶子结点和二叉树复制算法。 二、实验内容 1、构造基于先序遍历的二叉链表。 要求:按先序遍历规则,从键盘连续输入二叉树的先序序列,若无孩子结点,则用#代替...
在计算机科学中,二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。 一棵深度为k,且有2^k-1个结点的...
根据二叉树的抽象数据类型的定义,使用二叉链表实现一个二叉树。 二叉树的基本功能: 1、二叉树的建立 2、前序遍历二叉树 3、中序遍历二叉树 4、后序遍历二叉树 5、按层序遍历二叉树 6、求二叉树的深度 7、求指定...