本文目錄一覽：
急急急！求C語言的數據結構二叉樹遞歸遍歷程序！
/******************************************************/
/* 二叉樹的建立深度優先遍歷求葉子個數求深度 */
/******************************************************/
#include “stdio.h”
#include “string.h”
#include “stdlib.h”
#define NULL 0
typedef struct bitnode{
int data;
struct bitnode *lchild,*rchild;
}bitnode,*bitree;
/*創建一個二杈樹以#號結束*/
bitree create(bitree t){
char ch;
ch=getchar();
if(ch==’#’)
t=NULL;
else{
t=(bitree)malloc(sizeof(bitnode));
t-data=ch;
t-lchild=create(t-lchild);
t-rchild=create(t-rchild);
}
return t;
}
/*遞歸遍歷*/
void preorder(bitree t){
if(t){
printf(“%c”,t-data); /*先序*/
preorder(t-lchild);
/*printf(“%c”,t-data); 中序*/
preorder(t-rchild);
/*printf(“%c”,t-data); 後序*/
}
}
/*求深度*/
int depth(bitree t){
int depthval,depl,depr;
if(!t)
depthval=0;
else{
depl=depth(t-lchild);
depr=depth(t-rchild);
depthval=1+(depldepr?depl:depr);
}
return depthval;
}
/*求葉子數*/
int countleaf(bitree t){
int count=0;
if(!t)
count=0;
else if((!t-lchild)(!t-rchild))
count++;
else
count=countleaf(t-lchild)+countleaf(t-rchild);
return count;
}
/*主函數*/
main(){
bitree t=NULL;
printf(“\nplease input a tree:”);
t=create(t);
preorder(t);
printf(“\ndepth:%d\nleave:%d\n”,depth(t),countleaf(t));
system(“pause”);
}
程序以調試通過！！！！！
C語言二叉樹的遍歷。
二叉樹的前中後遍歷（遞歸與非遞歸）
#includestdio.h
#includestdlib.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語言數據結構「遍歷二叉樹」
[答案]：
//////////////////////////////////////////////////
使用方法：
輸入樹的節點，輸入0結束
1 2 3 4 5 6 7 8 9 0
中序列印
1-2-3-4-5-6-7-8-9-
後序列印
9-8-7-6-5-4-3-2-1-
前序列印
1-2-3-4-5-6-7-8-9-
程序原碼：
//////////////////////////////////////////////////
#includestdlib.h
#includestdio.h
typedef struct tree
{
struct tree *left;
int date;
struct tree *right;
}treenode,*b_tree;
///////按順序插入節點/////////////////////
b_tree insert(b_tree root,int node)
{
b_tree newnode;
b_tree currentnode;
b_tree parentnode;
newnode=(b_tree)malloc(sizeof(treenode));
newnode-date=node;
newnode-right=NULL;
newnode-left=NULL;
if(root==NULL)
return newnode;
else
{
currentnode=root;
while(currentnode!=NULL)
{
parentnode=currentnode;
if(currentnode-datenode)
currentnode=currentnode-left;
else
currentnode=currentnode-right;
}
if(parentnode-datenode)
parentnode-left=newnode;
else
parentnode-right=newnode;
}
return root;
}
//////建立樹///////////////////
b_tree creat(int *date,int len)
{
b_tree root=NULL;
int i;
for(i=0;ilen;i++)
root=insert(root,date[i]);
return root;
}
//////中序列印////////////////
void print1(b_tree root)
{if(root!=NULL)
{
print1(root-left);
printf(“%d-“,root-date);
print1(root-right);
}
}
//////後序列印////////////////
void print2(b_tree root)
{if(root!=NULL)
{
print2(root-left);
print2(root-right);
printf(“%d-“,root-date);
}
}
//////前序列印////////////////
void print3(b_tree root)
{if(root!=NULL)
{ printf(“%d-“,root-date);
print3(root-left);
print3(root-right);
}
}
///////測試函數//////////////////
void main()
{
b_tree root=NULL;
int i,index;
int value;
int nodelist[20];
printf(“輸入樹的節點，輸入0結束\n”);
index=0;
scanf(“%d”,value);
while(value!=0)
{
nodelist[index]=value;
index=index+1;
scanf(“%d”,value);
}
root=creat(nodelist,index);
printf(“\n中序列印\n”);
print1(root);
printf(“\n後序列印\n”);
print2(root);
printf(“\n前序列印\n”);
print3(root);
}
悉雨辰寂
二叉樹的創建和遍歷
我寫了一個二叉樹 你給看看 一定能行的 我自己用了
#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=hlhr? hl:hr; //取左右深度的最大值
NodeNum=NodeNum+1; //求結點數
if(hl==0hr==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=0i6);
}
兄弟你看看 不懂再往下留言 記得給我的勞動成果一點點獎勵哦！！
原創文章，作者：小藍，如若轉載，請註明出處：https://www.506064.com/zh-tw/n/231428.html
微信掃一掃 
支付寶掃一掃 