一、二叉树的性质

性质1、二叉树的第i层上至多有2 i-1（i ?1）个结点。用数学归纳法证明

推广：k叉树(或度为k的树)的第i层上至多有k i-1（i ?1）个结点

性质2、度为h的二叉树中至多含有2h-1个结点。

21-1 + 2 2-1+……+ 2 h-1 = 2 h-1

推广：深度为h的k叉树(或度为k的树)中至多含有 (k h-1)/(k-1)个结点

k1-1 + k 2-1+……+ k h-1 =( k h-1)/(k-1)

性质3、若在任意一棵二叉树中，有n0个叶子结点，

有n2个度为2的结点，则：n0=n2+1

证明：设：有n0个叶子结点，有n1个度为1的结点，有n2个度为2的结点， 则二叉树中结点总数为：n=n0+n1+ n2 (1)

设分支的总数为m,则：m= n1+2 n2 (2)

因为n=m+1（3）

所以： n0+n1+ n2 = n1+2 n2 +1

整理得： n0= n2+1

推广: 度为k的树有n1个度为1的结点， n2个度为2的结点，nk个度为k的结点则n0为:

?

i=1 k ( i- 1)ni+1

性质3推广的证明于性质3的证明

设：有n0个叶子结点，有n1个度为1的结点， n2个度为2的结点，nk个度为k的结点 则结点总数为：n=n0+n1+ n2 +……+nk(1)

设分支的总数为m,则：m= n1+2 n2+……+knk

因为n=m+1（3）

所以：n0+n1+ n2 +……+nk = n1+2 n2+……+knk +1

整理得： n0= 0n1+1n2+……+(k-1)nk+1

性质4、具有n个结点的完全二叉树，其深度为?㏒2n?+1

证明：设n个结点的完全二叉树的深度为k，根据性质2可知，k-1层满二叉树的结点总数为： 2k-1-1

k层满二叉树的结点总数为： 2k-1

…… …… 余下全文

一、二叉树的性质

性质1、二叉树的第i层上至多有2 i-1（i ?1）个结点。用数学归纳法证明

推广：k叉树(或度为k的树)的第i层上至多有k i-1（i ?1）个结点

性质2、度为h的二叉树中至多含有2h-1个结点。

21-1 + 2 2-1+……+ 2 h-1 = 2 h-1

推广：深度为h的k叉树(或度为k的树)中至多含有 (k h-1)/(k-1)个结点

k1-1 + k 2-1+……+ k h-1 =( k h-1)/(k-1)

性质3、若在任意一棵二叉树中，有n0个叶子结点，

有n2个度为2的结点，则：n0=n2+1

证明：设：有n0个叶子结点，有n1个度为1的结点，有n2个度为2的结点， 则二叉树中结点总数为：n=n0+n1+ n2 (1)

设分支的总数为m,则：m= n1+2 n2 (2)

因为n=m+1（3）

所以： n0+n1+ n2 = n1+2 n2 +1

整理得： n0= n2+1

推广: 度为k的树有n1个度为1的结点， n2个度为2的结点，nk个度为k的结点则n0为:

?

i=1 k ( i- 1)ni+1

性质3推广的证明于性质3的证明

设：有n0个叶子结点，有n1个度为1的结点， n2个度为2的结点，nk个度为k的结点 则结点总数为：n=n0+n1+ n2 +……+nk(1)

设分支的总数为m,则：m= n1+2 n2+……+knk

因为n=m+1（3）

所以：n0+n1+ n2 +……+nk = n1+2 n2+……+knk +1

整理得： n0= 0n1+1n2+……+(k-1)nk+1

性质4、具有n个结点的完全二叉树，其深度为?㏒2n?+1

证明：设n个结点的完全二叉树的深度为k，根据性质2可知，k-1层满二叉树的结点总数为： 2k-1-1

k层满二叉树的结点总数为： 2k-1

…… …… 余下全文

#include"malloc.h"

#define NULL 0

#include"stdio.h"

typedef struct node

{

char data;

struct node *lchild,*rchild;

}NODE;

int count;

NODE *crt_bt_pre()/*二叉树先序创建算法*/

{

NODE * bt;

char ch;

printf("\n\t\t\t");

scanf("%c",&ch);

getchar();

if(ch==' ') bt=NULL;

else

{

bt=(NODE*)malloc(sizeof(NODE));

bt->data=ch;

printf("\n\t\t\t请输入%c结点的左孩子:",bt->data); bt->lchild=crt_bt_pre();

printf("\n\t\t\t请输入%c结点的右孩子:",bt->data); bt->rchild=crt_bt_pre();

}

return(bt);

}

void Preorder(NODE* bt)/*二叉树先序递归遍历算法*/ {

if(bt!=NULL)

{

printf("\n\t\t\t %c",bt->data);

Preorder(bt->lchild);

Preorder(bt->rchild);

}

}

void Inorder(NODE* bt)

