贸易公司自建免费网站,微信群发软件,ftp媒体库 wordpress,网站推广的技术代码参考《妙趣横生的算法.C语言实现》 文章目录前言1、树的概念2、二叉树3、二叉树的遍历4、创建二叉树5、实例分析前言
本章总结#xff1a;树的概念、二叉树的创建、遍历 1、树的概念
树结构是以分支关系定义得一种层次结构。 树的定义#xff1a;树是由n(n0)个结点…代码参考《妙趣横生的算法.C语言实现》 文章目录前言1、树的概念2、二叉树3、二叉树的遍历4、创建二叉树5、实例分析前言
本章总结树的概念、二叉树的创建、遍历 1、树的概念
树结构是以分支关系定义得一种层次结构。 树的定义树是由n(n0)个结点组成的有穷集合。在任意的一棵非空树中 1、有且仅有一个称为根(root)的结点 2、当n1时其余的结点分为m(m0)个互不相交的有限集合T1,T2,T3,…Tm.其中每个集合本身又是一棵树并称为跟的子树(SubTree) 以上图为例A是rootBCD是A的child以BCD为根节点构成3棵树为A的字·SubTree。 树的存储形式多重链表在多重链表中每个结点由一个数据域和若干个指针域组成其中每个指针域指向该结点的一个孩子结点。 多重链表结点类型描述
#define MaxChild 10
typedef struct node {ElemType data;struct node* child[MaxChild]; //指向孩子结点的指针数组将父节结点和子结点联系起来
};在利用多重链表表示树结构时分定长结点每个结点的指针域个数固定和不定长结点每个结点的指针域个数不固定 对于二叉树来说一个结点至多可以有左右两个孩子结点或者只有一个孩子结点或者没有孩子结点。 T是一个指针指向二叉树的根结点。只有得到T才能访问整个树结构。
2、二叉树
二叉树的递归定义二叉树是这样的树结构它或者为空或者由一个根结点加上两棵分别称为左子树和右字数的互不相交的二叉树组成。
二叉树结点有三个域,lchild、rchild为指针域用来指向该结点的左孩子和右孩子。data是数据域用来存放该结点中包含的数据。
//二叉树结点定义
typedef struct BiTNode {ElemType data;struct BiTNode* lchild, * rchild;
}BiTNode,*BiTreee;
//二叉树结点类BiTNode,二叉树每个结点都属于该类型
//BiTree是一个指向BiTNode类型数据的指针3、二叉树的遍历
从一个结点(一般来说是根结点)出发按一定规律访问二叉树的全部结点每个结点只访问一次。
应用二叉树递归地逻辑特性采用递归方法遍历二叉树。
1、先序遍历
1、访问根结点
2、先序遍历左子树
3、先序遍历右子树
2、中序遍历
1、中序遍历左子树
2、访问根结点
3、中序遍历右子树
//定义visit函数
//访问结点,输出结点的层数
void visit(char c)
{printf(%c is at %d the level of BiTree\n);
}
//**********************遍历二叉树*********************//
//先序遍历
void PreOrderTraverse(BiTreee T)
{if (T) //递归结束条件T为空{visit(T-data); //访问根结点PreOrderTraverse(T-lchild); //先序遍历左子树PreOrderTraverse(T-rchild); //先序遍历右子树}
}
//中序遍历
void InOrderTraverse(BiTreee T)
{if (T) //递归结束条件T为空{InOrderTraverse(T-lchild); //先序遍历左子树visit(T-data); //访问根结点InOrderTraverse(T-rchild); //先序遍历右子树}
}
//后序遍历
void PosOrderTraverse(BiTreee T)
{if (T) //递归结束条件T为空{PosOrderTraverse(T-lchild); //先序遍历左子树PosOrderTraverse(T-rchild); //先序遍历右子树visit(T-data); //访问根结点}
}4、创建二叉树
借鉴二叉树的遍历算法也可以逐个生成结点从而创建出一个二叉树。
//先序创建一棵二叉树
void CreateBiTree(BiTreee* T)
{char c;scanf(%c,c);if (c ) *T NULL;else{*T (BiTNode *)malloc(sizeof(BiTNode)); //创建根结点(*T)-data c; //向根结点中输入数据CreateBiTree(((*T)-lchild)); //递归地创建左子树CreateBiTree(((*T)-rchild)); //递归地创建右子树}
}
//依次输入ABC D E F //
//空格是递归结束的标志当创建到叶子结点时因为叶子结点的左右子树都为空因此要输入空格表示结束。在创建二叉树的过程中程序总是按照创建根结点-创建左子树-创建右子树顺序进行5、实例分析
用先序创建一棵树并输出每个字符位于二叉树的层数
#include stdio.h
#include malloc.h
#include conio.h
#include stdlib.h
#include math.h
typedef char ElemType ;
#define MaxChild 10
typedef struct node {ElemType data;struct node* child[MaxChild]; //指向孩子结点的指针数组将父节结点和子结点联系起来
};
//在利用多重链表表示树结构时分定长结点每个结点的指针域个数固定和不定长结点每个结点的指针域个数不固定
//对于二叉树来说一个结点至多可以有左右两个孩子结点或者只有一个孩子结点或者没有孩子结点。
//T是一个指针指向二叉树的根结点。只有得到T才能访问整个树结构。//二叉树结点定义
typedef struct BiTNode {ElemType data;struct BiTNode* lchild, * rchild;
}BiTNode,*BiTreee;
//二叉树结点类BiTNode,二叉树每个结点都属于该类型
//BiTree是一个指向BiTNode类型数据的指针//定义visit函数
//访问结点,输出结点的层数
void visit(char c,int level)
{printf(%c is at %d the level of BiTree\n,c, level);
}
//**********************遍历二叉树*********************//
//先序遍历
void PreOrderTraverse(BiTreee T,int level)
{if (T) //递归结束条件T为空{visit(T-data,level); //访问根结点PreOrderTraverse(T-lchild, level1); //先序遍历左子树,层数1PreOrderTraverse(T-rchild, level1); //先序遍历右子树,层数1}
}
//中序遍历
void InOrderTraverse(BiTreee T, int level)
{if (T) //递归结束条件T为空{InOrderTraverse(T-lchild, level 1); //中序遍历左子树,层数1visit(T-data, level); //访问根结点InOrderTraverse(T-rchild, level1); //中序遍历右子树,层数1}
}
//后序遍历
void PosOrderTraverse(BiTreee T, int level)
{if (T) //递归结束条件T为空{PosOrderTraverse(T-lchild, level 1); //中序遍历左子树,层数1PosOrderTraverse(T-rchild, level1); //中序遍历右子树,层数1visit(T-data, level); //访问根结点}
}
//先序创建一棵二叉树
void CreateBiTree(BiTreee* T)
{char c;scanf(%c,c);if (c ) *T NULL;else{*T (BiTNode *)malloc(sizeof(BiTNode)); //创建根结点(*T)-data c; //向根结点中输入数据CreateBiTree(((*T)-lchild)); //递归地创建左子树CreateBiTree(((*T)-rchild)); //递归地创建右子树}
}
//依次输入ABC D E F //
//空格是递归结束的标志当创建到叶子结点时因为叶子结点的左右子树都为空因此要输入空格表示结束。在创建二叉树的过程中程序总是按照创建根结点-创建左子树-创建右子树顺序进行//测试程序
int main()
{int level 1;BiTreee T NULL;printf(创建二叉树\n);CreateBiTree(T); //创建二叉树printf(先序遍历\n);PreOrderTraverse(T,level); //先序遍历level 1;printf(中序遍历\n);InOrderTraverse(T, level); //先序遍历level 1;printf(后序遍历\n);PosOrderTraverse(T, level); //先序遍历level 1;_getche();return 0;
}效果 结果显然对的并且能够显示出三种遍历方式的具体遍历过程
