《c语言程序设计项目教程教学课件作者宋海燕项目十二二叉树》由会员分享，可在线阅读，更多相关《c语言程序设计项目教程教学课件作者宋海燕项目十二二叉树（24页珍藏版）》请在金锄头文库上搜索。
1、项目十二 二 叉 树,任务12.1 初识二叉树 任务12.2 二叉树的遍历,返回,任务12.1 初识二叉树,项目十介绍了线性结构，线性结构的特点是逻辑结构简单，易于进行查找、插入和删除等操作，其主要用于对客观世界中具有单一的前驱和后继的数据关系进行描述，而现实中的许多事物的关系并非这样简单，如人类社会的族谱、各种社会组织机构等。这些事物的联系都是非线性的，采用非线性结构进行描绘会更明确和便利。 所谓非线性结构，是指在该结构中至少存在一个数据元素，有两个或两个以上的直接前驱（或直接后继）元素。树型结构是其中十分重要的非线性结构，可以用来描述客观世界中广泛存在的层次结构。树型结构中最简单、应用十分
2、广泛的是二叉树结构。,下一页,返回,任务12.1 初识二叉树,【实例12.1】创建二叉树 #include “stdio.h“ #include “stdlib.h“ #define MaxSize 10 typedef struct node char data; struct node *lchild,*rchild; /左右孩子指针 BTreeNode; /结点类型 BTreeNode *create() ,上一页,下一页,返回,任务12.1 初识二叉树,BTreeNode *s; BTreeNode *qMaxSize; / MaxSize 根据需要设定大小 int i,j; char
3、 x; printf(“i,x=“); scanf(“%d,%c“, while(i!=0&x!=$) ,上一页,下一页,返回,任务12.1 初识二叉树,s=(BTreeNode *)malloc(sizeof(BTreeNode); s-data=x; s-lchild=NULL; s-rchild=NULL; qi=s; if(i!=1)/非根结点，寻找双亲结点的地址 j=i/2;/j 为双亲结点的地址 if(i%2=0)/左孩子 qj-lchild=s; else/右孩子 qj-rchild=s;,上一页,下一页,返回,任务12.1 初识二叉树, printf(“i,x=“); scan
4、f(“%d,%c“, ,上一页,下一页,返回,任务12.1 初识二叉树,（1）运行结果。 实例12.1 的运行结果如图12-3 所示。 （2）知识链接。 树的基本术语。 a. 结点的度。结点所拥有的子树的个数称为该结点的度。 b. 叶结点。度为0 的结点称为叶结点，或者称为终端结点。 c. 结点的层数。规定树的根结点的层数为1，其余结点的层数等于它的双亲结点的层数加1。 d. 树的深度。树中所有结点的最大层数称为树的深度(也称为树的高度)。 e. 树的度。树中各结点的度的最大值称为该树的度。,上一页,下一页,返回,任务12.1 初识二叉树, 二叉树的定义。 二叉树（Binary Tree）是有
5、限元素的集合，该集合或者为空，或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。 二叉树是有序的，即若将其左、右子树颠倒，就成为另一棵不同的二叉树。即使树中结点只有一棵子树，也要区分它是左子树还是右子树。因此二叉树具有5 种基本形态，如图12-4所示。 二叉树的性质。 性质1 一棵非空二叉树的第i 层上最多有2i1 个结点（i1）。 性质2 一棵深度为k 的二叉树中，最多具有2k1 个结点。,上一页,下一页,返回,任务12.1 初识二叉树,性质3 对于一棵非空的二叉树，如果叶子结点数为
6、n0，度数为2 的结点数为n2，则有：n0n21。 性质4 满二叉树：一棵高度为k 且拥有2k1 个结点的二叉树，称为满二叉树。 性质5 完全二叉树：如果一棵二叉树最多只有最下面的两层结点度数可以小于2，并且最下面一层的结点都集中在该层左面的若干位置，则其称为完全二叉树。 二叉树的链式存储（图12-5）。 二叉树链式存储结构类型的定义如下： typedef struct node,上一页,返回,任务12.2 二叉树的遍历,【实例12.2】二叉树的遍历 #include “stdio.h“ #include “stdlib.h“ #define MaxSize 10 typedef struct
7、 node char data; struct node *lchild,*rchild;/左右孩子指针 BTreeNode; /结点类型 BTreeNode *create() ,下一页,返回,任务12.2 二叉树的遍历,BTreeNode *s; BTreeNode *qMaxSize;/ MaxSize 根据需要设定大小 int i,j; char x; printf(“i,x=“); scanf(“%d,%c“, while(i!=0&x!=$) ,上一页,下一页,返回,任务12.2 二叉树的遍历, s=(BTreeNode *)malloc(sizeof(BTreeNode); s-
8、data=x; s-lchild=NULL; s-rchild=NULL; qi=s; if(i!=1)/非根结点，寻找双亲结点的地址 j=i/2;/j 为双亲结点的地址 if(i%2=0)/左孩子 qj-lchild=s;,上一页,下一页,返回,任务12.2 二叉树的遍历,else/右孩子 qj-rchild=s; printf(“i,x=“); scanf(“%d,%c“, ,上一页,下一页,返回,任务12.2 二叉树的遍历,/先序遍历算法如下： void preorder(BTreeNode *bt) if(bt!=NULL) printf(“%c “,bt-data); preorde
9、r(bt-lchild); preorder(bt-rchild); ,上一页,下一页,返回,任务12.2 二叉树的遍历,/中序遍历算法如下： void inorder(BTreeNode *bt) if(bt!=NULL) inorder(bt-lchild); printf(“%c “,bt-data); inorder(bt-rchild); ,上一页,下一页,返回,任务12.2 二叉树的遍历,/后序遍历算法如下： void postorder(BTreeNode *bt) if(bt!=NULL) postorder(bt-lchild); postorder(bt-rchild);
10、printf(“%c “,bt-data); main(),上一页,下一页,返回,任务12.2 二叉树的遍历, BTreeNode *bt; bt=create(); printf(“先序递归遍历结果：“); preorder(bt); printf(“n 中序递归遍历结果：“); inorder(bt); printf(“n 后序递归遍历结果：“); postorder(bt); ,上一页,下一页,返回,任务12.2 二叉树的遍历,（1）运行结果。 实例12.2 的运行结果如图12-7 所示。 （2）知识链接。 二叉树的遍历。 二叉树的遍历是指按照某种顺序访问二叉树中的每个结点，使每个结点被
11、访问一次且仅被访问一次。 二叉树的遍历方法。 a. 先序遍历：先序遍历的过程为访问根、遍历左子树、遍历右子树。 b. 中序遍历：中序遍历的过程为遍历左子树、访问根、遍历右子树。,上一页,下一页,返回,任务12.2 二叉树的遍历,c. 后序遍历：后序遍历的过程为遍历左子树、遍历右子树、访问根。 对于图12-8 所示的二叉树： 按先序遍历所得到的结点序列为：A B D G C E F； 按中序遍历所得到的结点序列为：D G B A E C F； 按后序遍历所得到的结点序列为：G D B E F C A。,上一页,返回,图12-3 实例12.1 的运行结果,返回,图12-4 二叉树的5 种基本形态,返回,图12-5 二叉树链式存储结构示意,返回,图12-7 实例12.2 的运行结果,返回,图12-8 二叉树 举例,返回,
