c实现树（二叉树）的建立和遍历算法（一）（前序，中序，后序） |
您所在的位置：网站首页 › 二叉树表达式a+b*(c-d)-e/f › c实现树（二叉树）的建立和遍历算法（一）（前序，中序，后序） |
c实现树（二叉树）的建立和遍历算法（一）（前序，中序，后序）
|
最近学习树的概念，有关二叉树的实现算法记录下来。。。 不过学习之前要了解的预备知识：树的概念；二叉树的存储结构；二叉树的遍历方法。。 二叉树的存储结构主要了解二叉链表结构，也就是一个数据域，两个指针域，（分别为指向左右孩子的指针），从下面程序1，二叉树的存储结构可以看出。 二叉树的遍历方法：主要有前序遍历，中序遍历，后序遍历，层序遍历。（层序遍历下一篇再讲，本篇主要讲的递归法） 下篇主要是非递归遍历，之后会有c++模板实现 二叉树 和 二叉搜索树（用于动态查找）。 如这样一个二叉树：
它的前序遍历顺序为：ABDGHCEIF（规则是先是根结点，再前序遍历左子树，再前序遍历右子树） 它的中序遍历顺序为：GDHBAEICF（规则是先中序遍历左子树，再是根结点，再是中序遍历右子树） 它的后序遍历顺序为：GHDBIEFCA（规则是先后序遍历左子树，再是后序遍历右子树，再是根结点） 如果不懂的话，可以参看有关数据结构的书籍。。 1，二叉树的存储结构（二叉链表） //二叉树的二叉链表结构，也就是二叉树的存储结构，1个数据域，2个指针域（分别指向左右孩子） typedef struct BiTNode { ElemType data; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree;2，首先要建立一个二叉树，建立二叉树必须要了解二叉树的遍历方法。 //二叉树的建立，按前序遍历的方式建立二叉树，当然也可以以中序或后序的方式建立二叉树 void CreateBiTree(BiTree *T) { ElemType ch; cin >> ch; if (ch == '#') *T = NULL; //保证是叶结点 else { *T = (BiTree)malloc(sizeof(BiTNode)); //if (!*T) //exit(OVERFLOW); //内存分配失败则退出。 (*T)->data = ch;//生成结点 CreateBiTree(&(*T)->lchild);//构造左子树 CreateBiTree(&(*T)->rchild);//构造右子树 } }3.二叉树的遍历（递归方式，非递归方式见下篇：树（二叉树）的建立和遍历算法（二））： 主要有三种方法： /递归方式前序遍历二叉树 void PreOrderTraverse(BiTree T, int level) { if (T == NULL) return; /*此处表示对遍历的树结点进行的操作，根据你自己的要求进行操作，这里只是输出了结点的数据*/ //operation1(T->data); operation2(T->data, level); //输出了层数 PreOrderTraverse(T->lchild, level + 1); PreOrderTraverse(T->rchild, level + 1); } //递归方式中序遍历二叉树 void InOrderTraverse(BiTree T,int level) { if(T==NULL) return; InOrderTraverse(T->lchild,level+1); //operation1(T->data); operation2(T->data, level); //输出了层数 InOrderTraverse(T->rchild,level+1); } //递归方式后序遍历二叉树 void PostOrderTraverse(BiTree T,int level) { if(T==NULL) return; PostOrderTraverse(T->lchild,level+1); PostOrderTraverse(T->rchild,level+1); //operation1(T->data); operation2(T->data, level); //输出了层数 }4.完整代码： #include #include using namespace std; typedef char ElemType; //二叉树的二叉链表结构，也就是二叉树的存储结构，1个数据域，2个指针域（分别指向左右孩子） typedef struct BiTNode { ElemType data; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree; //二叉树的建立，按前序遍历的方式建立二叉树，当然也可以以中序或后序的方式建立二叉树 void CreateBiTree(BiTree *T) { ElemType ch; cin >> ch; if (ch == '#') *T = NULL; //保证是叶结点 else { *T = (BiTree)malloc(sizeof(BiTNode)); //if (!*T) //exit(OVERFLOW); //内存分配失败则退出。 (*T)->data = ch;//生成结点 CreateBiTree(&(*T)->lchild);//构造左子树 CreateBiTree(&(*T)->rchild);//构造右子树 } } //表示对遍历到的结点数据进行的处理操作,此处操作是将树结点前序遍历输出 void operation1(ElemType ch) { cout lchild, level + 1); PreOrderTraverse(T->rchild, level + 1); } //递归方式中序遍历二叉树 void InOrderTraverse(BiTree T,int level) { if(T==NULL) return; InOrderTraverse(T->lchild,level+1); //operation1(T->data); operation2(T->data, level); //输出了层数 InOrderTraverse(T->rchild,level+1); } //递归方式后序遍历二叉树 void PostOrderTraverse(BiTree T,int level) { if(T==NULL) return; PostOrderTraverse(T->lchild,level+1); PostOrderTraverse(T->rchild,level+1); //operation1(T->data); operation2(T->data, level); //输出了层数 } int main() { int level = 1; //表示层数 BiTree T = NULL; cout |
【本文地址】
今日新闻 |
推荐新闻 |