详细了解C语言二叉树的建立与遍历

详细了解C语言二叉树的建立与遍历，久久派带你了解更多相关信息。

目录

• 这里给一个样例树：
• 总结

这里给一个样例树：

代码：

#include <stdio.h> #include <string.h>#include <stdlib.h>/*    二叉树的二叉链表结点结构定义     */typedef struct BiTNode{    char data;    struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;BiTree T=NULL;/*    先序遍历建立一个二叉树    */void Create (BiTree *T)       //    二级指针改变地址的地址{    char ch;    scanf(\"%c\",&ch);    if(ch==\'#\')        *T=NULL;    else    {        *T=(BiTree)malloc(sizeof(BiTNode));        if(!*T)            return ;        else        {            (*T)->data=ch;            Create(&(*T)->lchild);            Create(&(*T)->rchild);        }    }}/*    二叉树的前序递归遍历算法    */void PreOrderTraverse(BiTree T){    if(T==NULL)        return ;    printf(\"%c \",T->data);    PreOrderTraverse(T->lchild);    PreOrderTraverse(T->rchild);}/*    二叉树的中序递归遍历算法    */void InOrderTraverse(BiTree T){    if(T==NULL)        return ;    InOrderTraverse(T->lchild);    printf(\"%c \",T->data);    InOrderTraverse(T->rchild);}/*    二叉树的后序递归遍历算法    */void PostOrderTraverse(BiTree T){    if(T==NULL)        return ;    PostOrderTraverse(T->lchild);    PostOrderTraverse(T->rchild);    printf(\"%c \",T->data);}int main(){    printf(\"请按先序遍历的结果输入树，例如：ABDH#K###E##CFI###G#J##\\n\");    Create(&T);    printf(\"先序遍历的结果为：\\n\");    PreOrderTraverse(T);    printf(\"\\n\");    printf(\"中序遍历的结果为：\\n\");    InOrderTraverse(T);    printf(\"\\n\");    printf(\"后序遍历的结果为：\\n\");    PostOrderTraverse(T);    printf(\"\\n\");    return 0;}

输出结果如下

PS：下面是一个用C++里面的取引用代替了二级指针

#include<bits/stdc++.h>using namespace std;/*    二叉树的二叉链表结点结构定义     */typedef struct BiTNode{    char data;    struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;BiTree T=NULL;/*    先序遍历建立一个二叉树    */void Create (BiTree &T)        //    C++取引用{    char ch;    scanf(\"%c\",&ch);    if(ch==\'#\')        T=NULL;    else    {        T=(BiTree)malloc(sizeof(BiTNode));        if(!T)            return ;        else        {            T->data=ch;            Create(T->lchild);            Create(T->rchild);        }    }}/*    二叉树的前序递归遍历算法    */void PreOrderTraverse(BiTree T){    if(T==NULL)        return ;    printf(\"%c \",T->data);    PreOrderTraverse(T->lchild);    PreOrderTraverse(T->rchild);}/*    二叉树的中序递归遍历算法    */void InOrderTraverse(BiTree T){    if(T==NULL)        return ;    InOrderTraverse(T->lchild);    printf(\"%c \",T->data);    InOrderTraverse(T->rchild);}/*    二叉树的后序递归遍历算法    */void PostOrderTraverse(BiTree T){    if(T==NULL)        return ;    PostOrderTraverse(T->lchild);    PostOrderTraverse(T->rchild);    printf(\"%c \",T->data);}int main(){    printf(\"请按先序遍历的结果输入树，例如：ABDH#K###E##CFI###G#J##\\n\");    Create(T);    printf(\"先序遍历的结果为：\\n\");    PreOrderTraverse(T);    printf(\"\\n\");    printf(\"中序遍历的结果为：\\n\");    InOrderTraverse(T);    printf(\"\\n\");    printf(\"后序遍历的结果为：\\n\");    PostOrderTraverse(T);    printf(\"\\n\");    return 0;}

PS:遍历的PLus版，想要的自取。

