/******************************************************/
/* 二叉树的建立深度优先遍历求叶子个数求深度 */
/******************************************************/
#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");
}
程序以调试通过！！！！！
二叉树的前中后遍历（递归与非递归）
#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;
}
[答案]：
//////////////////////////////////////////////////
使用方法：
输入树的节点，输入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);
}
兄弟你看看 不懂再往下留言 记得给我的劳动成果一点点奖励哦！！
本文链接：http://task.lmcjl.com/news/2034.html
