1、第第1414章章 二叉树及其应用二叉树及其应用 1 1本章主要内容本章主要内容 树的概念树的概念 关于树的一些术语及特性关于树的一些术语及特性 二叉树的特点与数学性质二叉树的特点与数学性质 二叉树的基本操作及其实现二叉树的基本操作及其实现 二叉树的应用二叉树的应用2 2 树是由一个集合以及在该集合上定义树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点次结构。在这种层次结构
2、中有一个结点具有特殊的地位，这个结点称为该树的具有特殊的地位，这个结点称为该树的根结点，或简称为树根。根结点，或简称为树根。14.1 树的概念树的概念 3 34 4结点的度：一个结点的子结点的个数称结点的度：一个结点的子结点的个数称为该结点的度。一棵树的度是指该树中为该结点的度。一棵树的度是指该树中结点的最大度数。结点的最大度数。终端结点：树中度为零的结点称为终端终端结点：树中度为零的结点称为终端结点，树中度不为零的结点称为分枝结结点，树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。点统称为内部结点。14.2 关于树的一些术语及
3、特性关于树的一些术语及特性 5 5路径：如果存在树中的一个结点序列路径：如果存在树中的一个结点序列K1,K2,.,Kj，使得结点，使得结点Ki是结点是结点Ki+1的父的父结点结点(1ij)，则称该结点序列是树中，则称该结点序列是树中从结点从结点K1到结点到结点Kj的一条路径或道路。的一条路径或道路。结点高度：树中一个结点的高度是指从结点高度：树中一个结点的高度是指从该结点到作为它的子孙的各叶结点的最该结点到作为它的子孙的各叶结点的最长路径的长度。树的高度是指根结点的长路径的长度。树的高度是指根结点的高度。高度。6 6层：从树根到任一结点层：从树根到任一结点n有惟一的一条路有惟一的一条路径，这条
4、路径的长度称为结点径，这条路径的长度称为结点n的深度或的深度或层数。层数。有序树：树的定义在某些结点之间确定有序树：树的定义在某些结点之间确定了父子关系（可延拓为祖先子孙关系）。了父子关系（可延拓为祖先子孙关系）。但是树中兄弟结点之间就没有祖先子孙但是树中兄弟结点之间就没有祖先子孙关系。若在树的每一组兄弟结点之间定关系。若在树的每一组兄弟结点之间定义一个从左到右的次序，则得到一棵有义一个从左到右的次序，则得到一棵有序树；否则称为无序树序树；否则称为无序树 7 714.3 二叉树的特点与数学性质二叉树的特点与数学性质 二叉树的定义二叉树的定义二叉树是一种特殊的树型结构，其每个二叉树是一种特殊的树
5、型结构，其每个节点最多只有两个子树节点最多只有两个子树二叉树是结点的有限集合，该集合或是二叉树是结点的有限集合，该集合或是空集，或是一个根空集，或是一个根特点：特点：每一个结点至多有两个后继结点，且有每一个结点至多有两个后继结点，且有左右之分，不能任意交换，这些结点分别称左右之分，不能任意交换，这些结点分别称为左子树，右子树。为左子树，右子树。8 814.3.1 二叉树的特点二叉树的特点 9 9(a)只有左子树只有左子树(b)只有右子树只有右子树 101014.3.2 两种特殊形态的二叉树两种特殊形态的二叉树 满二叉树满二叉树 一棵高度一棵高度为为n0且有且有2n+1-1个个结点的二结点的二叉
6、树称为叉树称为满二叉树满二叉树 1111近似满二叉树近似满二叉树 若一棵二叉若一棵二叉树至多只有树至多只有最下面的两最下面的两层结点的度层结点的度数小于数小于2，并，并且最下面一且最下面一层结点都集层结点都集中在该层的中在该层的最左边，则最左边，则称这种二叉称这种二叉树为近似满树为近似满二叉树二叉树(有时有时也称为完全也称为完全二叉树二叉树)。1212非近似满二叉树非近似满二叉树 在近似满在近似满二叉树中，二叉树中，若某个结若某个结点没有左点没有左儿子，则儿子，则它一定没它一定没有右儿子，有右儿子，即该结点即该结点是一个叶是一个叶结点结点 131314.3.3 二叉树的数学性质二叉树的数学性质
7、 高度为高度为n0的二叉树至少有的二叉树至少有n+1个结点个结点高度不超过高度不超过n(0)的二叉树至多有的二叉树至多有2n+1-1个结点个结点含有含有n1个结点的二叉树的高度至多为个结点的二叉树的高度至多为n-1，至少为，至少为lg(n)141414.4二叉树的基本操作及其实现二叉树的基本操作及其实现 1515二叉树的常用操作如下：二叉树的常用操作如下：InitTree(&T)：构造一棵空二叉树；：构造一棵空二叉树；DestroyTree(&T)：销毁一棵二叉树；：销毁一棵二叉树；Parent(T,e)：返回二叉树：返回二叉树T中中e结点的父结结点的父结点，若不存在则返回点，若不存在则返回“
8、空空”；LeftChild(T,e)：返回二叉树：返回二叉树T中中e结点的左结点的左儿子结点，若不存在则返回儿子结点，若不存在则返回“空空”；RightChild(T,e)：返回二叉树：返回二叉树T中中e结点的结点的右儿子结点，若不存在则返回右儿子结点，若不存在则返回“空空”；Value(T,e)：返回二叉树：返回二叉树T中中e结点的值；结点的值；Root(T)：返回二叉树：返回二叉树T的根结点。的根结点。14.4.1 二叉树的基本操作二叉树的基本操作 16161 二叉树的顺序存储结构二叉树的顺序存储结构#define MAXLENGTH 255#define TYPE intstruct T
9、Treeint nTreeSize;TYPE nodeMAXLENGTH;typedef struct TTree Tree;14.4.2 二叉树基本操作的实现二叉树基本操作的实现 1717顺序存储结构实现顺序存储结构实现ADT二叉树的操作二叉树的操作:void InitTree(Tree*T)/构造空树构造空树int i;T-nTreeSize=0;for(i=0;inodei=0;void DestroyTree(Tree*T)/销毁树销毁树int i;T-nTreeSize=0;for(i=0;inodei=0;1818TYPE Parent(Tree T,int e)/返回父结点返回父
10、结点if(e0)return T.node(e-1)/2;else return 0;TYPE LeftChild(Tree T,int e)/返回二叉树返回二叉树T中中e结点的左儿子结点结点的左儿子结点if(e*2+1MAXLENGTH)return T.nodee*2+1;elsereturn 0;1919TYPE RightChild(Tree T,int e)/返回二叉树返回二叉树T中中e结点的右儿子结点结点的右儿子结点if(e*2+2=0&e infop-info)root-left=inserttree(root-left,p);else root-right=inserttree
11、(root-right,p);return(root);2828遍历二叉树的算法遍历二叉树的算法 中序遍历二叉树中序遍历二叉树inorder(root)struct tree*root;if(!root)return;inorder(root-left);printf(%c,root-info);inorder(root-right);2929二叉树的遍历算法二叉树的遍历算法 先序遍历二叉树先序遍历二叉树preorder(root)struct tree*root;if(!root)return;printf(%c,root-info);preorder(root-left);preorder
12、(root-right);3030二叉树的遍历算法二叉树的遍历算法 后序遍历二叉树后序遍历二叉树postorder(root)struct tree*root;if(!root)return;postorder(root-left);postorder(root-right);printf(%c,root-info);31313232【例】从键盘读入一组数据并创建一个【例】从键盘读入一组数据并创建一个二叉树，数据插入时按照左结点小于等二叉树，数据插入时按照左结点小于等于该结点，右结点大于该结点的规则。于该结点，右结点大于该结点的规则。例如，用户输入：例如，用户输入：8 6 4 5 7 3 1
13、2请建立二叉树，并用先序、中序和后序请建立二叉树，并用先序、中序和后序遍历遍历#include#include struct Tnode/二叉树存储结构二叉树存储结构int data;struct TNode*left;struct TNode*right;3333typedef struct TNode*Tree;void Insert(Tree*t,int value)/插入结点插入结点struct TNode*tmp;Tree T=*t;if(T=NULL)tmp=(struct TNode*)malloc(sizeof(struct TNode);tmp-data=value;/初始化
14、结点初始化结点 tmp-left=NULL;tmp-right=NULL;*t=tmp;3434elseif(value data)/插入右子树插入右子树if(T-left!=NULL)Insert(&(T-left),value);else tmp=(struct TNode*)malloc (sizeof(struct TNode);tmp-data=value;tmp-left=NULL;tmp-right=NULL;(*t)-left=tmp;3535elseif(T-right!=NULL)/插入左子树插入左子树 Insert(&(T-right),value);else tmp=(
15、struct TNode*)malloc (sizeof(struct TNode);tmp-data=value;tmp-left=NULL;tmp-right=NULL;(*t)-right=tmp;3636void PreOrder(Tree T)/先序遍历先序遍历if(T=NULL)return;elseprintf(%dt,T-data);PreOrder(T-left);PreOrder(T-right);3737void MidOrder(Tree T)/中序遍历中序遍历if(T=NULL)return;elseMidOrder(T-left);printf(%dt,T-data
16、);MidOrder(T-right);3838void PostOrder(Tree T)/后序遍历后序遍历if(T=NULL)return;elsePostOrder(T-left);PostOrder(T-right);printf(%dt,T-data);3939void main()Tree T;int i,a,n;T=NULL;printf(How many nodes?n);/提示所要输入的结点个数提示所要输入的结点个数scanf(%d,&n);for(i=0;in;i+)scanf(%d,&a);Insert(&T,a);/调用插入结点的函数调用插入结点的函数4040printf(n);PreOrder(T);printf(n);MidOrder(T);printf(n);PostOrder(T);printf(n);4141
