① 如何用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語言實現二叉樹的先序,中序,後序的遞歸和非遞歸演算法和層次遍歷演算法
#include<malloc.h> // malloc()等
#include<stdio.h> // 標准輸入輸出頭文件，包括EOF(=^Z或F6)，NULL等
#include<stdlib.h> // atoi()，exit()
#include<math.h> // 數學函數頭文件，包括floor()，ceil()，abs()等
#define ClearBiTree DestroyBiTree // 清空二叉樹和銷毀二叉樹的操作一樣
typedef struct BiTNode
{
int data; // 結點的值
BiTNode *lchild,*rchild; // 左右孩子指針
}BiTNode,*BiTree;
int Nil=0; // 設整型以0為空
void visit(int e)
{ printf("%d ",e); // 以整型格式輸出
}
void InitBiTree(BiTree &T)
{ // 操作結果：構造空二叉樹T
T=NULL;
}
void CreateBiTree(BiTree &T)
{ // 演算法6.4：按先序次序輸入二叉樹中結點的值(可為字元型或整型，在主程中定義)，
// 構造二叉鏈表表示的二叉樹T。變數Nil表示空(子)樹。修改
int number;
scanf("%d",&number); // 輸入結點的值
if(number==Nil) // 結點的值為空
T=NULL;
else // 結點的值不為空
{ T=(BiTree)malloc(sizeof(BiTNode)); // 生成根結點
if(!T)
exit(OVERFLOW);
T->data=number; // 將值賦給T所指結點
CreateBiTree(T->lchild); // 遞歸構造左子樹
CreateBiTree(T->rchild); // 遞歸構造右子樹
}
}
void DestroyBiTree(BiTree &T)
{ // 初始條件：二叉樹T存在。操作結果：銷毀二叉樹T
if(T) // 非空樹
{ DestroyBiTree(T->lchild); // 遞歸銷毀左子樹，如無左子樹，則不執行任何操作
DestroyBiTree(T->rchild); // 遞歸銷毀右子樹，如無右子樹，則不執行任何操作
free(T); // 釋放根結點
T=NULL; // 空指針賦0
}
}
void PreOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始條件：二叉樹T存在，Visit是對結點操作的應用函數。修改演算法6.1
// 操作結果：先序遞歸遍歷T，對每個結點調用函數Visit一次且僅一次
if(T) // T不空
{ Visit(T->data); // 先訪問根結點
PreOrderTraverse(T->lchild,Visit); // 再先序遍歷左子樹
PreOrderTraverse(T->rchild,Visit); // 最後先序遍歷右子樹
}
}
void InOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始條件：二叉樹T存在，Visit是對結點操作的應用函數
// 操作結果：中序遞歸遍歷T，對每個結點調用函數Visit一次且僅一次
if(T)
{ InOrderTraverse(T->lchild,Visit); // 先中序遍歷左子樹
Visit(T->data); // 再訪問根結點
InOrderTraverse(T->rchild,Visit); // 最後中序遍歷右子樹
}
}
void PostOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始條件：二叉樹T存在，Visit是對結點操作的應用函數
// 操作結果：後序遞歸遍歷T，對每個結點調用函數Visit一次且僅一次
if(T) // T不空
{ PostOrderTraverse(T->lchild,Visit); // 先後序遍歷左子樹
PostOrderTraverse(T->rchild,Visit); // 再後序遍歷右子樹
Visit(T->data); // 最後訪問根結點
}
}
void main()
{
BiTree T;
InitBiTree(T); // 初始化二叉樹T
printf("按先序次序輸入二叉樹中結點的值,輸入0表示節點為空，輸入範例：1 2 0 0 3 0 0\n");
CreateBiTree(T); // 建立二叉樹T
printf("先序遞歸遍歷二叉樹：\n");
PreOrderTraverse(T,visit); // 先序遞歸遍歷二叉樹T
printf("\n中序遞歸遍歷二叉樹：\n");
InOrderTraverse(T,visit); // 中序遞歸遍歷二叉樹T
printf("\n後序遞歸遍歷二叉樹：\n");
PostOrderTraverse(T,visit); // 後序遞歸遍歷二叉樹T
}
③ 關於C語言二叉樹
首先二叉樹的結點是由做孩子指針*lchild 右孩子指針*rchild 以及數據成員data
L表示左孩子R表示右孩子T表示他們的父結點
後序遍歷的訪問順序是LRT
中序遍歷的訪問順序是LTR
前序遍歷的訪問順序是TLR
其中說的前中後就是指訪問父結點的次序；
拓撲圖在這里沒法給出啊。。。
--------------------------------------------
這是我用C++類寫的二叉樹的頭文件，裡面有幾個函數你可能用不到，你主要看看那幾個遍歷函數
#include<iostream>
using namespace std;
typedef char elemType;
struct bnode
{
bnode *lchild,*rchild;
elemType data;
};
class BinaryTree
{
public:
BinaryTree();
void create(bnode* &tempR);
void visite(bnode *T);
void preorder(bnode *T);
void inorder(bnode *T);
void postorder(bnode *T);
int high(bnode *T);
void convert(bnode* &tempR,string &a,int i);
void (bnode *T,bnode *&T1);
void level(bnode *T,int i);
void swap(bnode *T);
bnode *root;
private:
int count;
};
BinaryTree::BinaryTree()
{
root = NULL;
count = 0;
}
void BinaryTree::create(bnode* &tempR)
{
elemType x;
cin>>x;
if(x == '.')
{
tempR = NULL;
}
else
{
tempR = new bnode;
count++;
tempR->data = x;
create(tempR->lchild);
create(tempR->rchild);
}
}
void BinaryTree::visite(bnode *T)
{
if(T!=NULL)
cout<<T->data<<' ';
}
void BinaryTree::preorder(bnode *T)
{
if(T!=NULL)
{
visite(T);
preorder(T->lchild);
preorder(T->rchild);
}
}
void BinaryTree::inorder(bnode *T)
{
if(T!=NULL)
{
inorder(T->lchild);
visite(T);
inorder(T->rchild);
}
}
void BinaryTree::postorder(bnode *T)
{
if(T!=NULL)
{
postorder(T->lchild);
postorder(T->rchild);
visite(T);
}
}
int BinaryTree::high(bnode *T)
{
if(T==NULL)
return 0;
else if(high(T->lchild)>high(T->rchild))
return high(T->lchild)+1;
else
return high(T->rchild)+1;
}
void BinaryTree::level(bnode *T,int i)
{
if(T!=NULL)
{
level(T->lchild,i+1);
visite(T);
cout<<i<<' ';
level(T->rchild,i+1);
}
}
void BinaryTree::convert(bnode *&T,string &a,int i)
{
elemType x;
if(i<=a.length())
{
x = a[i-1];
T = new bnode;
count++;
T->data = x;
convert(T->lchild,a,2*i);
convert(T->rchild,a,2*i+1);
}
else
{
T=NULL;
}
}
void BinaryTree::(bnode *T,bnode *&T1)
{
elemType x;
if(T!=NULL)
{
x=T->data;
if(x == '.')
{
T1 = NULL;
}
else
{
T1 = new bnode;
T1->data = x;
T1->lchild = NULL;
T1->rchild = NULL;
(T->lchild,T1->lchild);
(T->rchild,T1->rchild);
}
}
}
void BinaryTree::swap(bnode *T)
{
if(T!=NULL)
{
bnode *temp;
temp=T->lchild;
T->lchild=T->rchild;
T->rchild=temp;
swap(T->lchild);
swap(T->rchild);
}
}
④ C語言 樹的生成和遍歷
#include //頭文件
#include
typedef struct BiTNode
{
char data;
struct BiTNode *lchild,*rchild;
}
BiTNode,*BiTree;//定義結點類型
BiTree CreateBiTree()//創建樹
{
char p;BiTree T;
scanf("%c",&p);
if(p==' ')
T=NULL;
else
{
T=(BiTNode *)malloc(sizeof(BiTNode));//為結點開辟空間
T->data=p;
T->lchild=CreateBiTree();
T->rchild=CreateBiTree();
}
return (T);
}
void PreOrder(BiTree T)//先序
{
if(T!=NULL)
{
printf("%c",T->data);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
void InOrder(BiTree T)//中序
{
if(T!=NULL)
{
InOrder(T->lchild);
printf("%c",T->data);
InOrder(T->rchild);
}
}
void PostOrder(BiTree T)//後序
{
if(T!=NULL)
{
PostOrder(T->lchild);
PostOrder(T->rchild);
printf("%c",T->data);
}
}
void main()//主函數
{
BiTree Ta;
Ta=CreateBiTree();
printf("先序遍歷:");
printf("\n");
PreOrder(Ta);
printf("\n");
printf("中序遍歷:");
printf("\n");
InOrder(Ta);
printf("\n");
printf("後序遍歷:");
printf("\n");
PostOrder(Ta);
}
給你個簡單的例子：
AB***
其中*代表空格
復雜點的例子
ABC**DE*f**g***
其中*代表空格
⑤ 急求C語言寫二叉樹的遍歷
下面是一個用
遞歸方法
編的二叉樹遍歷程序，供lz參考。
#include
<stdio.h>//頭文件
#include
<stdlib.h>
#include
<malloc.h>
typedef
struct
bitnode
{
char
data;
struct
bitnode
*lchild,*rchild;
}
bitnode,*bitree;//定義結點類型
bitree
createbitree()//創建樹
{
char
p;bitree
t;
scanf("%c",&p);
if(p=='
')
t=null;
else
{
t=(bitnode
*)malloc(sizeof(bitnode));//為結點開辟空間
t->data=p;
t->lchild=createbitree();
t->rchild=createbitree();
}
return
(t);
}
void
preorder(bitree
t)//
先序
{
if(t!=null)
{
printf("%c",t->data);
preorder(t->lchild);
preorder(t->rchild);
}
}
void
inorder(bitree
t)//
中序
{
if(t!=null)
{
inorder(t->lchild);
printf("%c",t->data);
inorder(t->rchild);
}
}
void
postorder(bitree
t)//
後序
{
if(t!=null)
{
postorder(t->lchild);
postorder(t->rchild);
printf("%c",t->data);
}
}
void
main()//主函數
{
bitree
ta;
ta=createbitree();
printf("先序遍歷:");
printf("\n");
preorder(ta);
printf("\n");
printf("中序遍歷:");
printf("\n");
inorder(ta);
printf("\n");
printf("後序遍歷:");
printf("\n");
postorder(ta);
}
⑥ 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語言)
樓主你好~~~「ф」字元的源代碼我忘記了，我這里有一個自己寫過的遍歷演算法
#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<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語言 關於二叉樹的創建和遍歷(中序遍歷)
#include <stdio.h>
#include <stdlib.h> //需要包含這個頭文件，後面exit()用到
#include <malloc.h>
#define OVERFLOW 1
#define NULL 0
#define OK 1
typedef struct BiTNode
{ char data;
struct BiTNode * lchild, * rchild;
} BiTNode, * BiTree;
int flag=0;//增加這個變數，用於標記當前是否是根結點
BiTNode *head;//增加這個變數，用於記錄根結點
CreateBiTree ( BiTree T )
{ char ch;
fflush(stdin);//建議加上這個鍵盤緩沖區清空處理，防止讀入了上次輸入的回車
scanf ("%c",&ch);
if (ch=='*') T=NULL;
else {
T=( BiTNode * ) malloc( sizeof( BiTNode ) ) ;
if(T==NULL) exit(OVERFLOW); //不是判斷if (T) ，而是判斷if(T==NULL)
if(flag==0)//如果當前是第一個結點(根結點)
{
head=T;//將head指向根結點
flag=1;//flag置為1
}
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);}
return OK;
}
PreOrderTraverse(BiTree T)
{if(T)
{printf("%c",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);}
}
main()
{
BiTree t;
CreateBiTree(t);
PreOrderTraverse(head);//由於在CreateBiTree執行後，t指向的位置已經變為了葉結點了，所以這里傳入的應該是根結點head的地址
}
⑩ 二叉樹的基本操作 C語言版的
#include<stdio.h>
#include<malloc.h>
int count=0;
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{
if(!(T = (BiTNode * )malloc(sizeof(BiTNode)))) return;
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}//CreatBiTree
int PreOrder(BiTree T)//先序遍歷二叉樹的遞歸演算法
{
if (!T) return 0;
printf("%c ",T->data); // 訪問結點
PreOrder(T->lchild); // 遍歷左子樹
PreOrder(T->rchild);// 遍歷右子樹
return 1;
}
int InOrder(BiTree T)//先序遍歷二叉樹的遞歸演算法
{
if (!T) return 0;
InOrder(T->lchild); // 遍歷左子樹
printf("%c ",T->data); // 訪問結點
InOrder(T->rchild);// 遍歷右子樹
return 1;
}
int PostOrder(BiTree T)//先序遍歷二叉樹的遞歸演算法
{
if (!T) return 0;
PostOrder(T->lchild); // 遍歷左子樹
PostOrder(T->rchild);// 遍歷右子樹
printf("%c ",T->data); // 訪問結點
return 1;
}
int CountLeaf (BiTree T){
//返回指針T所指二叉樹中所有葉子結點個數
if (!T ) return 0;//空樹
if (!T->lchild && !T->rchild) return 1;//只有樹根
int m;
int n;
m = CountLeaf( T->lchild);
n = CountLeaf( T->rchild);
return (m+n);
} // CountLeaf
void main(){
int a;
BiTree T;
CreateBiTree(T);
printf("先序遍歷：");
PreOrder(T);
printf("中序遍歷：");
InOrder(T);
printf("後序遍歷：");
PostOrder(T);
a=CountLeaf(T);
printf("葉子節點個數：");
printf("%d",a);
}