c語言實現二叉樹的遍歷
㈠ 二叉樹遍歷(c語言實現)
#include <stdio.h>
#include <malloc.h>
typedef struct node{
int data;
struct node *lchild,*rchild;
}*treetp,tree;
treetp create (treetp t,int c);
void print1(treetp);
void print2(treetp);
void print3(treetp);
int number=0;
void main()
{
treetp t=0,r;
r=create (t,0);
printf("前序排列 ：");
print1 (r);
printf("\n中序排列 ：");
print2 (r);
printf("\n後序排列 ：");
print3 (r);
}
treetp create(treetp t,int c)
{
treetp p,di;
do{
scanf("%d",&c);
if (t==0)
{
t=(treetp)malloc(sizeof(tree));
t->lchild=t->rchild=0;
t->data=c;
}
else
{ p=t;
while(p!=0)
{
di=p;
if(c<(p->data))
p=p->lchild;
else
p=p->rchild;
}
if(c<(di->data))
{
treetp NEWdi=(treetp) malloc(sizeof(tree));
NEWdi->lchild=NEWdi->rchild=0;
NEWdi->data=c;
di->lchild=NEWdi;
}
else
{
treetp NEWdi=(treetp) malloc(sizeof(tree));
NEWdi->lchild=NEWdi->rchild=0;
NEWdi->data=c;
di->rchild=NEWdi;
}
}
++number;
}while(c!=0);
printf("葉子的數量：%d",number);
return t;
}
void print1(treetp t)
{
if (t!=0)
{
printf("%d ",t->data);
print1(t->lchild);
print1(t->rchild);
}
}
void print2(treetp t)
{
if (t!=0)
{
print2(t->lchild);
printf("%d ",t->data);
print2(t->rchild);
}
}
void print3(treetp t)
{
if (t!=0)
{
print3(t->lchild);
print3(t->rchild);
printf("%d ",t->data);
}
}
希望對你有幫助
㈡ 如何用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語言 二叉樹 遍歷問題
並不是你所說的那樣。
首先我們要知道遍歷是為了讓二叉樹的所有結點都掃描一遍，而前中後，三個遍歷方式，說的是他的顯示順序。
前序的特點：我們注意研究一下前序遍歷的結果，你會發現，對於每個二叉樹（只有根結點，左結點，右結點。一棵樹，是一個個小的二叉樹組成）在結果中，你都會發現，根結點必定在左結點前。你可以認真看看，就算，是子樹中也是根結點在左結點前。（比如，左結點成了另一個子樹的根結點，這個左結點對應的上一級根結點，也會顯示在這個左結點之前）
中序的特點：經過前序遍歷的分析 ，我們可以直接得出，中序遍歷結果中，每個根結點都會放在左結點和右結點中間。當然發生如，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語言寫二叉樹的遍歷
下面是一個用
遞歸方法
編的二叉樹遍歷程序，供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<malloc.h>
typedefstructBTree{
chardata;
structBTree*lChild;
structBTree*rChild;
}BinTree;
BinTree*CreateTree(BinTree*p){
charch;
scanf("%c",&ch);
if(ch=='#')returnNULL;
p=(BinTree*)malloc(sizeof(BinTree));
p->data=ch;
p->lChild=CreateTree(p->lChild);
p->rChild=CreateTree(p->rChild);
returnp;
}
intSumLeaf(BinTree*T){
intsum=0,m,n;
if(T){
if((!T->lChild)&&(!T->rChild))
sum++;
m=SumLeaf(T->lChild);
n=SumLeaf(T->rChild);
sum+=m+n;
}
returnsum;
}
voidQianXu(BinTree*T){
if(T){
printf("%c,",T->data);
QianXu(T->lChild);
QianXu(T->rChild);
}
}
voidZhongXu(BinTree*T){
if(T){
ZhongXu(T->lChild);
printf("%c,",T->data);
ZhongXu(T->rChild);
}
}
voidHouXu(BinTree*T){
if(T){
HouXu(T->lChild);
HouXu(T->rChild);
printf("%c,",T->data);
}
}
intDepth(BinTree*T){
intdep=0,depl,depr;
if(!T)dep=0;
else{
depl=Depth(T->lChild);
depr=Depth(T->rChild);
dep=1+(depl>depr?depl:depr);
}
returndep;
}
voidFreeTree(BinTree*T){
if(T){
FreeTree(T->lChild);
FreeTree(T->rChild);
free(T);
}
}
intmain(){
BinTree*Tree=NULL;
Tree=CreateTree(Tree);
//前序遍歷
printf("QianXuTraversal:");
QianXu(Tree);
printf(" ZhongXuTraversal:");
ZhongXu(Tree);
printf(" HouXuTraversal:");
HouXu(Tree);
printf(" Leaf'snumber:%d ",SumLeaf(Tree));
printf("Tree'sDepth:%d",Depth(Tree));
FreeTree(Tree);
return0;
}
輸入:#ABCD###E##FG#H##I#J##
輸出:
㈥ 用c語言實現二叉樹的程序，可以輸入輸出和遍歷
#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
const int MaxLength=10;//結點個數不超過10個
typedef struct tree
{
char data;
struct tree *lchild,*rchild;
}tree;
//先序遞歸 建立二叉樹
void Createbitree(tree* &T)
{
char ch;
ch=getchar();
if(ch=='#')
T=NULL;
else
{
T=(tree*)malloc(sizeof(tree));
T->data =ch;
Createbitree(T->lchild );
Createbitree(T->rchild );
}
}
//先序遞歸遍歷
void PreOrderTraverse(tree* T)
{
if(T)
{
cout<<T->data;
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
//中序遞歸遍歷
void InOrderTraverse(tree* T)
{
if(T)
{
InOrderTraverse(T->lchild);
cout<<T->data;
InOrderTraverse(T->rchild);
}
}
void PostOrderTraverse(tree* T)
{
if(T)
{
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout<<T->data;
}
}
//層序遍歷
void LevelOrderTraverse(tree* T)
{
tree* Q[MaxLength];
int front=0,rear=0;
tree* p;
if(T)//根結點入隊
{
Q[rear]=T;
rear=(rear+1)%MaxLength;
}
while(front!=rear)
{
p=Q[front]; //隊頭元素出隊
front=(front+1)%MaxLength;
cout<<p->data;
if(p->lchild)//左孩子不為空，入隊
{
Q[rear]=p->lchild;
rear=(rear+1)%MaxLength;
}
if(p->rchild)//右孩子不為空，入隊
{
Q[rear]=p->rchild;
rear=(rear+1)%MaxLength;
}
}
}
//主函數
void main()
{
cout<<"請按先序次序輸入二叉樹的數據:"<<endl;
tree* T;
Createbitree(T);
cout<<"二叉樹的先序序列為:"<<endl;
PreOrderTraverse(T);
cout<<endl<<"二叉樹的中序序列為:"<<endl;
InOrderTraverse(T);
cout<<endl<<"二叉樹的後序序列為:"<<endl;
PostOrderTraverse(T);
cout<<endl<<"二叉樹的層序序列為:"<<endl;
LevelOrderTraverse(T);
cout<<endl;
}
比如 1
2 3
4 5 6 7
按先序輸入是124##5##36##7##
㈦ C語言 二叉樹遍歷
因為沒有遞歸出口，而一開始while(T)會一直為真，進而一直執行 binlitree(T);，會一直遞歸下去。
//二叉樹的先序遍歷
int PreOrder(TreeNode *root)
{
if(!root)return 0;
printf("%c",root->data);
PreOrder(root->lchild);
PreOrder(root->rchild);
return 1;
}
㈧ 求二叉樹遍歷演算法C語言實現的
#include <stdio.h>
#include <malloc.h>
typedef struct node{
int data;
struct node *lchild,*rchild;
}*treetp,tree;
treetp create (treetp t,int c);
void print1(treetp);
void print2(treetp);
void print3(treetp);
int number=0;
void main()
{
treetp t=0,r;
r=create (t,0);
printf("前序排列 ：");
print1 (r);
printf("\n中序排列 ：");
print2 (r);
printf("\n後序排列 ：");
print3 (r);
}
treetp create(treetp t,int c)
{
treetp p,di;
do{
scanf("%d",&c);
if (t==0)
{
t=(treetp)malloc(sizeof(tree));
t->lchild=t->rchild=0;
t->data=c;
}
else
{ p=t;
while(p!=0)
{
di=p;
if(c<(p->data))
p=p->lchild;
else
p=p->rchild;
}
if(c<(di->data))
{
treetp NEWdi=(treetp) malloc(sizeof(tree));
NEWdi->lchild=NEWdi->rchild=0;
NEWdi->data=c;
di->lchild=NEWdi;
}
else
{
treetp NEWdi=(treetp) malloc(sizeof(tree));
NEWdi->lchild=NEWdi->rchild=0;
NEWdi->data=c;
di->rchild=NEWdi;
}
}
++number;
}while(c!=0);
printf("葉子的數量：%d",number);
return t;
}
void print1(treetp t)
{
if (t!=0)
{
printf("%d ",t->data);
print1(t->lchild);
print1(t->rchild);
}
}
void print2(treetp t)
{
if (t!=0)
{
print2(t->lchild);
printf("%d ",t->data);
print2(t->rchild);
}
}
void print3(treetp t)
{
if (t!=0)
{
print3(t->lchild);
print3(t->rchild);
printf("%d ",t->data);
}
}
㈨ 怎麼用c語言實現二叉樹的遍歷
這是用廣義表建立二叉樹並先序和中序遍歷二叉樹
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 100
typedef struct node
{
char data;
struct node *lchild;
struct node *rchild;
}BTNode,*BiTree;
void creategeneralizelist(BiTree *b,char *str)
{
BTNode *St[MaxSize],*p=NULL;
int top=-1,flag,j;
char ch;
for(j=0;(ch=str[j])!='#';j++)
{
switch(ch)
{
case '(':
top++;
St[top]=p;
flag=1;
break;
case ')':
top--;
break;
case ',':
flag=2;
break;
default:
p=(BiTree)malloc(sizeof(BTNode));
p->data=ch;
p->lchild=NULL;
p->rchild=NULL;
if(*b==NULL)
*b=p;
else
{
switch(flag)
{
case 1:
St[top]->lchild=p;
break;
case 2:
St[top]->rchild=p;
break;
}
}
}
}
}
void PreOrder(BiTree T)
{
if(T)
{
printf("%2c",T->data);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
void InOrder(BiTree T)
{
if(T)
{
InOrder(T->lchild);
printf("%2c",T->data);
InOrder(T->rchild);
}
}
int main(void)
{
BiTree T=NULL;
char str[MaxSize];/*用於保存用戶輸入的字元*/
printf("please input a string end with #:\n");
scanf("%s",str);
creategeneralize_list(&T,str);
printf("the result ofInOrder BiTree is:\n");
/* PreOrder(T);*/
InOrder(T);
getch();
return 1;
}
㈩ 求助：在數據結構中，用C語言如何編寫二叉樹的遍歷
#include "dataStructure.h "
typedef struct CharBiTNode {
char data;
struct CharBiTNode *lchild, *rchild;
} CharBiTNode, *CharBiTree;
typedef struct CharBiTQNode {
CharBiTree data;
struct CharBiTQNode *next;
} CharBiTQNode, *CharBiTQueuePtr;
typedef struct CharBiTQueue {
CharBiTQNode *front;
CharBiTQNode *rear;
} CharBiTQueue;
/**************** Char Queue *********************************/
Status initCharBiTQueue(CharBiTQueue& q) {
q.front = q.rear = (CharBiTQNode*)malloc(sizeof(CharBiTQNode));
if (!q.front)
return ERROR;
q.front-> next = NULL;
}
Boolean charBiTQueueEmpty(CharBiTQueue q) {
if (q.front == q.rear)
return TRUE;
else
return FALSE;
}
Status getCharBiTQueueLength(CharBiTQueue q) {
}
Status getCharBiTQueueHead(CharBiTQueue q, CharBiTree& e) {
e = q.front-> next-> data;
return OK;
}
Status enCharBiTQueue(CharBiTQueue& q, CharBiTree e) {
CharBiTQNode *newNode = (CharBiTQNode*)malloc(sizeof(CharBiTQNode));
if (!newNode)
return ERROR;
newNode-> data = e;
newNode-> next = NULL;
q.rear-> next = newNode;
q.rear = newNode;
return OK;
}
Status deCharBiTQueue(CharBiTQueue& q, CharBiTree& e) {
if (charBiTQueueEmpty(q)) {
return ERROR;
}
CharBiTQNode *p = q.front;
e = p-> next-> data;
q.front = q.front-> next;
free(p);
return OK;
}
Status charBiTQueueTraverse(CharBiTQueue q, Status (*visit)(CharBiTree e)) {
if (charBiTQueueEmpty(q)) {
return ERROR;
}
CharBiTQueuePtr p = q.front;
while(p) {
if (visit(p-> data) == ERROR)
return ERROR;
p = p-> next;
}
return OK;
}
/****************************** Char BiTree ****************************/
int depthLeft = 0;
int depthRight = 0;
int depth = 0;
Status initCharBiTree(CharBiTree& t) {
CharBiTNode *root = NULL;
root = (CharBiTNode*)malloc(sizeof(CharBiTNode));
if (!root)
return ERROR;
else
t = root;
t-> lchild = t-> rchild = NULL;
return OK;
}
Status createCharBiTree(CharBiTree& t) {
char ch;
cin > > ch;
if (ch == '# ')
t = NULL;
else {
if ((t = (CharBiTNode*)malloc(sizeof(CharBiTNode))) == ERROR)
return ERROR;
else {
t-> data = ch;
createCharBiTree(t-> lchild);
createCharBiTree(t-> rchild);
}
}
}
Boolean charBiTreeEmpty(CharBiTree t) {
}
Status charPreOrderTraverse(CharBiTree t, Status(*visit)(char e)) {
if (t != NULL){
if (visit(t-> data) == ERROR)
return ERROR;
if (charPreOrderTraverse(t-> lchild, visit) == ERROR)
return ERROR;
if (charPreOrderTraverse(t-> rchild, visit) == ERROR)
return ERROR;
} else
return OK;
}
Status charInOrderTraverse(CharBiTree t, Status(*visit)(char e)) {
if (t != NULL) {
if (charInOrderTraverse(t-> lchild, visit) == ERROR)
return ERROR;
if (visit(t-> data) == ERROR)
return ERROR;
if (charInOrderTraverse(t-> rchild, visit) == ERROR)
return ERROR;
} else
return OK;
}
Status charPostOrderTraverse(CharBiTree t, Status(*visit)(char e)) {
if (t != NULL) {
if (charPostOrderTraverse(t-> lchild, visit) == ERROR)
return ERROR;
if (charPostOrderTraverse(t-> rchild, visit) == ERROR)
return ERROR;
if (visit(t-> data) == ERROR)
return ERROR;
} else
return OK;
}
Status charLevelOrderTraverse(CharBiTree t, Status(*visit)(char e)) {
CharBiTQueue queue;
initCharBiTQueue(queue);
CharBiTree p;
if (t == NULL)
return ERROR;
else
enCharBiTQueue(queue, t);
while(!charBiTQueueEmpty(queue)) {
deCharBiTQueue(queue, p);
visit(p-> data);
if (p-> lchild != NULL) {
enCharBiTQueue(queue, p-> lchild);
}
if (p-> rchild != NULL) {
enCharBiTQueue(queue, p-> rchild);
}
}
}
int getCharBiTNodes(CharBiTree t, int& n) {
if (t != NULL) {
++n;
getCharBiTNodes(t-> lchild, n);
getCharBiTNodes(t-> rchild, n);
} else
return OK;
}
Status getCharBiTLeafs(CharBiTree t, int& n) {
if (t != NULL) {
if ( t-> lchild == NULL && t-> rchild == NULL)
++n;
getCharBiTLeafs(t-> lchild, n);
getCharBiTLeafs(t-> rchild, n);
} else
return OK;
}
int getCharBiTDepth(CharBiTree t) {
if (t == NULL) {
depth = 0;
} else {
depthLeft = getCharBiTDepth(t-> lchild);
depthRight = getCharBiTDepth(t-> rchild);
depth = 1 + (depthLeft > depthRight ? depthLeft:depthRight);
}
return depth;
}
Status printChar(char e) {
cout < <e;
return OK;
}
/* Test of char BiTree */
int main(char args[]) {
CharBiTree tree;
int numOfNode = 0, leafs = 0, depth = 0;
cout < < "請按先序輸入二叉樹元素 " < <endl;
createCharBiTree(tree);
cout < < "T(pre) = ";
charPreOrderTraverse(tree, printChar);
cout < <endl;
cout < < "T(in) = ";
charInOrderTraverse(tree, printChar);
cout < <endl;
cout < < "T(post) = ";
charPostOrderTraverse(tree, printChar);
cout < <endl;
cout < < "T(level) = ";
charLevelOrderTraverse(tree, printChar);
cout < <endl;
cout < < "The nodes of the tree is ";
getCharBiTNodes(tree, numOfNode);
cout < <numOfNode < <endl;
cout < < "The leafs of the tree is ";
getCharBiTLeafs(tree, leafs);
cout < <leafs < <endl;
cout < < "Tree Depth = ";
cout < <getCharBiTDepth(tree) < <endl;
system( "pause ");
}