数据结构教程--树的遍历及二叉树.ppt

A B D C E A(B(C,D(E),F)) A ^ ^ ^ 读A 读( A地址 p F 读B B ^ ^ ^ p A(B(C,D(E),F)) 读( B A 读C C ^ ^ ^ p 读, 取栈顶值给q q=‘B’ A ^ ^ ^ B ^ ^ ^ C ^ ^ ^ B A A(B(C,D(E),F)) 读D D ^ ^ ^ p 读( D B A 读E E ^ ^ ^ p 读) 出栈并将值送给q q=‘D’ D ^ ^ ^ E ^ ^ ^ B A #include stdio.h #include ctype.h #define MAXM 3 #define MAXN 100 struct node { char data; struct node *child[MAXM]; }; typedef struct node NODE; char a[MAXN]; int m; NODE *kh_tree(a,m) char a[ ]; int m; { NODE *stack[MAXN],*p=NULL,*q; char ch; int i,k=0,top=0; ch=a[0]; while (ch!=‘\0’) {if (isalpha(ch)) { p=(NODE*) malloc(sizeof(NODE)); p-data=ch; for(i=0;im;i++) p-child[i]=NULL;} else switch(ch) {case ‘(‘: stack[top++]=p; break; case ‘,’: q=stack[top-1]; i=-1; while (q-child[++i]!=null) ; q-child[i]=p; break; case’)’: q=stack[--top]; i=-1; while (q-child[++i]!=null); q-child[i]=p; p=q;} ch=a[++k]; } return(p); } 1.一棵共有n个结点的树,其中所有分枝结点的度 均为k,求该树中叶子结点的个数. 2.试证明:在具有n个结点的m次树中,有n(m-1)+1个 指针是空的. 作业 1.一棵3次有序树其前序,后序的遍历结果为: 前序: ABECFGHD 后:EBFHGCDA 则该3次有序树用图形表示应为什么? 2.已知有序树的层号表示,用图形表示该有序树. (5,A)(10,B)(20,E)(10,C)(15,F)(15,G)(18,H)(10,D) 二叉树 是n=0个结点的有穷集合T n=0时,称该二叉树为空二叉树 n0时,它包含一个根结点以及二棵不相交的分别称之为左子树和右子树的二叉树 与树的区别: 二叉树可以为空 树不能为空 与二次有序树的区别: 严格区分左右孩子 包含三个结点的二叉树 可能具有多少种形态? A B C D F G E 满二叉树: 若一棵二叉树中任何结点,或者是叶子结点, 或者有两棵非空子树,并且叶子结点都集中 在二叉树的最下一层 A B C D F E 完全二叉树(拟满树) A B C D E 若一棵二叉树中最多只有最下面两层的结点的度数 可以小于2,并且最下面一层的结点都依次排列在该 层最左边的位置 A B C D E A B C E D 丰满二叉树 若一棵二叉树中最多只有最下面两层的结点的度数 可以小于2,最下一层的结点随意分布在第i层上 二叉树的性质 一棵非空二叉树的第i层最多有2i个结点(i=0) 深度为k的二叉树最多有2k+1-1个结点(k=0) 任意非空二叉树中,若叶子结点的数目为n0,度为2的结点数目为n2,则有n0=n2+1 将任意次树转换成相应的二叉树 把具有m个子结点k0,k1,…km-1的结点k转换成以k0作为结点k的左子结点,并且ki+1作为ki的右子结点 A B E F C G H D 将所有相邻兄弟结点用线连接 对每个非终端结点,除最