第一篇：二叉树的性质总结
一、二叉树的性质
性质
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
显然有：
2k-1-1 < n 2k-12k-1 n < 2k
取对数有：k-1 log2n < k
因为k是整数，所以k-1 = log2n，k= ㏒2n 1
结论成立。
推广: 具有n个结点的完全k叉树，其深度为 logk(k-1)n 1
设n个结点的完全k叉树的深度为h，根据性质2推广可知，h-1层满k叉树的结点总数为：(k h-1-1)/(k-1)
h层满二叉树的结点总数为：(k h-1)/(k-1)
显然有：
(k h-1-1)/(k-1)< n (k h-1)/(k-1)
k h-1-1 <(k-1)n k h-1
k h-1 (k-1)n< k h
取对数有：h-1 logk(k-1)n 因为h是整数，所以h-1 = logk(k-1)n ，h= logk(k-1)n 1 性质 5、设完全二叉树共有n个结点。如果从根结点开始，按层序(每一层从左到右)用自然数1，2，3……,n给结点进行编号，则对于编号为k(k=1,2,……n)的结点有以下结论： (1)若k=1,则该结点为根结点，它没有双亲结点；若k>1,则该结点的双亲结点编号为 [k/2 ]。 (2)若2k<=n,则编号为k的左孩子结点编号为2k;否则该结点无左孩子结点(显然也没有右孩子结点)。 (3)若2k 1<=n,则编号为k的右孩子结点编号为2k 1;否则该结点无右孩子结点 推广:一个深度为L的满K叉树有以下性质：第L层上的结点都是叶子结点，其余各层上每个结点都有K棵非空子树，如果按层次顺序从1开始对全部结点进行编号，求： 1）各层的结点的数目是多少？ 2）编号为n的结点的双亲结点（若存在）的编号是多少？ 3）编号为n的结点的第i 个孩子结点（若存在）的编号是多少？ 4）编号为n的结点有右兄弟的条件是什么？如果有，其右兄弟的编号是多少？ 答: h-1(1)k(h为层数) h-1（2）因为该树每层上均有K个结点，从根开始编号为1，则结点i的从右向左数第２个 孩子的结点编号为ki。设n 为结点i的子女，则关系式(i-1)k 2<=n<=ik 1成立，因i是整数，故结点n的双亲i的编号为n-2)/k 1。 (3)结点n(n>1)的前一结点编号为n-1（其最右边子女编号是(n-1)*k 1），故结点 n的第 i个孩子的编号是(n-1)*k 1 i。 (4)根据以上分析，结点n有右兄弟的条件是，它不是双亲的从右数的第一子女，即(n-1)%k!=0，其右兄弟编号是n 1。 二：满二叉树： 一棵深度为k且有2k-1个结点的二叉树 特点：每一层上都含有最大结点数。叶子结点在同一层次上；无度为1的结点 具有n个结点的满二叉树则 叶子结点的个数为：（n 1)/2 度为2的结点的个数为：（n-1)/2 三、无度为1的结点 1: 具有n个结点的无度为1的结点的二叉树，求叶子结点的个数 n1=0 n=n1 n2 n0=n0 n2 0 n=2n0-1 n0=（n 1）/2n2=（n-1）/2 2:若已知叶子结点个数n0求总的结点的个数n N=n0 n2=2n0-1 四、完全二叉树：深度为k的有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中的编号从1至n的结点一一对应 特点：除最后一层外，每一层都取最大结点数，最后一层结点都集中在该层最左边的若干位置。 叶子结点在最后两层上，度为1的结点的个数最多为1 1:具有n个结点的完全二叉树，求叶子结点的个数 n是偶数： 则n1=1 n=n1 n2 n0=n0 n2 1 n=2n0 n0=n/2n2=n/2-1 n是奇数： 则n1=0 n=n1 n2 n0=n0 n2 0 n=2n0-1 n0=（n 1）/2n2=（n-1）/2 2:若已知完全二叉树叶子结点个数：求总的结点的个数 n=n0 n1 n2 n1=1 或n1=0n2=n0-1 n最大为2n0,最小为2n0-1 3:若已知完全二叉树第k层上具有n个叶子结点，求最多的结点个数及最少的结点个数最多的结点个数：共有k 1层 前k层共有2k-1个结点 k 1层: 第k 1层结点数最多为第k层的非叶子结点数乘以2；第k层的结点数为2k-1，叶子结点数为n, 非叶子结点数为(2k-1-n)，所以第k 1层结点数最多为2(2k-1-n)个结点,所以最多结点数为2k-1 2(2k-1-n) 最少的结点个数：共有k层 前k-1层具有2k-1-1个结点，k层有n个共有2k-1-1 n 实验报告 二叉树 一 实验目的 1、进一步掌握指针变量，动态变量的含义； 2、掌握二叉树的结构特性以及各种存储结构的特点及适用范围。 3、掌握用指针类型描述、访问和处理二叉树的运算。 4、熟悉各种存储结构的特征以及如何应用树结构解决具体问题。 二 实验原理 树形结构是一种应用十分广泛和重要的非线性数据结构，是一种以分支关系定义的层次结构。在这种结构中，每个数据元素至多只有一个前驱，但可以有多个后继；数据元素之间的关系是一对多的层次关系。树形结构主要用于描述客观世界中具有层次结构的数据关系，它在客观世界中大量存在。遍历二叉树的实质是将非线性结构转为线性结构。 三 使用仪器，材料 计算机 2 Wndows xp 3 VC6.0 四实验步骤 【问题描述】建立一个二叉树，请分别按前序，中序和后序遍历该二叉树。【基本要求】从键盘接受输入（按前序顺序），以二叉链表作为存储结构，建立二叉树（以前序来建立），并采用递归算法对其进行前序，中序和后序遍历，将结果输出。 【实现提示】按前序次序输入二叉树中结点的值（一个整数），0表示空树，叶子结点的特征是其左右孩子指针为空。 五实验过程原始记录 基本数据结构描述； 2 函数间的调用关系； 用类C语言描述各个子函数的算法； 附录：源程序。 六 试验结果分析 将实验结果分析、实验中遇到的问题和解决问题的方法以及关于本实验项目的心得体会，写在实验报告上。 # include { Etype data; struct BiTNode *lch,*rch; }BiTNode;/* 函数原形声明 */ BiTNode *creat_bt1();BiTNode *creat_bt2();void preorder(BiTNode *p);void inorder(BiTNode *p);void postorder(BiTNode *p);void numb1(BiTNode *p);void numb2(BiTNode *p);void numb3(BiTNode *p);BiTNode *t;int n,n0,n1,n2;/* 主函数 */ main(){ char ch;int k; do { printf(“nnn”); printf(“nn 1.建立二叉树方法1 ”); printf(“nn 2.建立二叉树方法2”); printf(“nn 3.前序递归遍历二叉树”); printf(“nn 4.中序递归遍历二叉树”); printf(“nn 5.后序递归遍历二叉树”); printf(“nn 6.前序计算树中结点个数”); printf(“nn 7.中序计算树中结点个数”); printf(“nn 8.后序计算树中结点个数”); printf(“nn 9.结束程序运行”); printf(“n======================================”); printf(“n 请输入您的选择(1-9)”);scanf(“%d”,&k); switch(k) { case 1:t=creat_bt1();break;/* 调用性质5建立二叉树算法 */ case 2:t=creat_bt2();break;/* 调用递归建立二叉树算法 */ case 3: { preorder(t); /* 调用前序遍历 */ printf(“nn 打回车键，继续。”);ch=getch(); } break; case 4: { inorder(t); /* 调用中序遍历 */ printf(“nn 打回车键，继续。”);ch=getch(); } break; case 5: { postorder(t); /* 调用后序遍历 */ printf(“nn 打回车键，继续。”);ch=getch(); } break; case 6:{ n=0;n0=0;n1=0;n2=0;/* 全局变量置0 */ numb1(t); printf(“n 二叉树结点总数 n=%d”,n); printf(“n 二叉树叶子结点数 n0=%d”,n0); printf(“n 度为1的结点数 n1=%d”,n1); printf(“n 度为2的结点数 n2=%d”,n2); printf(“nn 打回车键，继续。”);ch=getch(); } break; case 7:{ n=0;n0=0;n1=0;n2=0;/* 全局变量置0 */ numb2(t); printf(“n 二叉树结点总数 n=%d”,n); printf(“n 二叉树叶子结点数 n0=%d”,n0); printf(“n 度为1的结点数 n1=%d”,n1); printf(“n 度为2的结点数 n2=%d”,n2); printf(“nn 打回车键，继续。”);ch=getch(); } break; case 8:{ n=0;n0=0;n1=0;n2=0;/* 全局变量置0 */ numb3(t); printf(“n 二叉树结点总数 n=%d”,n); printf(“n 二叉树叶子结点数 n0=%d”,n0); printf(“n 度为1的结点数 n1=%d”,n1); printf(“n 度为2的结点数 n2=%d”,n2); printf(“nn 打回车键，继续。”);ch=getch(); } break; case 9: exit(0); } /* switch */ printf(“n----------------”); }while(k>=1 && k<9); printf(“n 再见！”); printf(“n 打回车键，返回。”);ch=getch();} /* main */ /* 利用二叉树性质5，借助一维数组V 建立二叉树 */ BiTNode *creat_bt1(){ BiTNode *t,*p,*v[20];int i,j;Etype e; /* 输入结点的序号i、结点的数据e */ printf(“n 序号i,数据data=?”);scanf(“%d%d”,&i,&e); while(i!=0 && e!=0) /* 当 i ,e都为0时，结束循环 */ { p=(BiTNode *)malloc(sizeof(BiTNode)); p->data=e;p->lch=NULL;p->rch=NULL; v[i]=p; if(i==1)t=p; /* 序号为1的结点是根 */ else{ j=i/2; if(i%2==0)v[j]->lch=p;/* 序号为偶数，做左孩子*/ else v[j]->rch=p;/* 序号为奇数，做右孩子*/ } printf(“n i,data=?”);scanf(“%d%d”,&i,&e); } return(t);} /* creat_bt1 */ /* 模仿先序递归遍历方法，建立二叉树 */ BiTNode *creat_bt2() { BiTNode *t; int e; printf(“n data=”);scanf(“%d”,&e); if(e==0)t=NULL; /* 对于0值，不分配新结点 */ else { t=(BiTNode *)malloc(sizeof(BiTNode)); t->data=e; t->lch=creat_bt2();/* 左孩子获得新指针值 */ t->rch=creat_bt2();/* 右孩子获得新指针值 */ } return(t); } /* creat_bt2 */ /* 前序递归遍历二叉树 */ void preorder(BiTNode *p){ if(p){ printf(“=”,p->data); preorder(p->lch); preorder(p->rch); } } /* preorder */ /* 中序递归遍历二叉树 */ void inorder(BiTNode *p){ if(p){ inorder(p->lch); printf(“=”,p->data); inorder(p->rch); } } /* inorder */ /* 后序递归遍历二叉树 */ void postorder(BiTNode *p){ if(p){ postorder(p->lch); postorder(p->rch); printf(“=”,p->data); } } /* posorder */ /* 利用前序递归遍历二叉树的方法，计算树中结点个数 */ void numb1(BiTNode *p){ if(p){ { printf(“=”,p->data); n ; if(p->lch==NULL && p->rch==NULL)n0 ; if((p->lch==NULL && p->rch!=NULL)|| (p->lch!=NULL && p->rch==NULL))n1 ; if(p->lch!=NULL && p->rch!=NULL)n2 ; } numb1(p->lch); numb1(p->rch); } } /* numb1 */ /* 利用中序递归遍历二叉树的方法，计算树中结点个数 */ void numb2(BiTNode *p){ if(p){ numb2(p->lch); { printf(“=”,p->data); n ; if(p->lch==NULL && p->rch==NULL)n0 ; if((p->lch==NULL && p->rch!=NULL)|| (p->lch!=NULL && p->rch==NULL))n1 ; if(p->lch!=NULL && p->rch!=NULL)n2 ; } numb2(p->rch); } } /* numb2 */ /* 利用后序递归遍历二叉树的方法，计算树中结点个数 */ void numb3(BiTNode *p){ if(p){ numb3(p->lch); numb3(p->rch); { printf(“=”,p->data); n ; if(p->lch==NULL && p->rch==NULL)n0 ; if((p->lch==NULL && p->rch!=NULL)|| (p->lch!=NULL && p->rch==NULL))n1 ; if(p->lch!=NULL && p->rch!=NULL)n2 ; } } } /* numb3 */ 数据结构实验报告二 题目： 用先序递归过程监理二叉树（存储结构：二叉链表） 输入数据按先序遍历输入，当某节点左子树或者右子树为空时，输入‘*’号，如输入abc**d**e**时，得到的二叉树为： 并用如下实力测试： 算法思路： 显然，建立一个二叉链表存储的二叉树，如果不考虑效率要求，考虑到程序的简介性，递归建立和递归遍历是一种很好的办法。 利用C 的类模板的方法实现建立，遍历，输出等二叉树操作。首先利用构造函数实现先序遍历建立二叉树，然后调用类模板中已经声明好的四种遍历函数，将遍历结果输出，检验建立好的二叉树是否为要求的二叉树。 初始化：利用构造函数建立二叉树。采用先序递归的调用方法，构造函数主体如下： template template root = new BiNode //生成一个结点 root->data=aa; root->lchild = Creat(); //递归建立左子树 root->rchild = Creat(); //递归建立右子树 } return root;} 构造这样的函数，可以在输入时，按先序遍历顺序每次输入一个节点的数据，可以实现任意二叉树的构造。 为了检验构造的二叉树是否为预先设想的二叉树，需要遍历二叉树并进行输出。考虑到单一的输出并不能确定唯一的二叉树，因此对遍历二叉树的四种常用发方法，即先序遍历，中序遍历，后续遍历，层次遍历分别实现，通过遍历结果检验构造的二叉树是否为预先设计好的二叉树。 先序遍历：采用递归的方法建立。template xianxu(root->lchild);//先序遍历树的左子树 xianxu(root->rchild);//先序遍历树的右子树 } 中序遍历：递归方法建立： template if(root==NULL)return; //如果节点为空，则返回空 else{ zhongxu(root->lchild); //中序递归遍历root的左子树 cout< //访问根结点 zhongxu(root->rchild); //中序递归遍历root的右子树 } } 后序遍历：递归方法建立： template if(root==NULL) return; //如果节点为空，返回空 else{ houxu(root->lchild); //后序递归遍历root的左子树 houxu(root->rchild); //后序递归遍历root的右子树 cout< //访问根节点 } } 层序遍历：采用非递归方法。利用队列的方法层序遍历二叉树。建立一个队列，在访问一个节点的时候，把它的左孩子和右孩子入队，并且将这个节点出队。当队列为空时，就完成了对二叉树的层序遍历。 template Q[rear ] = root;// 若节点不为空，则该节点入队 while(front!= rear) { q = Q[front ];//只要队列不为空，则节点依次出队 cout< if(q->lchild!= NULL) Q[rear ] = q->lchild; if(q->rchild!= NULL) Q[rear ] = q->rchild;// 同时，该节点的双子入队 } } } 函数主体部分：声明一个类中的对象，调用构造函数，建立二叉树，并输出四种遍历结果，检验输出结果。 int main(){ BiTree BiNode cout<<“前序遍历序列为 ”< 程序结构： 主函数建立一个类模板定义构造函数，析构函数，以及成员函数声明类中的一个对象调用构造函数，构造一颗二叉树层序遍历二叉树后序遍历二叉树中序遍历二叉树前序遍历二叉树获取该二叉树的根节点将结果输出，人工检验 源代码： #include template { T data; BiNode template { public: BiTree(); //构造函数，初始化一棵二叉树 ~BiTree(void); //析构函数，释放二叉链表中各结点的存储空间 BiNode //获得指向根结点的指针 void xianxu(BiNode //前序遍历二叉树 void zhongxu(BiNode //中序遍历二叉树 void houxu(BiNode //后序遍历二叉树 void cengxu(BiNode //层序遍历二叉树 private: BiNode BiNode void Release(BiNode };template template if(aa==“*”)root = NULL; else{ root = new BiNode //生成一个结点 root->data=aa; root->lchild = Creat(); //递归建立左子树 root->rchild = Creat(); //递归建立右子树 } return root;} template template template else{ cout< xianxu(root->lchild);//先序遍历树的左子树 xianxu(root->rchild);//先序遍历树的右子树 } } template if(root==NULL)return; //如果节点为空，则返回空 else{ zhongxu(root->lchild); //中序递归遍历root的左子树 cout< //访问根结点 zhongxu(root->rchild); //中序递归遍历root的右子树 } } template if(root==NULL) return; //如果节点为空，返回空 else{ houxu(root->lchild); //后序递归遍历root的左子树 houxu(root->rchild); //后序递归遍历root的右子树 cout< //访问根节点 } } template const int MaxSize = 100;int front = 0;int rear = 0;//利用队列的方法对树进行层序遍历 BiNode BiNode else{ Q[rear ] = root;// 若节点不为空，则该节点入队 while(front!= rear) { q = Q[front ];//只要队列不为空，则节点依次出队 cout< if(q->lchild!= NULL) Q[rear ] = q->lchild; if(q->rchild!= NULL) Q[rear ] = q->rchild;// 同时，该节点的双子入队 } } } template if(root!= NULL){ Release(root->lchild); //释放左子树 Release(root->rchild); //释放右子树 delete root; } } int main(){ BiTree BiNode cout<<“前序遍历序列为 ”< cout<<“层序遍历序列为”< 通过对结果的分析，发现输出结果与建立二叉树时的输入完全符合，说明程序的运行结果是正确的。 心得体会： 1)函数递归的方法可以在相当程度上使程序简洁，避免代码的冗长复杂。2)构造函数如果带参数，在声明对象的时候应该将实参指出来。但是本题中构造函数位递归调用，初始的根节点的数据值由键盘输入，因此无法在声明对象时引入实参。所以最后选择了无参但是引用了this指针的构造函数。可见，对于构造函数的含参调用应该小心谨慎。 3)编程时，要不停得检验自己的输入与输出，必要的时候需要人工进行计算，以保证程序的运行按照预先的设想。 数据结构程序设计报告 学院： 班级： 学号： 姓名： 实验名称：二叉树的建立与遍历 一、实验目的： 1.掌握二叉树的二叉链表存储结构； 2.掌握二叉树创建方法； 3.掌握二叉树的先序、中序、后序的递归实现方法。 二、实验内容和要求： 创建二叉树，分别对该二叉树进行先序、中序、后序遍历，并输出遍历结果。 三、叉树的建立与遍历代码如下： #include };typedef struct tnode TNODE; TNODE *creat(void){ TNODE *root,*p;TNODE *queue[50];char data;struct tnode *lchild,*rchild; int front=0,rear=-1,counter=0;//初始队列中需要的变量front、rear和计数器counter char ch;printf(“建立二叉树，请输入结点:（#表示虚节点,!表示结束)n”); ch=getchar(); while(ch!='!'){ if(ch!='#') { p=(TNODE *)malloc(sizeof(TNODE)); p->data=ch; p->lchild=NULL; p->rchild=NULL;rear ; queue[rear]=p;//把非#的元素入队 if(rear==0)//如果是第一个元素，则作为根节点 { } else { if(counter%2==1)//奇数时与其双亲的左子树连接 { } if(counter%2==0)//偶数时与其双亲的右子树连接 { queue[front]->rchild=p;queue[front]->lchild=p;root=p;counter ; } } } } front ; counter ; else//为#时，计数，但不连接结点 { if(counter%2==0) front ;counter ; } ch=getchar();} return root;void preorder(TNODE *bt)//先序遍历 { if(bt!=NULL){ printf(“%c ”,bt->data);preorder(bt->lchild);preorder(bt->rchild); } } void inorder(TNODE *bt)//中序遍历 { if(bt!=NULL){ inorder(bt->lchild);printf(“%c ”,bt->data);inorder(bt->rchild); } } void postorder(TNODE *bt)//后序遍历 { if(bt!=NULL){ postorder(bt->lchild);postorder(bt->rchild);printf(“%c ”,bt->data); } } int main(){ TNODE *root; root=creat();printf(“递归先序遍历是:”); preorder(root); printf(“n”);printf(“递归中序遍历是：”);inorder(root);printf(“n”); } printf(“递归后序遍历是：”);postorder(root);printf(“n”);return 0; 四、程序运行结果： 五、程序设计指导： 1.创建二叉树的算法：首先对一般的二叉树，添加若干个虚结点使其成为完全二叉树，然后依次输入结点信息，若输入的结点不是虚结点，则建立一个新结点，若是第一个，则令其为根结点，否则将新结点链接至它的双亲结点上。如此重复下去，直至遇到输入结束符（自定）为止。为了使新结点能够与双亲结点正确相连，并考虑到这种方法中先建立的结点其孩子结点也一定先建立的特点，可以设置一个指针类型的数组构成的队列来保存已输入结点的地址，并使队尾(rear)指向当前输入的结点，队头(front)指向这个结点的双亲结点的前一个位置。由于根结点的地址放在队列的第一个单元里，所以当rear为奇数时，则rear所指的结点应作为左孩子与其双亲链接，否则rear所指的结点应作为右孩子与其双亲链接。若双亲结点或孩子结点为虚结点，则无须链接。若一个双亲结点与两个孩子链接完毕，则进行出队操作，使队头指针指向下一个待链接的双亲结点。 2.void preorder(TNODE *bt)函数：利用递归的思想，不断嵌套循环，读取结点元素，在每个循环中每次先读取，再进行进入下一个递归循环中。 3.void inorder(TNODE *bt)函数 ：利用递归的思想，不断嵌套循环，读取结点元素，在每个循环中每次先左子树，再读取结点元素，再进行进入下一个递归循环中。 4.void postorder(TNODE *bt)函数：利用递归的思想，不断嵌套循环，读取结点元素，在每个循环中每次先分别进入左右子树，再进行读取，再进行进入下一个递归循环中。 六、心得体会： 本次数据结构程序设计对我有一定的帮助。通过这次的实践，使我对数据结构这门课程有了更深入地了解。在写程序的过程中，我重复地读课本上的知识，并且渐渐领悟到数据结构编程的方法。在编程中，虽然遇到了一些困难，但我并不气馁。当程序运行出来时，我感到了快乐。总之，通过自己地探索和努力，思维得到了锻炼，编程能力也有了较大地改善。第二篇：实验报告：二叉树
第三篇：二叉树的遍历
第四篇：数据结构作业——二叉树
第五篇：二叉树遍历课程设计】