{

if(bt!=NULL)

{

Inorder(bt->lchild);

…… …… 余下全文

甘肃政法学院

数据结构课程设计

 题  目      二叉树遍历

计算机科学 学院 信息管理与信息系统 专业

 09  级信息管理与信息系统 班

学    号：_200981020116

姓    名：___唐占红____

指导教师：___金 涛_____

成    绩：_____________

完成时间：_2010 年 12 月

[摘 要]二叉树是树形结构的一个重要的类型，二叉树是n（n>=0）个结点的有限集，它或者是空集（n=0），或者由个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。

二叉树的存储结构和算法比较简单，特别适合计算机处理。即使一般形式的树也可简单的转换为二叉树。二叉树的顺序存储结构是把二叉树的所有结点，按照一定的次序顺序，存储到一片连续的存储单元中。遍历二叉树就是沿某有前序遍历、中条搜索路径周游二叉树，对树中每个结点访问一次且仅访问一次。在遍历方案中主要序遍历、后序遍历。

    现实中有许多应用到二叉树的例子，所以我们要把理论与现实结合起来。在学习中主要掌握怎么求二叉树的高度、叶子结点个数、总结点个数以及熟练三种遍历的方法。

[关键词] 二叉树  遍历   深度

目 录

第一章 数据结构课程设计题目及解析. 3

&1.1 数据结构课程设计题目. 3

&1.2 设计题目解析. 3

第二章 程序设计的目的和基本要求. 3

&2.1 程序设计的目的. 3

&2.2 程序设计的基本要求. 3

第三章 程序设计的内容. 3

…… …… 余下全文

//------------------二叉树结点的数据结构---------------

typedef struct BiTNode //树节点定义

{

int value;

BiTNode *lchild,*rchild;

}BiTNode,*BiTree;

//-------------------二叉树的遍历------------------

void Preorder(BiTree root) //先序遍历以T树根指针的二叉树(递归算法) {

}

if(root) { cout<<root->value; Preorder(root->lchild); Preorder(root->rchild); }

//-------------------先序遍历求二叉树的深度------------------

int depth=0,h=0;

void BiTreeDepthPre(BiTree root,int h,int &depth)

{

if(root)

{

if(h>depth)

depth=h;

BiTreeDepthPre(root->lchild,h+1,depth);

BiTreeDepthPre(root->rchild,h+1,depth);

}

}

//-------------------后序遍历求二叉树的深度------------------

int BiTreeDepthPost(BiTree root)

{

int hl=0,hr=0;

if(!root)

return 0;

else

{

hl=BiTreeDepthPost(root->lchild); hr=BiTreeDepthPost(root->rchild); if(hl>=hr)

…… …… 余下全文

实验三　二叉树的遍历

一、实验目的

１、熟悉二叉树的结点类型和二叉树的基本操作。

２、掌握二叉树的前序、中序和后序遍历的算法。

3、加深对二叉树的理解，逐步培养解决实际问题的编程能力。

二、实验环境

运行Ｃ或VC++的微机。

三、实验内容

1、依次输入元素值，以链表方式建立二叉树，并输出结点的值。

2、分别以前序、中序和后序遍历二叉树的方式输出结点内容。

四、设计思路

1. 对于这道题，我的设计思路是先做好各个分部函数，然后在主函数中进行顺序排列，以此完成实验要求

2．二叉树采用动态数组

3.二叉树运用9个函数，主要有主函数、构建空二叉树函数、建立二叉树函数、访问节点函数、销毁二叉树函数、先序函数、中序函数、后序函数、范例函数，关键在于访问节点

五、程序代码

#include <stdio.h>

#include <stdlib.h>

#include <malloc.h>

#define OK 1

#define ERROR 0

typedef struct TNode//结构体定义

 {

     int data; //数据域

     struct TNode *lchild,*rchild;  // 指针域包括左右孩子指针

 }TNode,*Tree;

 void CreateT(Tree *T)//创建二叉树按,依次输入二叉树中结点的值

 {

   int a;

   scanf("%d",&a);

   if(a==00) // 结点的值为空

     *T=NULL;

…… …… 余下全文

#include "stdio.h"

#include "stdlib.h"

#include "string.h"

#include "math.h"

typedef char TElemType; //定义结点数据为字符型 typedef int Status; //定义函数类型为int型 #define ERROR 0

#define OK 1

typedef struct BiTNode{ //定义结构体

TElemType data; //结点数值 struct BiTNode *lchild; //左孩子指针 struct BiTNode *rchild; //右孩子指针 struct BiTNode *next; //下一结点指针 }BiTNode, *BiTree;

Status NumJudge(char ch[20]){

//限制输入数据必须为大于零的整形

char ch1[20]; int num; while(1){ } scanf("%s",ch); num=atoi(ch); //将字符串转换为整型 itoa(num,ch1,10); //将整型转换为字符串型 if(strcmp(ch,ch1)==0&&num>0)break; else{printf("请输入一个大于零的整数: ");}

return num;

}//NumJudge

Status InitBiTree(BiTree &T){

//构造空二叉树T

if(!(T=(BiTree)malloc(sizeof(BiTNode))))exit(ERROR); //若申请空间失败则退出 T->next=NULL; printf("\n\t空二叉树构建成功!\n\n"); return OK;

…… …… 余下全文