#include <iostream>#include <queue>#include <stack>#include <cstdio>#include <cstdlib>using namespace std;const int cmax=1e2+5;typedef struct BiTNode {	char data;	struct BiTNode *lchild ,*rchild;}BiTNode,*BiTree;void CreateBiTree (BiTree &T){	char ch;	scanf(\"%c\",&ch);	if(ch==\'#\')	T=NULL;	else	{		T=(BiTNode *)malloc(sizeof(BiTNode));		T->data=ch;		CreateBiTree(T->lchild);		CreateBiTree(T->rchild);	}	return ; }void PreOrder(BiTree T){	if(T)	{		printf(\"%c\",T->data);		PreOrder(T->lchild);		PreOrder(T->rchild);	}}void InOrder(BiTree T){	if(T)	{		InOrder(T->lchild);		printf(\"%c\",T->data);		InOrder(T->rchild);	}}void PostOrder(BiTree T){	if(T)	{		PostOrder(T->lchild);		PostOrder(T->rchild);		printf(\"%c\",T->data);	}}//   非递归中序遍历 void InOrderTraverse(BiTree T) {	stack<BiTree> S;	BiTree p;	S.push(T);	while(!S.empty())	{		p=new BiTNode;		while((p=S.top())&&p)		    S.push(p->lchild);		S.pop();		if(!S.empty())		{			p=S.top();			S.pop();			cout<<p->data<<\"  \";			S.push(p->rchild); 		 } 	 } }//    先序非递归遍历void PreOrder_Nonrecursive(BiTree T){	stack<BiTree> S;	BiTree p;	S.push(T);	while(!S.empty())	{		while((p=S.top())&&p)		{			cout<<p->data<<\"  \";			S.push(p->lchild); 		 } 		S.pop();		if(!S.empty())		{			p=S.top();			S.pop();			S.push(p->rchild);		 } 	} }  int visit(BiTree T) { 	if(T) 	{ 		printf(\"%c \",T->data); 		return 1;	 }	else	return 0; } //    非递归层次遍历 void  LeverTraverse(BiTree T) { 	queue <BiTree> Q; 	BiTree p; 	p=T; 	if(visit(p)==1) 	    Q.push(p); 	while(!Q.empty()) 	{ 		p=Q.front(); 		Q.pop(); 		if(visit(p->lchild)==1) 		    Q.push(p->lchild); 		if(visit(p->rchild)==1) 		    Q.push(p->rchild);	 } }//主函数int main(){	BiTree T;	char j;	int flag=1;	printf(\"本程序实现二叉树的操作。\\n\");    printf(\"叶子结点以#表示。\\n\");    printf(\"可以进行建立二叉树，递归先序、中序、后序遍历，非递归先序、中序遍历及非递归层序遍历等操作。\\n\");    printf(\"请建立二叉树。\\n\");    printf(\"建树将以三个空格后回车结束。\\n\");    printf(\"例如:1 2 3 4 5 6       (回车)\\n\\n\");	CreateBiTree(T);           //初始化队列    getchar();    printf(\"\\n\");    printf(\"请选择: \\n\");    printf(\"1.递归先序遍历\\n\");    printf(\"2.递归中序遍历\\n\");    printf(\"3.递归后序遍历\\n\");    printf(\"4.非递归中序遍历\\n\");    printf(\"5.非递归先序遍历\\n\");    printf(\"6.非递归层序遍历\\n\");    printf(\"0.退出程序\\n\");    while(flag)    {        scanf(\" %c\",&j);        switch(j)        {            case \'1\':if(T)            {                printf(\"递归先序遍历二叉树:\");                PreOrder(T);                printf(\"\\n\");            }            else printf(\"二叉树为空!\\n\");            break;            case \'2\':if(T)            {                printf(\"递归中序遍历二叉树:\");                InOrder(T);                printf(\"\\n\");            }            else printf(\"二叉树为空!\\n\");            break;            case \'3\':if(T)            {                printf(\"递归后序遍历二叉树:\");                PostOrder(T);                printf(\"\\n\");            }            else printf(\"二叉树为空!\\n\");            break;            case \'4\':if(T)            {                printf(\"非递归中序遍历二叉树:\");                InOrderTraverse(T);                printf(\"\\n\");            }            else printf(\"二叉树为空!\\n\");            break;            case \'5\':if(T)            {                printf(\"非递归先序遍历二叉树:\");                PreOrder_Nonrecursive(T);                printf(\"\\n\");            }            else printf(\"二叉树为空!\\n\");            break;            case \'6\':if(T)            {                printf(\"非递归层序遍历二叉树:\");                LeverTraverse(T);                printf(\"\\n\");            }            else printf(\"二叉树为空!\\n\");            break;            default:flag=0;printf(\"程序运行结束，按任意键退出!\\n\");        }    }}

总结

本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注趣讯吧的更多内容！