第六章树
第一部分：知识点
知识脉络：
重点：二叉树的性质、：I树的各种遍历方法及它g1所确定的序列问的关系、
二又树上的基本运算算法
的实现、二又树的线索化方法，构造赂夫曼树的方法。
难点：二叉树上各种算法，特别是遍历的非递归算法的设计。
一、二叉树的遍历的非递归算法
1.先序遍历
先将根结点入栈，然后只要栈不空，先出栈，然后沿着左子针依次访问沿途经过的子树根结点，同时将右指针进栈（以便递归访问左子树后访问右子树），如此重复，直至栈为空。
void PreOrderBiTree(BitTree T)
{ SqStack S;
BitTree p;
InitStack(&S); /* 初始化一个空栈*/
Push(&S,T); /* 根结点指针进栈*/
while(!EmptyStack(S)) /* 栈为空时算法结束*/
{ Pop(S，&p); /* 弹栈，p指向(子树)根结点*/
while(p)
{ printf("%d ",p->data); /* 访问根结点*/
if(p->rchild) Push(S,p->rchild); /* 非空的右指针进栈*/
p=p->lchild; /* 沿着左指针访问，直到左指针为空*/ }
}
2.中序遍历
先沿着左指针走到最左下的结点同时将沿途经过的（子树）根结点指针进栈。当走到空指针时，出栈得到一个结点并访问，然后跳到右子树上。如此重复，直到指针为空并且栈为空为止。
void InOrderBitree(BitTree T)
{ SqStack S;
BitTree p;
InitStack(&S); /* 初始化一个栈*/
p=T; /* p指向根结点*/
while(p||!EmptyStack(S)) /* 当p为空且栈为空时算法结束*/
{ while(p)
{ Push(S,p);
p=p->lchild; /* 沿左指针走，沿途经过的(子树)根结点指针进栈*/ }
Pop(S，&p);
printf("%d ",p->data); /*当左指针为空时弹栈并访问该结点(子树根结点) */ p=p->rchild; /* 向右跳一步到右子树上继续进行遍历过程*/
}
}
3.后序遍历
void PostOrderBiTree(BitTree T)
{ SqStack S;
BitTree p,q;
InitStack(S);
p=T;q=NULL;
while(p||!EmptyStack(S))
{ if(p!=q)
{ while(p)
{ Push(S,p);
if(p->lchild) p=p->lchild;
else p=p->rchild;
}
}
if(S->top==S->base) break;
GetTop(S,&q);
if(q->rchild==p)
{ p=Pop(S);
printf("%d ",p->data);
}
else p=q->rchild;
}
二、线索二叉树
1、已知树T如下，画出它的三种线索二叉树
先序线索二叉树
（1）写出先序序列：ABDCEFG
（2）为度不是2结点添加指针。
若没有左孩子，添加左孩子指针并
指向直接前驱。
若没有右孩子，添加右孩子指针
并指向直接后继。
中序线索二叉树后序线索二叉树
中序序列：DBAFEGC 写出后序序列：DBFGECA
2、中序线索二叉树的存储结构
{
BiThrTree p=Thrt->lchild;
while(p!=Thrt)
{ while(p->ltag==0) p=p->lchild;
printf("%d ",p->data);
while(p->rtag==1&&p->rchild!=Thrt)
{ p=p->rchild;printf("%d ",p->data);}
p=p->rchild;
}
}
第二部分：习题
一、选择题
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 2.设有一表示算术表达式的二叉树（见右图）， 它所表示的算术表达式是（ ）。 C. (A*B+C)/(D*E+（F-G ）) D. A*B+C/D*E+F-G
3. 算术表达式a+b*（c+d/e ）的逆波兰式为（ ）
A ．ab+cde/*
B ．abcde/+*+
C ．abcde/*++
D ．abcde*/++ 4. 在下述结论中，正确的是（ ）。
①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换;
④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A ．①②③ B ．②③④ C ．②④ D ．①④
5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ） A ．9 B ．11 C ．15 D ．不确定
6. 一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）。 A ． 250 B ． 500 C ．254 D ．505 E ．以上答案都不对
7.设树T 的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T 中的叶子数为（ ）
A ．5
B ．6
C ．7
D ．8
8.设森林F 对应的二叉树为B ，它有m 个结点，B 的根为p,p 的右子树结点个数为n,森林F 中第一棵树的结点个数是（ ）
A ．m-n
B ．m-n-1
C ．n+1
D ．条件不足，无法确定
9.设森林F 中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F 对应的二叉树根结点的右子树上的结点个数是（ ）。
A ．M1
B ．M1+M2
C ．M3
D ．M2+M3
10. 一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点 A ．2h B ．2h-1 C ．2h+1 D ．h+1 11. 深度为h 的满m 叉树的第k 层有（ ）个结点。(1= A ．m k-1 B ．m k -1 C ．m h-1 D ．m h -1 12. 将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度（） A ．4 B ．5 C ．6 D ．7 13. 利用二叉链表存储树，则根结点的右指针是（ ）。 A ．指向最左孩子 B ．指向最右孩子 C ．空 D ．非空 14. 树的后根遍历序列等同于该树对应的二叉树的( ). A. 先序序列 B. 中序序列 C. 后序序列 15．若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( )遍历方法最合适。 A．前序 B．中序 C．后序 D．按层次 16. 在下列存储形式中，哪一个不是树的存储形式？（）。 A．双亲表示法 B．孩子链表表示法 C．孩子兄弟表示法 D．顺序存储表示法 17. 某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E 则前序序列是：（） A．E,G,F,A,C,D,B B．E,A,C,B,D,G,F C．E,A,G,C,F,B,D D．上面的都不对18. 上题的二叉树对应的森林包括多少棵树（）。 A．l B．2 C．3 D．概念上是错误的 19. 一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（） A．所有的结点均无左孩子 B．所有的结点均无右孩子 C．只有一个叶子结点 D．是任意一棵二叉树 20. 在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（） A．都不相同B．完全相同 C．先序和中序相同，而与后序不同 D．中序和后序相同，而与先序不同 21. 一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是：( ) A．不确定 B. 0 C. 1 D. 2 22. 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：( )。 A. 0 B. 1 C. 2 D. 不确定 23. 若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为( ) A.X的双亲 B.X的右子树中最左的结点 C.X的左子树中最右结点 D.X的左子树中最右叶结点 24. 引入二叉线索树的目的是（） A．加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一 25. 线索二叉树是一种（）结构。 A．逻辑 B．逻辑和存储 C．物理 D．线性 26. n个结点的线索二叉树上含有的线索数为（） A．2n B．n－l C．n＋l D．n 27. 二叉树在线索后，仍不能有效求解的问题是（）。 A．前（先）序线索二叉树中求前（先）序后继 B．中序线索二叉树中求中序后继C．中序线索二叉树中求中序前驱 D．后序线索二叉树中求后序后继 28. 如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就是T2中结点的（）。A．先序 B．中序 C．后序 D．层次序 29.设给定权值总数有n 个，其哈夫曼树的结点总数为( ) 。 A．不确定 B．2n C．2n+1 D．2n-1 30.下述编码中哪一个不是前缀码（）。 A．（00，01，10，11） B．（0，1，00，11） C．（0，10，110，111） D．（1，01，000，001） 二、填空题 1.在完全二叉树中，编号为i和j的两个结点处于同一层的条件是______。 2.一棵有n个结点的满二叉树有__(1)_个度为1的结点、有__(2)_个分支（非终端）结点和__(3)_个叶子，该满二叉树的深度为_(4)__。 3. 高度为K的完全二叉树至少有______个叶子结点。 4. 已知二叉树有50个叶子结点，则该二叉树的总结点数至少是______。 5. 设F是由T1,T2,T3三棵树组成的森林,与F对应的二叉树为B,已知T1,T2,T3的结点数分别为n1,n2和n3则二叉树B的左子树中有__(1)_个结点，右子树中有_(2)__个结点。 6. 如某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数为______。 7.对于一个具有n个结点的二元树，当它为一棵_(1)_二元树时具有最小高度，当它为一棵_(2)_时，具有最大高度。 8. 具有N个结点的二叉树，采用二叉链表存储，共有______个空链域。 9. 每一棵树都能唯一的转换为它所对应的二叉树。若已知一棵二叉树的前序序列是BEFCGDH，对称序列是FEBGCHD，则它的后序序列是_(1)__。设上述二叉树是由某棵树转换而成，则该树的先根次序序列是_(2)__。 10. 二叉树的先序序列和中序序列相同的条件是______。 11. 线索二元树的左线索指向其______，右线索指向其______。 12.若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是______。 13. 下列是先序遍历二叉树的非递归子程序，请阅读子程序（C语言与PASCAL语言过程功 能完全相同，任选其一），填充空格，使其成为完整的算法。 void example(b) btree *b; { btree *stack[20], *p； int top; if (b!=null) { top=1; stack[top]=b; while (top>0) { p=stack[top]; top--; printf(“%d”,p->data); if (p->rchild!=null) { (1)___; (2)___; } if (p->lchild!=null) (3)___; (4)__; } } } 14. 以下程序是二叉链表树中序遍历的非递归算法，请填空使之完善。二叉树链表的结点类型的定义如下： typedef struct node /*C语言/ {char data; struct node *lchild,*rchild;}*bitree; void vst(bitree bt) /*bt为根结点的指针*/ { bitree p; p=bt; initstack(s); /*初始化栈s为空栈*/ while(p || !empty(s)) /*栈s不为空*/ if(p) { push (s,p); (1)___; } /*P入栈*/ else { p=pop(s); printf(“%c”,p->data); (2)____; } /*栈顶元素出栈*/ } 15.由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序所缺的语句。 #define MAX 100 typedef struct Node {char info; struct Node *llink, *rlink; }TNODE; char pred[MAX],inod[MAX]; main(int argc,int **argv) { TNODE *root; if(argc<3) exit 0; strcpy(pred,argv[1]); strcpy(inod,argv[2]); root=restore(pred,inod,strlen(pred)); postorder(root); } TNODE *restore(char *ppos,char *ipos,int n) { TNODE *ptr； char *rpos; int k; if(n<=0) return NULL; ptr->info=(1)_______; for((2)_______ ; rpos k=(3)_______; ptr->llink=restore(ppos+1, (4)_______,k ); ptr->rlink=restore ((5)_______+k,rpos+1,n-1-k); return ptr; } postorder(TNODE*ptr) { if(ptr=NULL) return; postorder(ptr->llink); postorder(ptr->rlink); printf(“%c”,ptr->info); } 16、下面是中序线索树的遍历算法，树有头结点且由指针thr指向。树的结点有五个域，分 别为数据域 data，左、右孩子域 lchild、rchild和左、右标志域 ltag,rtag。规定，标志域为1是线索，O是指向孩子的指针。 inordethread(thr) {p=thr->lchild; while ((1)______) { while((2) _____) p= (3) ___; printf(p->data); while((4)_________) { p=(5)___；printf(p->data);} p= (6)_; } } 17、线索二叉树有数据域data，左右孩子域lchild和rchild，左右标志ltag及rtag，规定标志为1对应的孩子域是线索，0则为指向孩子的指针。规定在储存线索二叉树时，完成下面中序线索化过程。（存储线索二叉树，不增加头结点，只在原有的由tree指向的二叉树中增加线索，此处也不考虑c语言的具体语法与约定，线索化前所有的标志tag都是0）。 /* pre是同tree类型相同的指针，初值是null */ thread_inorder (tree) { if(tree!=null) { thread_inorder((1)____); if(tree->lchild==(2)______) { tree->ltag=1; tree->lchild=pre; } if((3)___ == null){ (4)_______; (5)_______;} pre=p; thread-inorder((6)_______); } } 18、如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，请在算法空格处填上正确的语句。设线索二叉树的结点数据结构为(lflag,left,data,right,rflag)，其中： lflag= 0，left 指向其左孩子，lflag= 1，left 指向其前驱；rflag=0，right 指向其右孩子，rflag=1，right 指向其后继。 prior(node,x) { if (node !=null) if ((1)_____ ) *x=node->right; else *x=node->left; } next(bt, node, x) /*bt是二叉树的树根*/ {(2)_____; if (node!=bt && node!=null) if (node->rflag) (3)_______ ； else {do t=*x; (4)_______;while (*x==node); *x=t; } } 三、应用题 1、从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。 2、一个深度为L的满K叉树有以下性质：第L层上的结点都是叶子结点，其余各层上每个结点都有K棵非空子树，如果按层次顺序从1开始对全部结点进行编号，求：1）各层的结点的数目是多少？ 2）编号为n的结点的双亲结点（若存在）的编号是多少？ 3）编号为n的结点的第i 个孩子结点（若存在）的编号是多少？ 4）编号为n的结点有右兄弟的条件是什么？如果有，其右兄弟的编号是多少？ 请给出计算和推导过程。、 3、已知A[1..N]是一棵顺序存储的完全二叉树，如何求出A[i]和A[j]的最近的共同祖先？ 4、若一棵树中有度数为1至m的各种结点数为n1,n2,…,n m(n m表示度数为m的结点个数)请推导出该树中共有多少个叶子结点n0的公式。 5、试证明,在具有n(n>=1)个结点的m次树中,有n(m-1)+1个指针是空的。 6、①试找出满足下列条件的二叉树 1）先序序列与后序序列相同 2）中序序列与后序序列相同 3）先序序列与中序序列相同 4）中序序列与层次遍历序列相同 ②已知一棵二叉树的中序序列和后序序列分别为DBEAFIHCG和DEBHIFGCA，画出这棵二叉树。 7、将下列由三棵树组成的森林转换为二叉树。（只要求给出转换结果） 8、设一棵二叉树的先序、中序遍历序列分别为 先序遍历序列： A B D F C E G H 中序遍历序列： B F D A G E H C （1）画出这棵二叉树。 （2）画出这棵二叉树的后序线索树。 （3）将这棵二叉树转换成对应的树（或森林）。 9、已知一个森林的先序序列和后序序列如下，请构造出该森林。 先序序列：ABCDEFGHIJKLMNO 后序序列：CDEBFHIJGAMLONK 10、一棵二叉树的先序、中序和后序序列分别如下，其中有一部分为显示出来。试求出空格处的内容，并画出该二叉树。 先序序列: _ B F I C E H G 中序序列：D K F I A E J C 后序序列： K F B H J G A 11、设用于通讯的电文仅由8个字母组成，他们在电文中出现的频率分别为0.30，0.07，0.10，0.03，0.20，0.06,0.22，0.02，试设计哈夫曼树及其编码。 四、算法设计题 1．假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树BT中，写出计算该算术表达式值的算法。 2. 假定用两个一维数组L[N]和R[N]作为有N个结点1，2,…， N的二元树的存储结构。L[i]和R[i]分别指示结点 i的左儿子和右儿子；L[i]=0（R[i]=0）表示i的左（右）儿子为空。试写一个算法，由L和R建立一个一维数组T[n]，使T[i]存放结点i的父亲；然后再写一个判别结点U是否为结点V的后代的算法。 3. 要求二叉树按二叉链表形式存储 写一个判别给定的二叉树是否是完全二叉树的算法。 完全二叉树定义为：深度为K，具有N个结点的二叉树的每个结点都与深度为K的满二叉树中编号从1至N的结点一一对应。此题以此定义为准。 4.有n个结点的完全二叉树存放在一维数组A[1..n]中，试据此建立一棵用二叉链表表示的二叉树 5. 二叉树的动态二叉链表结构中的每个结点有三个字段：data ，lchild ，rchild 。 其中指针lchild 和rchild 的类型为bitre 。静态二叉链表是用数组作为存储空间，每个数组元素存储二叉树 的一个结点，也有三个字段：data ，lchild ，rchild 。所不同的是，lchild 和rdhild 为 int 型，分别用于存储左右孩子的下标，如果没有左右孩子，则相应的值为0。 例如，下面左图所示的二叉树的静态二叉链表如右图所示。 编写算法由二叉树的动态二叉链表构造出相应的静态二叉链表a[1..n]，并写出其调用形式和有关的类型描述。其中n 为一个确定的整数。 6.假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深度的算法。（注:已知树中结点数） 7. 以孩子兄弟链表为存储结构，请设计递归和非递归算法求树的深度。 8. 在二叉树中查找值为x 的结点，试编写算法打印值为x 的结点的所有祖先，假设值为x 的结点不多于一个，最后试分析该算法的时间复杂度。 9. 已知一棵二叉树按顺序方式存储在数组A[1..n]中。设计算法，求出下标分别为i 和j 的两个结点的最近的公共祖先结点的值。 10. 设一棵二叉树的结点结构为 (LLINK,INFO,RLINK),ROOT 为指向该二叉树根结点的指针，p 和q 分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR （ROOT ，p,q,r ）,该算法找到p 和q 的最近共同祖先结点r 。 11、设一棵完全二叉树使用顺序存储在数组bt[1..n]中,请写出进行非递归的前序遍历算法。 #include { inorder(p->lchild); printf("%c ",p->data); inorder(p->rchild); } } void postorder(TREE *p) //后序遍历 { if (p!=NULL) { postorder(p->lchild); postorder(p->rchild); printf("%c ",p->data); } } void shu(TREE *p,int len) //数的形状{ if (p!=NULL) { shu(p->lchild,len+1); for (int i=1;i<=4*len;i++) { printf(" "); } printf("%c",p->data); printf("------\n"); shu(p->rchild,len+1); } } int shendu(TREE *p) //计算深度 { int l,r; if (p==NULL) { return 0; } l=shendu(p->lchild)+1; r=shendu(p->rchild)+1; if (l>=r) //左右子树比较return l; else /* *题目：按屏幕提示用前序方法建立一棵二叉树，并能按凹入法显示二叉树结构。 * 编写前序遍历、中序遍历、后序遍历、层次遍历程序。 * 编写求二叉树的叶结点数、总结点数和深度的程序。 * 设计一个选择式菜单，以菜单方式选择下列操作。 * 二叉树子系统 * *************************** **** * * 1 -- 建二叉树* * * 2 -- 凹入显示* * * 3 -- 先序遍历* * * 4 -- 中序遍历* * * 5 -- 后序遍历* * * 6 -- 层次遍历* * *7 -- 求叶子数* * *8 -- 求结点数* * *9 -- 求树深度* * *0 -- 返回* * *************************** **** * 请选择菜单号（0--9） */ #include 目录 摘要 (1) ABSTRACT (2) 第一章绪论 (3) 1.1 背景介绍 (3) 1.2 本文的主题 (4) 第二章预备知识 (5) 2.1 期权 (5) 2.2二叉树方法 (6) 2.2.1 方法概述 (6) 2.2.2 二叉树方法的优点和缺点 (9) 2.2.3 风险中性定价 (9) 2.3 Black-Scholes 期权定价模型 (11) 错误!未定义书签。 错误!未定义书签。 错误!未定义书签。 错误!未定义书签。 第三章本论 (14) 3.1期权定价的二叉树模型 (14) ................................................ 错误!未定义书签。 ................................................ 错误!未定义书签。 ................................................ 错误!未定义书签。 ................................................ 错误!未定义书签。 3.2 例子模拟计算和结果分析 (18) 3.3 模型改进——三叉树 (19) 第四章结论...................................... 错误!未定义书签。谢辞及参考文献 (23) 谢辞 (23) 参考文献 (23) 附录 (25) 计算过程中涉及算法 (25) 摘要 Black-Scholes 期权定价模型为期权定价尤其是欧式期权定价提供了良好的解析结果，而Black-Scholes 公式是此模型的核心，但是此公式并不能很好地求解出在很多衍生模型例如亚式期权以及美式期权中的解析解。二叉树方法作为一种数值方法，同时也是图论中一种重要方法，应用于期权定价问题中，它有了更特别的演变。本文利用二叉树方法计算期权定价的数值解，用二叉树方法迭代多次，求出较为准确的期权价格。通过B-S公式得出的结果与二叉树方法得到的结论对比，分析二叉树方法模拟的优点和缺点。同时，我们还要研究二叉树模拟的步数与预测结果和精度间的关系，从而更加深入了解二叉树方法。然而，我们在模型中设立了许多条件，这些都使模型离真实情况越来越远，我们必须不断发展模型，完善模型。三叉树方法正是二叉树方法的合适补充。 关键词：二叉树方法，Black-Scholes 模型，风险中性定价 实验报告 课程名称数据结构 实验项目实验三--创建一个二叉树并输出三种遍历结果 系别■计算机学院 _________________ 专业_______________ 班级/学号_____________ 学生姓名___________ 实验日期— 成绩______________________________ 指导 教师 实验题目：实验三创建一个二叉树并输出三种遍历结果 实验目的 1）掌握二叉树存储结构； 2）掌握并实现二叉树遍历的递归算法和非递归算法; 3）理解树及森林对二叉树的转换; 4）理解二叉树的应用一哈夫曼编码及WPL计算。 实验内容 1）以广义表或遍历序列形式创建一个二叉树，存储结构自选； 2）输出先序、中序、后序遍历序列； 3）二选一应用题：1）树和森林向二叉树转换；2）哈夫曼编码的应用问题。 题目可替换上述前两项实验内容） 设计与编码 1）程序结构基本设计框架 （提示：请根据所选定题目，描述程序的基本框架，可以用流程图、界面描述图、 框图等来表示） 2）本实验用到的理论知识遍历二叉树，递归和非递归的方法 （应用型 (提示：总结本实验用到的理论知识，实现理论与实践相结合。总结尽量简明扼要，并与本次实验密切相关，要求结合自己的题目并阐述自己的理解和想法) 3) 具体算法设计 1) 首先，定义二叉树的存储结构为二叉链表存储，每个元素的数 据类型Elemtype,定义一棵二叉树，只需定义其根指针。 2) 然后以递归的先序遍历方法创建二叉树，函数为CreateTree()，在输 入字符时要注意,当节点的左孩子或者右孩子为空的时候,应当输入一 个特殊的字符(本算法为“ #”),表示左孩子或者右孩子为空。 3) 下一步,创建利用递归方法先序遍历二叉树的函数,函数为 PreOrderTreeQ,创建非递归方法中序遍历二叉树的函数，函数为 InOrderTree()，中序遍历过程是：从二叉树的根节点开始，沿左子树 向下搜索，在搜索过程将所遇到的节点进栈；左子树遍历完毕后，从 栈顶退出栈中的节点并访问；然后再用上述过程遍历右子树，依次类 推，指导整棵二叉树全部访问完毕。创建递归方法后序遍历二叉树的 函数，函数为LaOrderTree()。 (提示：该部分主要是利用C、C++ 等完成数据结构定义、设计算法实现各种操作，可以用列表分步形式的自然语言描述，也可以利用流程图等描述) 4) 编码 #include 摘要 Matlab是一种用于算法开发,数据可视化，数据分析以及数值计算的高级技术计算语言和交互式环境。MATLAB是当今最优秀的科技应用软件之一，利用MATLAB 对层次分析法的判断、分析和计算过程进行处理后，为决策者提供方便友好的对话界面。只要决策者在MATLAB软件中输入自己的层次结构方案和两两对比的判断矩阵后能迅速得出相应的结果，为解决实际问题提供一个快捷的方法。从而提高人们的决策效率，同时也为科技工作者使用层次分析法提供一种新思路。本文是利用matlab的强大功能来构造最优二叉树。二叉树是一种非常重要以及常见的数据结构，不仅在计算机系统中运用广泛，而且在日常生活中也有一定的应用。本文概述了二叉树的数据结构以及使用matlab来模拟出二叉树的数据结构，从而来实现二叉树的插入，删除，查询等常用功能。 关键词：Matlab；二叉树；数据结构； ABSTRACT Matlab is used for algorithm development, data visualization, data analysis and numerical calculation of the senior technical computing language and interactive environment. Matlab is the most outstanding application of science and technology, using MATLAB to determine the right level of analysis, analysis and computation processing, in order to provide decision makers with convenient user-friendly dialog interface. When the decision-makers in MATLAB software, enter their own hierarchy of the program and judgment matrix to determine quickly after the corresponding results obtained, in order to solve practical problems to provide a quick method. Thereby enhancing the efficiency of people's decision-making, but also for the scientific and technological workers to use AHP to provide a new idea.This article is using matlab to construct optimal binary tree. Binary Tree is a very important and common data structures, it is widely used in the computer system. This article outlines the binary tree data structure and the use of matlab to simulate a binary tree data structure, in order to achieve the binary tree insertion, deletion, query and other commonly used functions. Key words：Matlab；binary tree；data struction； #include else { if (!(T = new BiTreeNode)) exit(OVERFLOW); T->data = ch; // 生成根结点 CreateBiTree(T->lchild); // 构造左子树 CreateBiTree(T->rchild); // 构造右子树 } } // CreateBiTree void PreOrder(BiTree &T)//递归函数：先序遍历以T为根的二叉树。 { if(T !=NULL) //递归结束条件 { cout< void InOrder(BiTree &T)//递归函数：中序次序遍历以T为根的子树。 { if(T !=NULL) //NULL是递归终止条件 { InOrder(T->lchild); //中序遍历根的左子树 cout< 长春建筑学院《数据结构》课程设计（论文） 基于二叉树遍历系统设计与实现Binary tree traversal System Design and Implementation 年级: 学号: 姓名: 专业: 指导老师: 二零一三年十二月 摘要 针对现实世界中许多关系复杂的数据，如人类社会的家谱，各种社会组织机构,博弈交通等复杂事物或过程以及客观世界中广泛存在的具有分支关系或层次特性的对象．如操作系统的文件构成、人工智能和算法分析的模型表示以及数据库系统的信息组织形式等，用线性结构难以把其中的逻辑关系表达出来，必须借助于数和图这样的非线性结构，因此在以模拟客观世界问题，解决客观世界问题为主要任务的计算机领域中树型结构是信息的一种重要组织形式，树有着广泛应用。在树型结构的应用中又以二叉树最为常用。 二叉树是一种非常重要的非线性结构，所描述的数据有明显的层次关系，其中的每个元素只有一个前驱，二叉树是最为常用的数据结构，它的实际应用非常广泛，二叉树的遍历方式有三种，前序遍历，中序遍历，后序遍历，先序遍历的顺序为：NLR 先根结点，然后左子树，右子树；中序遍历顺序为；LNR先左子树，然后根结点，右子树；后序遍历顺序为：LRN先左子树，然后右子树，根结点。由前序和中序遍历，有中序和后序遍历序列可以唯一确定一棵二叉树。 对于给几个数据的排序或在已知的几个数据中进行查找，二叉树均能提供一种十分有效的方法，比如在查找问题上，任何借助于比较法查找长度为Ⅳ的一个序表的算法，都可以表示成一株二叉树。反之，任何二叉树都对应一个查找有序表的有效方法根据树的数学理论，对于算法分析的某些最有启发性的应用，是与给出用于计算各种类型中不同树的数目的公式有关的。 本文对二叉树以及二叉树的各种功能做介绍以及写出一些基本的程序，让读者对二叉树的理解有更好的效果。 关键词：二叉树；左子树；右子树 二叉树 定义[二叉树] 二叉树（binary tree）t 是有限个元素的集合（可以为空）。当二叉树非空时，其中有一个称为根的元素，余下的元素（如果有的话）被组成2个二叉树，分别称为t的左子树和右子树。 二叉树和树的根本区别是： ? 二叉树可以为空，但树不能为空。 ? 二叉树中每个元素都恰好有两棵子树（其中一个或两个可能为空）。而树中每个元 素可有若干子树。 ? 在二叉树中每个元素的子树都是有序的，也就是说，可以用左、右子树来区别。而 树的子树间是无序的。 像树一样，二叉树也是根节点在顶部。二叉树左(右)子树中的元素画在根的左(右)下方。在每个元素和其子节点间有一条边。 二叉树的特性 特性1包含n (n> 0 )个元素的二叉树边数为n-1。 证明: 二叉树中每个元素(除了根节点) 有且只有一个父节点。在子节点与父节点间有且只有一条边，因此边数为n-1。 二叉树的高度（h e i g h t）或深度（d e p t h）是指该二叉树的层数。 特性2若二叉树的高度为h，h≥0，则该二叉树最少有h个元素，最多有2h - 1个元素。 证明: 因为每一层最少要有1个元素，因此元素数最少为h。每元素最多有2个子节点，则第i 层节点元素最多为2i - 1个，i > 0。h= 0时，元素的总数为0，也就是20 - 1。当h > 0 时，元素的总数不会超过. 特性3 包含n 个元素的二叉树的高度最大为n，最小为[l o g2 (n+ 1 )]。 证明: 因为每层至少有一个元素，因此高度不会超过n。由特性2，可以得知高度为h 的二叉树最多有2h-1个元素。因为n≤2h-1，因此h≥log2 (n+ 1 )。由于h 是整数，所以h≥[l o g2 (n+ 1 )]。 当高度为h 的二叉树恰好有2h - 1个元素时，称其为满二叉树（full binary tree） 假设从满二叉树中删除k个元素，其编号为2h -i, 1≤i≤k，所得到的二叉树被称为完全二叉树（complete binary tree） 在完全二叉树中，一个元素与其孩子的编号有非常好的对应关系。其关系在特性4中给出。 特性4 设完全二叉树中一元素的序号为i, 1≤i≤n。则有以下关系成立： 1) 当i = 1时，该元素为二叉树的根。若i > 1，则该元素父节点的编号为?i / 2?。 2) 当2i >n时，该元素无左孩子。否则，其左孩子的编号为2i。 3) 若2i + 1 >n，该元素无右孩子。否则，其右孩子编号为2i + 1。 证明 :通过对i 进行归纳即可得证。 # include 《数据结构》实验报告 姓名： 班级： 学号： 一、算法简介 简单二叉树的创建，删除，查找 二、基本原理 定义节点的结构体，内部成员包括数据data，父节点指针*parent，左子节点指针*lchild，右子结点指针*rchild，以及指针next，然后通过add()和move()函数建立一个二叉树；最后通过del()删除整个二叉树。 三、实现步骤 第一，创建二叉树结点 第二，创建构造二叉树的函数add()和move().在add()中调用move()；然后在主函数中初始化二叉树为7个结点（通过建立二叉树的函数）。 创建的二叉树如图： 1 2 3 4 5 6 第三，最后一个个通过查找的方式进行删除结点。该方式不局限于顺序删除，可以 从任何一个结点开始删除，删除后会通过move重新构建，直到删除为止。 四、实验结果如下图 五、结论 本套算法在创建二叉树同时增加了有序检查，通过创建和删除一棵完全二叉树，还可以实现查找结点的功能，未实现遍历、插入、修改、替换等算法，程序较为简单，但是代码工整严谨，时间复杂度和空间复杂度可忽略不计。 六、源程序 #include void move(struct node *p,struct node *s) { while(0) { if(s->data > p->data ) { if(p->rchild==NULL) { p->rchild=s; break; } else { p=p->rchild; } } else { if(p->lchild==NULL) { p->lchild=s; break; } } } } void add(int x) { struct node *s=malloc(sizeof(struct node)),*p=malloc(sizeof(struct node)); s->data=x; s->lchild=NULL; s->rchild=NULL; s->parent=NULL; if(head==NULL) { head=s; } else { p=head; move(p,s); } 5.1树的概念 树的递归定义如下：（1）至少有一个结点（称为根）（2）其它是互不相交的子树 1.树的度——也即是宽度，简单地说，就是结点的分支数。以组成该树各结点中最大的度作为该树的度，如上图的树，其度为3;树中度为零的结点称为叶结点或终端结点。树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。 2.树的深度——组成该树各结点的最大层次，如上图，其深度为4； 3.森林——指若干棵互不相交的树的集合，如上图，去掉根结点A，其原来的二棵子树T1、T2、T3的集合{T1,T2,T3}就为森林； 4.有序树——指树中同层结点从左到右有次序排列，它们之间的次序不能互换，这样的树称为有序树，否则称为无序树。 5.树的表示 树的表示方法有许多，常用的方法是用括号：先将根结点放入一对圆括号中，然后把它的子树由左至右的顺序放入括号中，而对子树也采用同样的方法处理；同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。如上图可写成如下形式： (A(B(E(K,L),F),C(G),D(H(M),I,J))) 5. 2 二叉树 1.二叉树的基本形态： 二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态： (1)空二叉树——(a)； (2)只有一个根结点的二叉树——(b)； (3)右子树为空的二叉树——(c)； (4)左子树为空的二叉树——(d)； (5)完全二叉树——(e) 注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。 2.两个重要的概念： (1)完全二叉树——只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树； (2)满二叉树——除了叶结点外每一个结点都有左右子女且叶结点都处在最底层的二叉树,。 如下图： 完全二叉树 1页 #include "stdio.h" #include "stdlib.h" #define STACK_INIT_SIZE 100 //栈存储空间初始分配量 #define STACKINCREMENT 10 //存储空间分配增量 //------二叉树的存储结构表示------// typedef struct BiTNode{ int data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; //-----顺序栈的存储结构表示------// typedef struct{ BiTree *top; BiTree *base; int stacksize; }SqStack; //*************************************************** //构造一个空栈s SqStack *InitStack(); //创建一颗二叉树 BiTree CreatBiTree(); //判断栈空 int StackEmpty(SqStack *S); //插入元素e为新的栈顶元素 void Push(SqStack *S,BiTree p); //若栈不为空，则删除s栈顶的元素e，将e插入到链表L中void Pop(SqStack *S,BiTree *q); //非递归先序遍历二叉树 void PreOrderTraverse(BiTree L); //非递归中序遍历二叉树 void InOrderTraverse(BiTree L); //非递归后序遍历二叉树 void PostOrderTraverse(BiTree L); //递归后序遍历二叉树 void PostOrder(BiTree bt); //递归中序遍历二叉树 void InOrder(BiTree bt); //递归先序遍历二叉树 void PreOrder(BiTree bt); //*************************************************** 数据结构二叉树基本操作 (1). // 对二叉树的基本操作的类模板封装 //------------------------------------------------------------------------------------------------------------------------ #include 创建二叉树的三种算法： 1、结构体定义： struct node{ struct node *lchild; struct node *rchild; char ch; }; 2、算法部分 1）递归创建二叉树（无返回值法）： void create(struct node **T) { char ch; std::cin>>ch; if( ch == ‘#’) *T = NULL; else { *T = (struct node *)malloc(sizeof(struct node)); *T->ch = ch; create(&(*T)->lchild); create(&(*T)->rchild); } } 搭配上主函数即可使用： int main(void) { struct node *tree; create(&tree); return 0; } 2 ) 递归创建二叉树（有返回值）： struct node *create(struct node *T) { char ch; std::cin>>ch; if( ch != ‘#’) { T = (struct node *)malloc(sizeof(struct node)); T->ch = ch; T->lchild = create(T->lchild); T->rchild = create(T->rchild); return T; } return NULL; } 搭配主函数即可使用： int main(void) { struct node T,*head; head = create(&T); return 0; } 3 ) 非递归创建树： struct node *create() { char ch[20]; int i = 0, flag = 0 ,top = 0; struct node *tree, *head, *stack[20], *st; std::cin>>ch; tree = (struct node *)malloc(sizeof(struct node)); head=tree; tree->data = ch[i]; tree->lchild = NULL; tree->rchild = NULL; stack[top++] = tree; int a = 0; i++; while(i 平衡二叉树构造方法 平衡二叉树 对于二叉查找树，尽管查找、插入及删除操作的平均运行时间为O(logn)，但是它们的最差运行时间都是O(n),原因在于对树的形状没有限制。 平衡二叉树又称为AVL树，它或者是一棵空树，或者是有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左右子树的深度之差的绝对值不超过1。二叉树的的平衡因子BF为：该结点的左子树的深度减去它的右子树的深度，则平衡二叉树的所有结点的平衡因子为只可能是：-1、0和1 一棵好的平衡二叉树的特征： （1）保证有n个结点的树的高度为O(logn) （2）容易维护，也就是说，在做数据项的插入或删除操作时，为平衡树所做的一些辅助操作时间开销为O(1) 一、平衡二叉树的构造 在一棵二叉查找树中插入结点后，调整其为平衡二叉树。若向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性。首先要找出插入新结点后失去平衡的最小子树根结点的指针。然后再调整这个子树中有关结点之间的链接关系，使之成为新的平衡子树。当失去平衡的最小子树被调整为平衡子树后，原有其他所有不平衡子树无需调整，整个二叉排序树就又成为一棵平衡二叉树 1.调整方法 （1）插入点位置必须满足二叉查找树的性质，即任意一棵子树的左结点都小于根结点，右结点大于根结点 （2）找出插入结点后不平衡的最小二叉树进行调整，如果是整个树不平衡，才进行整个树的调整。 2.调整方式 （1）LL型 LL型：插入位置为左子树的左结点，进行向右旋转 由于在A的左孩子B的左子树上插入结点F，使A的平衡因子由1变为2，成为不平衡的最小二叉树根结点。此时A结点顺时针右旋转，旋转过程中遵循“旋转优先”的规则，A结点替换D结点成为B结点的右子树，D结点成为A结点的左孩子。 （2）RR型 RR型：插入位置为右子树的右孩子，进行向左旋转 由于在A的右子树C的右子树插入了结点F，A的平衡因子由-1变为-2，成为不平衡的最小二叉树根结点。此时，A结点逆时针左旋转，遵循“旋转优先”的规则，A结点替换D结点成为C的左子树，D结点成为A的右子树。 （3）LR型 LR型：插入位置为左子树的右孩子，要进行两次旋转，先左旋转，再右旋转；第一次最小不平衡子树的根结点先不动，调整插入结点所在的子树，第二次再调整最小不平衡子树。 由于在A的左子树B的右子树上插入了结点F，A的平衡因子由1变为了2，成为不平衡的最小二叉树根结点。第一次旋转A结点不动，先将B的右子树的根结点D向左上旋转提升到B结点的位置，然后再把该D结点向右上旋转提升到A结点的位置。 （4）RL型 RL型：插入位置为右子树的左孩子，进行两次调整，先右旋转再左旋转；处理情况与LR 类似。 封皮 （按学校要求手工填写） 成绩评定表 课程设计任务书 摘要 树结构在客观世界中广泛存在，如族谱、各种社会组织机构等都可以用树形结构来表示；树结构在计算机中应用也很广泛，如文件夹；其中二叉树结构是比较常用的一种数据结构，简单来说每个结点最多有两个孩子。本文采用C++语言来描述二叉树类模板的设计并实现其功能，并且采用VS2010应用程序来实现程序。 关键词：二叉树类模板；MFC 目录 1 需求分析 (1) 2 算法基本原理 (1) 3 类设计 (1) 4 基于控制台的应用程序 (2) 4.1类的接口设计 (2) 4.2类的实现 (3) 4.3主函数设计 (8) 4.4基于控制台的应用程序测试 (9) 5 基于MFC的应用程序 (10) 5.1基于MFC的应用程序设计 (10) 5.1.1 MFC程序界面设计 (11) 5.1.2 MFC程序代码设计 (13) 5.2基于MFC的应用程序测试 (17) 结论 (20) 参考文献 (21) 1需求分析 进行二叉树类模板的设计并实现,数据元素可以是char,int,float等多种数据类型,包括以下功能: （1）采取顺序存储结构或链式存储结构实现二叉树的存储; （2）实现二叉树的建树; （3）实现二叉树的前序、中序、后序遍历； （4）能够求解二叉树的结点总数和叶子结点总数； （5）能够求解二叉树的高度； （6）将上述功能作为类的成员函数实现，编写主函数测试上述功能。 整个二叉树类模板程序中的存储采用的是链式存储结构。在整个二叉树类中所有数据成员和成员函数均采用公有方式，类中有一个二叉树结点的定义，有建立二叉树的成员函数，有先序、中序、后序遍历的成员函数，有求解结点数、叶子节点数、二叉树深度的成员函数，它的功能在类里定义一个调用各个成员函数的成员函数来实现对二叉树的操作，然后在主函数中通过对模板的实例化产生对象，用对象调用成员函数的方式实现预期功能。 2算法基本原理 一颗二叉树有许多个结点组成，每个结点有三个区域分别存有数据和它的左右孩子指针。 大体思路：先构造一棵二叉树，然后依次实现前序、中序、后序遍历，统计二叉树的结点总数，统计二叉树的叶子结点数，求出二叉树的高度这些功能。 在主函数中实例化char,int,float数据类型的类对象，然后根据类对象来实现功能。 3 类设计 BiTree.h文件 #include else { if (!(T = new BiTreeNode)) exit(OVERFLOW); T->data = ch; // 生成根结点 CreateBiTree(T->lchild); // 构造左子树 CreateBiTree(T->rchild); // 构造右子树 } } // CreateBiTree void PreOrder(BiTree &T)//递归函数：先序遍历以T为根的二叉树。 { if(T !=NULL) //递归结束条件 { cout< void InOrder(BiTree &T)//递归函数：中序次序遍历以T为根的子树。 { if(T !=NULL) //NULL是递归终止条件 { InOrder(T->lchild); //中序遍历根的左子树 cout< 数据结构-二叉树的建立与遍历 《数据结构》实验报告 ◎实验题目:二叉树的建立与遍历 ◎实验目的：1、掌握使用Visual C++6.0上机调试程序的基本方法； 2、掌握二叉树的存储结构和非递归遍 历操作的实现方法。 3、提高自己分析问题和解决问题的能 力，在实践中理解教材上的理论。 ◎实验内容：利用链式存储结构建立二叉树，然后先序输出该二叉树的结点序列，在在本实验中不使用递归的方法，而是用一个栈存储结点的指针，以此完成实验要求。 一、需求分析 1、输入的形式和输入值的范围：根据提示，输入二叉树的括号表示形式，按回车结束。 2、输出的形式：输出结果为先序遍历二叉树所得到的结点序列。 3、程序所能达到的功能：输入二叉树后，该程序可以建立二叉树的链式存储结构，之后按照一定的顺序访问结点并输出相应的值，从而完成二叉树的先序遍历。 4、测试数据： 输入二叉树的括号表示形式:A(B(D(,G)),C(E,F)) 先序遍历结果为:ABDGCEF 是否继续?（是,输入1;否,输入0）:1 输入二叉树的括号表示形式: 二叉树未建立 是否继续?（是,输入1;否,输入0）:0 Press any key to continu e 二概要设计 1、二叉树的链式存储结构是用一个链表来存储一棵二叉树，二叉树中每一个结点用链表中的一个链结点来存储。 每个结点的形式如下图所示。 其中data表示值域，用于存储对应的数据元素，lchild和rchild分别表示左指针域和右指针域，用于分别存储左孩子结点和右孩子结点的存储位置。 2、二叉树的建立 本程序中利用数组存储所输入的二叉树，然后从头到尾扫描数组中的每一个字符根据字符的不同分别执行不同的操作，并用一个存储结点指针的栈辅助完成。在扫描前先申请一个结点作为根结点，也是当前指针所指结点，在二叉树的建立的过程中，每次申请一个新结点，需对其进行初始化，即令lchild域和rchild域为空。按照本程序的思路，二叉树A（B（D（，G）），C（E，F））的链式存储结构如下图所示。二叉树建立的具体过程见详细设计部分。 3、二叉树的先序遍历 在二叉树的先序遍历过程中也需利用一个存储结点指针的栈辅助完成，初始时栈为空，二叉树遍历结束后栈也为空，所以在开始时将头结点入栈，之后根据当前指针所指结点的特性的不同执行不同的操作，以栈空作为二叉树遍历的结束条件。二叉树先序遍历的具体过程见详细设计部分。二叉树的建立及其应用程序代码
数据结构：二叉树子系统
基于二叉树模型的期权定价
创建一个二叉树并输出三种遍历结果
基于matlab构造最优二叉树
C++创建二叉树及操作
基于二叉树遍历系统设计与实现
数据结构C++树与二叉树
二叉树的单分支结点个数(精)
简单二叉树的创建,删除,查找
各类型二叉树例题说明
二叉树的建立及几种简单的遍历方法
数据结构——二叉树基本操作源代码
创建二叉树的三种算法(递归和非递归)
平衡二叉树 构造方法(绝妙)
二叉树类模板的设计与实现
C++创建二叉树及操作
数据结构-二叉树的建
相关主题
文本预览