c语言二叉树遍历
‘壹’ c语言二叉树的遍历。
二叉树的前中后遍历（递归与非递归）
#include<stdio.h>
#include<stdlib.h>
typedef struct NODE
{
char value;
struct NODE *LChild;
struct NODE *RChild;
}BiTNode,*BiTree; //二叉树数据结构
BiTree root;
typedef struct node
{
BiTNode *pointer;
struct node *link;
}LinkStackNode,*LinkStack; //链栈数据结构
LinkStack S;
int count = 0;
//BiTNode * InitTree(BiTree Tree);
BiTNode *CreateTree(BiTree Tree); //创建二叉树
void PreOrder(BiTree Tree); //递归前序遍历二叉树
void MidOrder(BiTree Tree); //递归中序遍历二叉树
void PostOrder(BiTree Tree); //递归后序遍历二叉树
void NPreOrder(BiTree Tree); //非递归前序遍历二叉树
void NMidOrder(BiTree Tree); //非递归中序遍历二叉树
void NPostOrder(BiTree Tree); //非递归后序遍历二叉树
//---------------------------------------------------
LinkStackNode *InitLinkStack(LinkStack top); //初始化链栈
void Push(LinkStack top,BiTNode *p); //进栈操作
BiTNode * Pop(LinkStack top); //出栈操作
//int IsEmpty(LinkStack S); //判断栈是否为空
void main()
{
//BiTree tree;
//root = InitTree(tree);
root = CreateTree(root);
PreOrder(root);
printf("\n");
MidOrder(root);
printf("\n");
PostOrder(root);
printf("\n");
NPreOrder(root);
printf("\n");
NMidOrder(root);
printf("\n");
NPostOrder(root);
printf("\n");
}
/*BiTNode * InitTree(BiTree Tree)
{
//BiTNode *root;
//root = Tree;
Tree = (BiTNode *)malloc(sizeof(BiTNode));
Tree = NULL;
//Tree->LChild = NULL;
//Tree->RChild = NULL;
return Tree;
}*/
//二叉树的扩展先序遍历的创建
BiTNode * CreateTree(BiTree Tree)
{
char ch;
ch = getchar();
if(ch == '.')
Tree = NULL;
else
{
Tree = (BiTNode *)malloc(sizeof(BiTNode));
if(Tree)
{
Tree->value = ch;
Tree->LChild = CreateTree(Tree->LChild);
Tree->RChild = CreateTree(Tree->RChild);
}
}
return Tree;
}
//递归前序遍历二叉树
void PreOrder(BiTree Tree)
{
if(Tree)
{
printf("%c",Tree->value);
PreOrder(Tree->LChild);
PreOrder(Tree->RChild);
}
}
//递归中序遍历二叉树
void MidOrder(BiTree Tree)
{
if(Tree)
{
MidOrder(Tree->LChild);
printf("%c",Tree->value);
MidOrder(Tree->RChild);
}
}
//递归后序遍历二叉树
void PostOrder(BiTree Tree)
{
if(Tree)
{
PostOrder(Tree->LChild);
PostOrder(Tree->RChild);
printf("%c",Tree->value);
}
}
//非递归前序遍历二叉树
void NPreOrder(BiTree Tree)
{
BiTNode *p;
S = InitLinkStack(S);
p = Tree;
while(p || count != 0)
{
if(p)
{
if(p->RChild)
Push(S,p->RChild);
printf("%c",p->value);
p = p->LChild;
}
else
p = Pop(S);
}
}
//非递归中序遍历二叉树
void NMidOrder(BiTree Tree)
{
//char ch;
BiTNode *p;
S = InitLinkStack(S);
p = Tree;
while(p || count != 0)
{
if(p)
{
Push(S,p);
p = p->LChild;
}
else
{
p = Pop(S);
printf("%c",p->value);
p = p->RChild;
}
}
}
//非递归后序遍历二叉树
void NPostOrder(BiTree Tree)
{
BiTNode *p,*q = NULL;
S = InitLinkStack(S);
p = Tree;
while(p || count != 0)
{
if(p)
{
Push(S,p);
p = p->LChild;
}
else
{
p = S->link->pointer;
if(p->RChild == NULL || p->RChild == q)
{
p = Pop(S);
printf("%c",p->value);
q = p;
p = NULL;
}
else
{
//p = Pop(S);
p = p->RChild;
}
}
}
}
//初始化链栈
LinkStackNode *InitLinkStack(LinkStack top)
{
top = (LinkStackNode *)malloc(sizeof(LinkStackNode));
return top;
}
//进栈操作
void Push(LinkStack top,BiTNode *p)
{
LinkStackNode *temp;
temp = (LinkStackNode *)malloc(sizeof(LinkStackNode));
if(temp)
{
temp->pointer = p;
temp->link = top->link;
top->link = temp;
count++;
}
}
//出栈操作
BiTNode * Pop(LinkStack top)
{
//char ch;
BiTNode *p;
LinkStackNode *temp;
p = (BiTNode *)malloc(sizeof(BiTNode));
temp = top->link;
if(temp)
{
top->link = temp->link;
p = temp->pointer;
free(temp);
count--;
}
return p;
}
‘贰’ C语言二叉树遍历代码
1.t = malloc(sizeof(tree));
2.t->rchild =createTree();
3.void qianxu(tree *t)
4.zhongxu(t->lchild );//再读左子树
printf("%c",t->data);//先读根结点
zhongxu(t->rchild );//再读右子树
5.houxu(t->lchild );//再读左子树
houxu(t->rchild );//再读右子树
printf("%c",t->data);//先读根结点
6.return 0;
7.n=count(t->lchild)+count(t->rchild)+1;
8.t1->data=t->data;
9.return t1;
10.return m+1;
PS:注意有些语句结尾是没有分号的
‘叁’ 二叉树的遍历程序！数据结构C语言！要能运行的！
#include<iostream>
using
namespace
std;
#define
OK
1
#define
ERROR
0
#define
OVERFLOW
-1
typedef
int
Status
;
typedef
char
TElemType;
typedef
struct
TreeNode{
//定义的树结点
TElemType
Data;
struct
TreeNode
*lchild,*rchild;
}TreeNode,*Treep;
Treep
CreateTree(Treep
&T)
//使用先序遍历优势创建
{
char
ch;
//
cout<<"\n请你输入你要创建的树元素：";
cin>>ch;
if(ch
==
'#')
//若是"#",代表该节点为空
T
=
NULL;
else
{
T
=
new
TreeNode;
//申请空间
if(!T)
return
ERROR;
//空间申请失败返回错误信息
T->Data
=
ch;
//键盘输入结点信息
CreateTree(T->lchild);
//递归调用创建左子树
CreateTree(T->rchild);
//递归调用创建右子树
}
return
T;
}
void
TreeTreaverseF(Treep
T)
//二叉树先序遍历
{
if(T)
{
cout<<T->Data;
//输出根节点值
TreeTreaverseF(T->lchild);
//递归调用输出左子树
TreeTreaverseF(T->rchild);
//递归调用输出右子树
}
}
void
TreeTreaverseS(Treep
T)
//中序遍历二叉树
{
if(T)
{
TreeTreaverseS(T->lchild);
//递归调用输出左子树
cout<<T->Data;
//输出左节点
TreeTreaverseS(T->rchild);
//递归调用输出右子树
}
}
void
TreeTreaverseT(Treep
T)
{
if(T)
{
TreeTreaverseT(T->lchild);
//递归调用输出左子树
TreeTreaverseT(T->rchild);
//递归调用输出右子树
cout<<T->Data;
//输出右节点
}
}
int
main()
{
Treep
T=NULL;
cout<<"\n开始创建树状结构...\n";
cout<<"\n各元素以空格隔开\n";
CreateTree(T);
cout<<"\n先序遍历输出树...\n";
TreeTreaverseF(T);
cout<<endl<<endl;
cout<<"\n中序遍历输出树...\n";
TreeTreaverseS(T);
cout<<endl<<endl;
cout<<"\n后序遍历输出树...\n";
TreeTreaverseT(T);
cout<<endl<<endl;
return
0;
}
‘肆’ 求用C语言实现二叉树层次遍历的递归算法，谢谢！！！
算法思想：层次遍历目前最普遍用的就是队列的那种方式，不是递归，但是用到while循环，既然题目要求用递归，可以用递归实现该while循环功能。算法如下：
void TransLevele(Tree *r)
{
if (r==NULL)
{
return ;
}
printf("%c",r->ch);
if (r->left != NULL)
{
InsertQueue(r->left);
}
if (r->right != NULL)
{
InsertQueue(r->right);
}
Tree *t = DeleteQueue();
TransLevele(t);
}
//测试程序，创建树输入例如ABD##E##C##,根左右创建的方式。
如下代码是测试通过的。
#include "stdlib.h"
#define MAX 100
typedef int Element;
typedef struct tree
{
Element ch;
struct tree *left;
struct tree *right;
}Tree;
typedef struct queue
{
Tree *a[MAX];
int front;
int rear;
}Queue;
Queue Qu;
void Init();
int InsertQueue(Element ch);
Tree *DeleteQueue();
void CreateTree(Tree **r);
void TransLevele(Tree *r);
void PrintTree(Tree *r);
int main()
{
Tree *r=NULL;
CreateTree(&r);
PrintTree(r);
printf("\n");
TransLevele(r);
return 0;
}
void Init()
{
int i=0;
for (i=0; i<MAX; i++)
{
Qu.a[i] = NULL;
}
Qu.front = 0;
Qu.rear = 0;
}
int InsertQueue(Tree *r)
{
if ( (Qu.rear+1)%MAX == Qu.front)
{
printf("Queue full!");
return 0;
}
Qu.a[Qu.rear] = r;
Qu.rear = (Qu.rear+1)%MAX;
return 1;
}
Tree *DeleteQueue()
{
if (Qu.front == Qu.rear)
{
printf("Queue empty");
return NULL;
}
Tree *t=NULL;
t = Qu.a[Qu.front];
Qu.front = (Qu.front+1)%MAX;
return t;
}
void CreateTree(Tree **r)
{
Element ch;
ch=getchar();
if (ch=='#')
{
(*r)=NULL;
return ;
}
*r = (Tree *)malloc(sizeof(Tree));
(*r)->ch = ch;
CreateTree(&((*r)->left));
CreateTree(&((*r)->right));
}
void PrintTree(Tree *r)
{
if (r==NULL)
{
return ;
}
printf("%c",r->ch);
PrintTree(r->left);
PrintTree(r->right);
}
void TransLevele(Tree *r)
{
if (r==NULL)
{
return ;
}
printf("%c",r->ch);
if (r->left != NULL)
{
InsertQueue(r->left);
}
if (r->right != NULL)
{
InsertQueue(r->right);
}
Tree *t = DeleteQueue();
TransLevele(t);
}
‘伍’ C语言 二叉树 遍历问题
并不是你所说的那样。
首先我们要知道遍历是为了让二叉树的所有结点都扫描一遍，而前中后，三个遍历方式，说的是他的显示顺序。
前序的特点：我们注意研究一下前序遍历的结果，你会发现，对于每个二叉树（只有根结点，左结点，右结点。一棵树，是一个个小的二叉树组成）在结果中，你都会发现，根结点必定在左结点前。你可以认真看看，就算，是子树中也是根结点在左结点前。（比如，左结点成了另一个子树的根结点，这个左结点对应的上一级根结点，也会显示在这个左结点之前）
中序的特点：经过前序遍历的分析 ，我们可以直接得出，中序遍历结果中，每个根结点都会放在左结点和右结点中间。当然发生如，A的左结点是B，B的右结点是C，时中序遍历结果会是
BCA，虽然A未在中间，但我们要分析，对于A是根结点，左结点B在其前面，对于B是根结点，右结点C在其后面。这符合根结点在左右结点中间的特点。
后序的特点：是先遍历左右结点，才返回来遍历根结点。参照前序和中序，就能明白
最后要注意的，可能 你也发现了，左结点的遍历一定在右结点前。
下面附上遍历的递归算法
/*1 、前序遍历二叉树的递归算法 */
void preorder(bintree t)
{
if (t) {
printf("%c",t->data);
preorder(t->lchild);
preorder(t->rchild);
}
}
/*2 、中序遍历二叉树的递归算法 */
void inorder(bintree t)
{
if (t) {
inorder(t->lchild);
printf("%c",t->data);
inorder(t->rchild);
}
}
/*3 、后序遍历二叉树的递归算法 */
void postorder(bintree t)
{
if (t) {
postorder(t->lchild);
postorder(t->rchild);
printf("%c",t->data);
}
}
说那么多，我自己也复习下，哈哈
‘陆’ C语言二叉树遍历查找问题
二叉树的遍历分为以下三种：
先序遍历：遍历顺序规则为【根左右】
中序遍历：遍历顺序规则为【左根右】
后序遍历：遍历顺序规则为【左右根】
什么是【根左右】？就是先遍历根，再遍历左孩子，最后遍历右孩子；
举个例子，看下图：
先序遍历：ABCDEFGHK
中序遍历：BDCAEHGKF
后序遍历：DCBHKGFEA
以中序遍历为例：
中序遍历的规则是【左根右】，我们从root节点A看起；
此时A是根节点，遍历A的左子树；
A的左子树存在，找到B，此时B看做根节点，遍历B的左子树；
B的左子树不存在，返回B，根据【左根右】的遍历规则，记录B，遍历B的右子树；
B的右子树存在，找到C，此时C看做根节点，遍历C的左子树；
C的左子树存在，找到D，由于D是叶子节点，无左子树，记录D，无右子树，返回C，根据【左根右】的遍历规则，记录C，遍历C的右子树；
C的右子树不存在，返回B，B的右子树遍历完，返回A；
至此，A的左子树遍历完毕，根据【左根右】的遍历规则，记录A，遍历A的右子树；
A的右子树存在，找到E，此时E看做根节点，遍历E的左子树；
E的左子树不存在，返回E，根据【左根右】的遍历规则，记录E，遍历E的右子树；
E的右子树存在，找到F，此时F看做根节点，遍历F的左子树；
F的左子树存在，找到G，此时G看做根节点，遍历G的左子树；
G的左子树存在，找到H，由于H是叶子节点，无左子树，记录H，无右子树，返回G，根据【左根右】的遍历规则，记录G，遍历G的右子树；
G的右子树存在，找到K，由于K是叶子节点，无左子树，记录K，无右子树，返回G，根据【左根右】的遍历规则，记录F，遍历F的右子树；
F的右子树不存在，返回F，E的右子树遍历完毕，返回A；
至此，A的右子树也遍历完毕；
最终我们得到上图的中序遍历为BDCAEHGKF，无非是按照遍历规则来的；
根据“中序遍历”的分析，相信先序遍历和后序遍历也可以轻松写出~
‘柒’ 二叉树的建立与遍历(C语言)
楼主你好~~~“ф”字符的源代码我忘记了，我这里有一个自己写过的遍历算法
#include<iostream.h>
typedef struct btnode
{
char data;
struct btnode *Lchild,*Rchild;
}*bitreptr;
void Create(bitreptr &p)
{
char n;
p=new btnode;
cin>>n;
if(n!='#')
{
p->data=n;
Create(p->Lchild);
Create(p->Rchild);
}
else
p=NULL;
}
void preorder(bitreptr &p)
{
if(p)
{
cout<<p->data<<" ";
preorder(p->Lchild);
preorder(p->Rchild);
}
}
void midorder(bitreptr &p)
{
if(p)
{
midorder(p->Lchild);
cout<<p->data<<" ";
midorder(p->Rchild);
}
}
void postorder(bitreptr &p)
{
if(p)
{
postorder(p->Lchild);
postorder(p->Rchild);
cout<<p->data<<" ";
}
}
void change(bitreptr &p)
{
bitreptr t,q;
if(p)
{
t=p->Lchild;
q=p->Rchild;
p->Lchild=q;
p->Rchild=t;
change(p->Lchild);
change(p->Rchild);
}
}
void main()
{
char i;
cout<<"请选择所需功能（'A'输出该二叉树序列，'B'输出交换后二叉树序列)"<<endl;
cin>>i;
bitreptr p;
cout<<"输入数据：";
Create(p);
switch(i)
{
case 'A':
{
cout<<"前序:";
preorder(p);
cout<<endl;
cout<<"中序:";
midorder(p);
cout<<endl;
cout<<"后序:";
postorder(p);
cout<<endl;
}break;
case 'B':
{
change(p);
cout<<"交换二叉树前序:";
preorder(p);
cout<<endl;
cout<<"交换二叉树中序:";
midorder(p);
cout<<endl;
cout<<"交换二叉树后序:";
postorder(p);
cout<<endl;
}break;
}
}
这个算法输入时要以“#”代表空节点，及将[测试数据] “ABCффDEфGффFффф”改成“ABC##DE#G##F###”即可。另外我的算法包括了二叉树左右子树交换的代码“change(bitreptr &p)”，只要楼主稍作修改就可以得到你想要的完美结果~
‘捌’ C语言二叉树的创建和遍历
我写了一个二叉树 你给看看 一定能行的 我自己用了
#include "stdio.h"
#include "malloc.h"
#include "string.h"
#include "stdlib.h"
#define Max 20 //结点的最大个数
typedef struct BinTNode{
char data;
struct BinTNode *lchild,*rchild;
}BinTNode,*BinTree; //自定义二叉树的结点类型
//定义二叉树的指针
int NodeNum,leaf; //NodeNum为结点数，leaf为叶子数
//==========以广义表显示二叉树==============
void DisTree(BinTree T)
{
if(T)
{
printf("%c",T->data);
if((T->lchild)||(T->rchild))
{
if(T->lchild)
{
printf("%c",'(');
DisTree(T->lchild);
}
if(T->rchild)
{
printf("%c",',');
DisTree(T->rchild);
printf("%c",')');
}
}
}
}
//==========基于先序遍历算法创建二叉树==============
//=====要求输入先序序列，其中加入虚结点"#"以示空指针的位置==========
BinTree CreatBinTree(BinTree T)
{
char ch;
ch=getchar();
if(ch=='#')
T=NULL;
else
{
if(!(T=(BinTNode *)malloc(sizeof(BinTNode))))
printf("Error!");
T->data=ch;
T->lchild=CreatBinTree(T->lchild);
T->rchild=CreatBinTree(T->rchild);
}
return T;
}
//========NLR 先序遍历=============
void Preorder(BinTree T)
{
if(T)
{
printf("%c",T->data);
Preorder(T->lchild);
Preorder(T->rchild);
}
}
//========LNR 中序遍历===============
void Inorder(BinTree T)
{
if(T){
Inorder(T->lchild);
printf("%c",T->data);
Inorder(T->rchild);
}
}
//==========LRN 后序遍历============
void Postorder(BinTree T)
{
if(T){
Postorder(T->lchild);
Postorder(T->rchild);
printf("%c",T->data);
}
}
//=====采用后序遍历求二叉树的深度、结点数及叶子数的递归算法========
int TreeDepth(BinTree T)
{
int hl,hr,max;
if(T){
hl=TreeDepth(T->lchild); //求左深度
hr=TreeDepth(T->rchild); //求右深度
max=hl>hr? hl:hr; //取左右深度的最大值
NodeNum=NodeNum+1; //求结点数
if(hl==0&&hr==0)
leaf=leaf+1; //若左右深度为0，即为叶子。
return(max+1);
}
else return(0);
}
//====利用"先进先出"（FIFO）队列，按层次遍历二叉树==========
void Levelorder(BinTree T)
{
int front=0,rear=1;
BinTNode *cq[Max],*p; //定义结点的指针数组cq
cq[1]=T; //根入队
while(front!=rear)
{
front=(front+1)%NodeNum;
p=cq[front]; //出队
printf("%c",p->data); //出队，输出结点的值
if(p->lchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->lchild; //左子树入队
}
if(p->rchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->rchild; //右子树入队
}
}
}
//==========主函数=================
void main()
{
BinTree T,root;
int i,depth;
printf("\n");
printf("输入完全二叉树的先序序列:"); //输入完全二叉树的先序序列，
// 用#代表虚结点，如ABD###CE##F##
root=CreatBinTree(T); //创建二叉树，返回根结点
DisTree(root);
printf("\n");
do //从菜单中选择遍历方式，输入序号。
{
printf("\t********** 菜单 ************\n");
printf("\n");
printf("\t1: 先序遍历\n");
printf("\t2: 中序遍历\n");
printf("\t3: 后序遍历\n");
printf("\t4: 该树的深度,结点数,叶子数\n");
printf("\t5: 层次遍历\n"); //按层次遍历之前，先选择4，求出该树的结点数。
printf("\t0: 退出\n");
printf("\t*******************************\n");
scanf("%d",&i);
//输入菜单序号（0-5）
switch(i)
{
case 1: {printf("Print Bin_tree Preorder: ");
Preorder(root); //先序遍历
}break;
case 2: {printf("Print Bin_Tree Inorder: ");
Inorder(root); //中序遍历
}break;
case 3: {printf("Print Bin_Tree Postorder: ");
Postorder(root); //后序遍历
}break;
case 4: {depth=TreeDepth(root); //求树的深度及叶子数
printf("树深=%d 树总结点数=%d",depth,NodeNum);
printf(" 树叶子数=%d",leaf);
}break;
case 5: {printf("LevePrint Bin_Tree: ");
Levelorder(root); //按层次遍历
}break;
default: exit(1);
}
}while(i>=0&&i<6);
}
兄弟你看看 不懂再往下留言 记得给我的劳动成果一点点奖励哦！！
‘玖’ 如何用C语言实现层次遍历二叉树
下面是c语言的前序遍历二叉树的算法，在这里假设的节点元素值假设的为字符型，
说明：算法中用到了结构体，也用到了递归的方法，你看看怎么样，祝你好运！
#include"stdio.h"
typedef
char
elemtype;
typedef
struct
node
//定义链表结构
{
elemtype
data;
//定义节点值
struct
note
*lchild;
//定义左子节点值
struct
note
*rchild;
//定义右节点值
}btree;
preorder(btree
*root)
//前序遍历
{
if(roof!=null)
//如果不是空节点
{
printf("%c\n",root->data);
//输出当前节点
preorder(root->lchild);
//递归前序遍历左子节点
preorder(root->rchild);
//递归前序遍历右子节点
}
return;
//结束
}
‘拾’ C语言二叉树遍历程序
先看下creat这个函数:
status creat(bitnode *t)/*先序建立二叉树*/
{
char ch;
ch=getch();putch(ch);
if(ch=='0') t=NULL;
else
{
t=(bitnode *)malloc(sizeof(bitnode));
if(!t)
exit(OVERFLOW);
t->data=ch;
creat(t->lchild);
creat(t->rchild);
}
return OK;
}
其中有句代码是t=(bitnode *)malloc(sizeof(bitnode));
这是给t赋值，由于t是参数，这样做是不能返回的。
我知道你的意思是想通过指针返回，但是那样的用法应该是对t所指向的变量赋值，也就是对*t赋值。
如果你还没理解的话看下函数里的递归调用：creat(t->lchild);调用函数后，本意是要给t->lchild赋值的，但是是做不到的，因为要改变一个变量的值的话，应该传的是它的地址。
可能你觉得有点乱了，我举个函数中用指针做参数来返回的例子：
假如要用指针返回一个整型的变量，那么指针应该是指向整型变量的，即int*
这里应该是要返回一个struct bitnode *类型的，也就是返回的值就是个指针，那么参数就应该是一个指向这种指针的指针，即struct bitnode **
可以这么修改：
status creat(bitnode **t) //多了个*
{
char ch;
ch=getch();putch(ch);
if(ch=='0') *t=NULL; //多了个*
else
{
*t=(bitnode *)malloc(sizeof(bitnode)); //多了个*
if(!*t) //多了个*
exit(OVERFLOW);
(*t)->data=ch;
creat(&(*t)->lchild); //注意不同
creat(&(*t)->rchild);
}
return OK;
}
主函数这么改
status main()
{
bitnode* t1; //多了个*
creat(&t1);
pre(t1,print); //少了个&
getch();
return 0;
}
另外一个编译错误就是
int pre(bitnode *t,status (*visit)())
指针函数后面应该带参数，改为
int pre(bitnode *t,status (*visit)(bitnode *))