数据结构二叉树的基本操作

数据结构二叉树基本操作

(1).

// 对二叉树的基本操作的类模板封装

//------------------------------------------------------------------------------------------------------------------------

#include using namespace std;

//------------------------------------------------------------------------------------------------------------------------

//定义二叉树的结点类型BTNode,其中包含数据域、左孩子，右孩子结点。 template struct BTNode {

T data ; //数据域 BTNode* lchild; //指向左子树的指针 BTNode* rchild; //指向右子树的指针 };

//-------------------------------------------------

实验六：二叉树及其应用

一、实验目的

树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题。

二、问题描述

首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。 如算术表达式：a+b*(c-d)-e/f

三、实验要求

如果利用完全二叉树的性质和二叉链表结构建立一棵二叉树，分别计算统计叶子结点的个数。求二叉树的深度。十进制的四则运算的计算器可以接收用户来自键盘的输入。由输入的表达式字符串动态生成算术表达式所对应的二叉树。自动完成求值运算和输出结果。

四、实验环境

PC微机

DOS操作系统或 Windows 操作系统

Turbo C 程序集成环境或 Visual C++ 程序集成环境 1、根据二叉树的各种存储结构建立二叉树；

2、设计求叶子结点个数算法和树的深度算法；

3、根据表达式建立相应的二叉树，生成表达式树的模块； 4、根据表达式树，求出表达式值，生成求值模块； 5、程序运行效果，测试数据分析算法。

五、实验步骤

六、测试数据

1、输入数据：2.2*（3.1+1.20）-7.5/3

正确结果：6.9

第六章 习题

一、选择题

1、在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个 A 、4 B、5 C、6 D、 7

2、假定在一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（ ）个。

A、 15 B、16 C、17 Ｄ、47

3、假定一棵三叉树的结点数为50，则它的最小高度为（ ） A、 3 B、4 C、5 D、6

4、在一棵二叉树上第5层的结点数最多为（ ） A、8 B、 16 C、 15 D、32

5、用顺序存储方式将完全二叉树中的所有结点逐层存放在数组R[1..n]中，结点R[I]若有子树，则左子树是结点（ ）

A、R[2I+1] B、R[2I] C、R[I/2] D、R[2I-1] 6、在一棵具有k层的满三叉树中，结点总数为（ ） A、（3k-1）/2 B、3k-1 C、（3k-1）/3 D、3k

7、由带权为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（

二叉树的基本运算

数据结构常见问题 二叉树的基本运算（C语言）2007年05月09日 星期三 13:19/*[问题描述] 随机生成25个整数，介于1～10间为真实节点，其余为虚节点。将这一生成理解成完全二叉树，构造生成一棵完全二叉树。在此基础上执行：先根、中根、后根遍历；指定一节点整数，可给出其从根开始的路径。
[基本要求] 二叉树采用链式方式存储。*/

#include<stdio.h>
#include<stdlib.h>
#define N 25

/*----------------------------------------------------------------*/
typedef struct BiTNode
{
int data;
int tag;
struct BiTNode *lchild,*rchild,*parent;
}BiTNode,* btree;

typedef struct stack
{
int *base;
int *top;
int stacksize;
}stack;

btree Creat(btree t,int num[],int n,int i);
void preOrder(btree t);
voi

二叉树的基本运算

数据结构常见问题 二叉树的基本运算（C语言）2007年05月09日 星期三 13:19/*[问题描述] 随机生成25个整数，介于1～10间为真实节点，其余为虚节点。将这一生成理解成完全二叉树，构造生成一棵完全二叉树。在此基础上执行：先根、中根、后根遍历；指定一节点整数，可给出其从根开始的路径。
[基本要求] 二叉树采用链式方式存储。*/

#include<stdio.h>
#include<stdlib.h>
#define N 25

/*----------------------------------------------------------------*/
typedef struct BiTNode
{
int data;
int tag;
struct BiTNode *lchild,*rchild,*parent;
}BiTNode,* btree;

typedef struct stack
{
int *base;
int *top;
int stacksize;
}stack;

btree Creat(btree t,int num[],int n,int i);
void preOrder(btree t);
voi

#include \#include \#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status;

typedef char ElemType; typedef struct BiTNode {

ElemType data;

struct BiTNode *lchild,*rchild;//左右孩子指针 } BiTNode,*BiTree;

Status CreateBiTree();

Status CreateBiTree(BiTree &T) // 算法6.4 {

// 按先序次序输入二叉树中结点的值（一个字符），’#’字符表示空树， // 构造二叉链表表示的二叉树T。 char ch;

scanf(\ if (ch=='#') T = NULL; else {

if (!(T = (BiTNode *)malloc(sizeof(BiTNode))))

第六章 树和二叉树

一、选择题

1．已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( )

A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE 【北京航空航天大学 1999 一、3 （2分)】

2．算术表达式a+b*（c+d/e）转为后缀表达式后为（ ）【中山大学 1999 一、5】

A．ab+cde/* B．abcde/+*+ C．abcde/*++ D．abcde*/++ / 3. 设有一表示算术表达式的二叉树（见下图），

+ + 它所表示的算术表达式是（ ）

【南京理工大学1999 一、20（2分）】 * - * C A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) E F G D B A C. (A*B+C)/(D*E+（F-G）) D. A*B+C/D*E+F-G

则T中的叶子 ，1 4. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1

数为（ ）

A．

第六章 树和二叉树

一、选择题

1．已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( )

A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE 【北京航空航天大学 1999 一、3 （2分)】

2．算术表达式a+b*（c+d/e）转为后缀表达式后为（ ）【中山大学 1999 一、5】

A．ab+cde/* B．abcde/+*+ C．abcde/*++ D．abcde*/++ / 3. 设有一表示算术表达式的二叉树（见下图），

+ + 它所表示的算术表达式是（ ） 【南京理工大学1999 一、20（2分）】 * - * C A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) B D E F G A C. (A*B+C)/(D*E+（F-G）) D. A*B+C/D*E+F-G

则T中的叶子 ，1 4. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1

数为（ ）

A．

liminationcoalproductionprocessintheofvariousaccidenthidden,improvedworkersworkingconditionsandworkenvironment,preventaccidentoccurred,promotesafet 数据结构课程设计

题目：二叉树的集合操作

学院：计算机与信息工程学院

年级：

班级：

姓名：陈礼

时间：

ddentroubleshootingandreorganizationcloseimplementationapproachandcoalminesecurityproceduresabout 2 3 2004-6-17

liminationcoalproductionprocessintheofvariousaccidenthidden,improvedworkersworkingconditionsandworkenvironment,preventaccidentoccurred,promotesafet 一、需求分析：

编写一段程序，对二叉树进行复合操作，包括创建一棵二叉树，显示二叉树的树型结构，对创建的

数据结构上机实验报告

二叉树问题

陈冠豪

2010210501

0101015

二O一O年5月26号

验的目建一棵立二树叉要，分别求递用归和递非方法实归二现 叉树的先、序序中和序遍后历。

实现代码:

#ifndef TREE_H #define TREE_H #include <stdio.h> #include <malloc.h> #include <stack> #include <queue> #include <assert.h> using namespace std; typedefintElemType; typedef struct treeT { ElemType key; struct treeT* left; struct treeT* right; }treeT, *pTreeT;

static void visit(pTreeT root) { if (NULL != root) { printf(" %d\n", root->key); } } static pTreeT BT_MakeNode(E