君，已阅读到文档的结尾了呢~~
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
编写递归算法,计算二叉树中叶子结点的数目。.doc
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口看见二叉树的各种递归算法就倒了怎么办？ - 知乎2被浏览268分享邀请回答2添加评论分享收藏感谢收起温馨提示！由于新浪微博认证机制调整，您的新浪微博帐号绑定已过期，请重新绑定！&&|&&
LOFTER精选
网易考拉推荐
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
阅读(1626)|
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
历史上的今天
loftPermalink:'',
id:'fks_',
blogTitle:'二叉树__递归实现：中根(中序)遍历、先根遍历、后根遍历_非递归实现：中根(中序)遍历、先根遍历、后根遍历',
blogAbstract:'\r\n一、中根(中序)遍历\r\n//中序:左-&根-&右\r\n递归实现：template&typename elemType& void binaryTreeType&elemType&::inorder(nodeType&elemType& *p) { &&&&& if( p != NULL ) &&&&& { &&&&&&&&&& inorder(p-&llink); &&&&&&&&&& cout && p-&info && \" \"; &&&&&&&&&& inorder(p-&rlink);&&&&&&&} ',
blogTag:'',
blogUrl:'blog/static/',
isPublished:1,
istop:false,
modifyTime:6,
publishTime:4,
permalink:'blog/static/',
commentCount:0,
mainCommentCount:0,
recommendCount:0,
bsrk:-100,
publisherId:0,
recomBlogHome:false,
currentRecomBlog:false,
attachmentsFileIds:[],
groupInfo:{},
friendstatus:'none',
followstatus:'unFollow',
pubSucc:'',
visitorProvince:'',
visitorCity:'',
visitorNewUser:false,
postAddInfo:{},
mset:'000',
remindgoodnightblog:false,
isBlackVisitor:false,
isShowYodaoAd:true,
hostIntro:'',
hmcon:'1',
selfRecomBlogCount:'0',
lofter_single:''
{list a as x}
{if x.moveFrom=='wap'}
{elseif x.moveFrom=='iphone'}
{elseif x.moveFrom=='android'}
{elseif x.moveFrom=='mobile'}
${a.selfIntro|escape}{if great260}${suplement}{/if}
{list a as x}
推荐过这篇日志的人：
{list a as x}
{if !!b&&b.length>0}
他们还推荐了：
{list b as y}
转载记录：
{list d as x}
{list a as x}
{list a as x}
{list a as x}
{list a as x}
{if x_index>4}{break}{/if}
${fn2(x.publishTime,'yyyy-MM-dd HH:mm:ss')}
{list a as x}
{if !!(blogDetail.preBlogPermalink)}
{if !!(blogDetail.nextBlogPermalink)}
{list a as x}
{if defined('newslist')&&newslist.length>0}
{list newslist as x}
{if x_index>7}{break}{/if}
{list a as x}
{var first_option =}
{list x.voteDetailList as voteToOption}
{if voteToOption==1}
{if first_option==false},{/if}&&“${b[voteToOption_index]}”&&
{if (x.role!="-1") },“我是${c[x.role]}”&&{/if}
&&&&&&&&${fn1(x.voteTime)}
{if x.userName==''}{/if}
网易公司版权所有&&
{list x.l as y}
{if defined('wl')}
{list wl as x}{/list}二叉树的各种操作的（递归非递归）的实现，如（递归非递归）先序后序中序层次遍历　二叉树的高度　叶子节点数，所有节点数
//BinaryTree.h
#define CHAR
//当CHAR定义时，用字符的处理模式
//当CHAR没有被定义时，采用整数处理模式
#ifdef CHAR
//数据类型的定义
typedef char DataT
typedef int D
#define true 1
#define false 0
//二叉树的链式存储结构
typedef struct BiTNode
struct BiTNode *
struct BiTNode *
} BiTNode,* BiT
//队列的链式存储结构
//队列节点存储结构
typedef struct Node
struct Node *
} Node, *pN
//队列存储结构
typedef struct Queue
} LinkQueue, *pLinkQ
//栈节点类型
typedef struct StackNode
struct StackNode *
StackNode,*pStackN
typedef struct LinkStack
} LinkStack,*pLinkS
pLinkStack
InitLinkStack()
pLinkStack s=(pLinkStack) malloc(sizeof( LinkStack)) ;
s-&stacksize=0;
s-&top=NULL;
void ClearLinkStack(pLinkStack s)
while( s-&stacksize )
Pop(s,&ptr);
void DestroyLinkStack(pLinkStack s)
if( s-&stacksize)
ClearLinkStack(s);
void Push(pLinkStack s,BiTree ptr )
pStackNode p=(pStackNode ) malloc( sizeof(StackNode)) ;
p-&next=NULL;
p-&next=s-&
s-&stacksize++;
void Pop(pLinkStack s,BiTree *ptr)
if(s-&stacksize==0)
printf(&the linkstack is null.can't pop anything\n&);
pStackNode p=s-&
s-&top=s-&top-&
s-&stacksize--;
GetLinkStackSize(pLinkStack s)
return s-&
BiTree GetTop(pLinkStack s )
if(s-&stacksize==0)
printf(&the linkstack is null&);
return s-&top-&
int IsLinkStackEmpty(pLinkStack s)
if(s-&stacksize==0)
void LinkStackTraverse(pLinkStack s, void (*Visit)(DataType data) )
pStackNode p=s-&
Visit(p-&ptr-&data) ;
void print(DataType data)
printf(&%c&,data);
int main()
pLinkStack s=InitLinkStack();
printf(&gettop :\n&);
for( i=0 ;i&100;i++)
Push(s,i);
DataType datatop= GetTop(s);
printf(&%d &,datatop);
printf(&\nIsLinkStackEmpty %d&,IsLinkStackEmpty(s) );
printf(&\n traverse the LinkStack:\n&);
LinkStackTraverse(s ,print);
printf(&\n the current LinkStack' size :%d\n&,GetLinkStackSize(s) );
Pop(s,&data);
printf(&Pop %d \n&,data);
printf(&\n the current LinkStack' size :%d\n&,GetLinkStackSize(s) );
Pop(s,&data);
printf(&Pop %d \n&,data);
printf(&LinkStack clear!\n&);
ClearLinkStack(s);
printf(&LinkStack destroy!\n&);
DestroyLinkStack(s);
pLinkQueue InitLinkQueue()
pLinkQueue q=(pLinkQueue ) malloc(sizeof(LinkQueue)) ;
q-&front=NULL;
q-&rear=NULL;
q-&queuesize=0;
IsLinkQueueEmpty(pLinkQueue q)
if(q-&queuesize ==0)
int GetLinkQueueLength(pLinkQueue q)
return q-&
void EnLinkQueue(pLinkQueue q, BiTree ptr)
pNode p=(pNode ) malloc(sizeof(Node) ) ;
p-&next=NULL;
if(q-&queuesize==0)
//刚开始时队列为空时，对队头指针进行赋值
q-&front=p;
q-&rear=p;
q-&rear-&next=p;
q-&rear=p;
q-&queuesize++;
void DeLinkQueue(pLinkQueue q,BiTree *ptr)
if(q-&queuesize==0)
printf(&the queue is null,can't get anything\n&);
if(q-&front==q-&rear) //只有一个节点时，无节点的情况上面已经考虑了
*ptr=q-&front-&
free(q-&front);
q-&front=NULL;
q-&rear=NULL;
pNode p=q-&
q-&front=q-&front-&
q-&queuesize--;
GetHead(pLinkQueue q,DataType *x)
if(q-&queuesize==0)
return 0 ;
*x= q-&front-&ptr-&
return 1 ;
void LinkQueueTraverse(pLinkQueue q, void (*Visit) (DataType data) )
pNode p=q-&
printf(&the LinkQueue is null\n&);
Visit(p-&ptr-&data);
void ClearLinkQueue(pLinkQueue q)
while(q-&queuesize)
DeLinkQueue( q, &ptr );
void DestroyLinkQueue(pLinkQueue q)
if(q-&queuesize!=0)
ClearLinkQueue(q) ;
//BinartTree.c
#include&stdio.h&
#include&string.h&
#include&malloc.h&
#include&stdlib.h&
#include&BinaryTree.h&
CreateBiTree( )
char ch=getchar();
// scanf(&%c&,&ch);
if( ch=='#')
return NULL;
bt=(BiTree) malloc( sizeof(BiTNode) );
bt-&lchild=CreateBiTree();
bt-&rchild=CreateBiTree();
*后序遍历形式销毁二叉树
void DestroyBiTree(BiTree root)
DestroyBiTree(root-&lchild);
DestroyBiTree(root-&rchild);
free(root);
* 采用先序遍历递归方式查找
BiTree SearchBiTree(BiTree root ,DataType x)
return NULL;
if(root-&data==x)
ptr= SearchBiTree(root-&lchild ,x) ;
if(ptr==NULL)
return SearchBiTree(root-&rchild ,x) ;
* 返回当前结点的左孩子
BiTree LchildNode(BiTree ptr)
return ptr-&
*返回当前结点的右孩子
BiTree RchildNode(BiTree ptr)
return ptr-&
*二叉树的查找采用中序遍历非递归方式
BiTree SearchBiTree2(BiTree root ,DataType x)
return NULL;
BiTree ptr=
pLinkStack s=InitLinkStack();
while(ptr || !IsLinkStackEmpty(s) )
if(ptr-&data==x)
Push(s ,ptr ) ;
Pop(s, &ptr) ;
DestroyLinkStack(s) ;
void Visit(char
printf(&%c &,ch);
void PreOrderTraverse(BiTree root )
Visit(root-&data);
PreOrderTraverse(root-&lchild);
PreOrderTraverse(root-&rchild);
void InOrderTraverse(BiTree root )
InOrderTraverse(root-&lchild );
Visit(root-&data);
InOrderTraverse(root-&rchild);
*计算二叉树的高度
int TreeHeight(BiTree root)
if(root==NULL)
int lheight= TreeHeight(root-&lchild) ;
int rheight= TreeHeight(root-&rchild) ;
(lheight&rheight ? lheight+1:rheight+1) ;
*采用非递归层次遍历的方式计算二叉树的高度
TreeHeight2( BiTree root )
pLinkQueue q=InitLinkQueue();
EnLinkQueue(q , root);
int height=1; //头节点入队列
while(! IsLinkQueueEmpty(q )
DeLinkQueue(q,&ptr );
// Visit(ptr-&data);
if(ptr-&lchild)
EnLinkQueue(q, ptr-&lchild );
if(ptr-&rchild)
EnLinkQueue(q, ptr-&rchild);
if( ptr-&lchild || ptr-&rchild)
DestroyLinkQueue(q);
*非递归的中序遍历的形式计算二叉树的高度
TreeHeight3( BiTree root )
if(!root )
BiTree ptr=
pLinkStack s=InitLinkStack();
int height=0;
while( ptr
|| !IsLinkStackEmpty(s) )
Push(s,ptr) ;
int stacksize=GetLinkStackSize(s);
printf(&stacksize :%d\n&,stacksize);
height=height & stacksize ? height :
//其实二叉树的高度等于栈的最大深度 这样是错误的，当是后序遍历的时候成立
Pop(s,&ptr ) ;
//Visit(ptr-&data);
DestroyLinkStack(s);
void PostOrderTraverse(BiTree root )
PostOrderTraverse(root-&lchild);
PostOrderTraverse(root-&rchild);
Visit(root-&data);
bool IsTreeEmpty(BiTree root)
if(root==NULL)
void LevelOrderTraverse(BiTree root)
pLinkQueue q=InitLinkQueue();
EnLinkQueue(q , root);
while(! IsLinkQueueEmpty(q )
DeLinkQueue(q,&ptr );
Visit(ptr-&data);
if(ptr-&lchild)
EnLinkQueue(q, ptr-&lchild );
if(ptr-&rchild)
EnLinkQueue(q, ptr-&rchild);
DestroyLinkQueue(q);
//非递归形式的先序遍历
PreOrderTraverse2(BiTree root)
if( !root)
BiTree ptr=
pLinkStack s=InitLinkStack();
while ( ptr ||
! IsLinkStackEmpty(s))
Visit(ptr-&data );
Push(s,ptr );
Pop(s, &ptr);
DestroyLinkStack(s);
//非递归形式的中序遍历序
// 此方法思路不是太清晰
void InOrderTraverse2( BiTree root )
if(!root )
BiTree ptr=
pLinkStack s=InitLinkStack();
while( ptr )
Push(s,ptr);
Pop(s, &ptr);
Visit(ptr-&data) ;
while( ptr )
Push(s,ptr);
} while ( ! IsLinkStackEmpty(s) ) ;
void InOrderTraverse2( BiTree root )
if(!root )
BiTree ptr=
pLinkStack s=InitLinkStack();
while( ptr
|| !IsLinkStackEmpty(s) )
Push(s,ptr) ;
Pop(s,&ptr ) ;
Visit(ptr-&data);
DestroyLinkStack(s);
*非递归形式的计算叶子节点个数(遍历采用非递归中序遍历)
int CountLeaf2(BiTree root)
int count=0;
BiTree ptr=
pLinkStack s=InitLinkStack();
while(ptr || !IsLinkStackEmpty(s) )
Push(s,ptr);
Pop(s,&ptr);
if(ptr-&lchild==NULL && ptr-&rchild==NULL)
DestroyLinkStack(s);
*计算叶子节点的个数
int CountLeaf(BiTree root)
BiTree ptr=
if(ptr==NULL)
else if(ptr-&lchild==NULL && ptr-&rchild==NULL)
return CountLeaf(ptr-&lchild)+CountLeaf(ptr-&rchild);
*统计左右孩子都存在的节点的个数
*这个方法比较巧妙
*思想：根节点判断是不是，在递归左右子树
int CountDoubleson(BiTree root)
BiTree ptr=
if(ptr ==NULL)
if(ptr-&lchild && ptr-&rchild)
n=1; //没有用return 1
return CountDoubleson(ptr-&lchild)+CountDoubleson(ptr-&rchild) +n;
*统计节点的个数
int CountNodes(BiTree root)
if(root ==NULL)
return CountNodes(root-&lchild)+CountNodes(root-&rchild)+1;
BiTree Swap(BiTree root)
return NULL;
BiTree ptr=(BiTree) malloc(sizeof(BiTNode)) ;
ptr-&data=root-&
ptr-&rchild=Swap(root-&lchild);
ptr-&lchild=Swap(root-&rchild);
//这句必须有，把头指针返回
CopyBiTree(BiTree input )
if(!input)
output=NULL;
output=(BiTree) malloc(sizeof(BiTNode)) ;
output-&data=input-&
output-&lchild=CopyBiTree(input-&lchild );
output-&rchild=CopyBiTree(input-&rchild );
bool IsEqualBiTree(BiTree root1,BiTree root2)
if(root1==NULL && root2==NULL)
if( root1 && root2 && root1-&data==root2-&data)
return IsEqualBiTree(root1-&lchild,root2-&lchild) && IsEqualBiTree(root1-&rchild ,root2-&rchild) ;
void DisplayBiTree(BiTree root)
printf(&%c&,root-&data);
if(root-&lchild!=NULL || root-&rchild!=NULL)
printf(&(&) ;
DisplayBiTree(root-&lchild) ;
if(root-&rchild !=NULL)
printf( &,&) ;
DisplayBiTree(root-&rchild);
printf( &) &);
//----------------竖向打印二叉树--------------------------------------
void DisplayBiTree(BiTree root,int nLayer)
if(root==NULL)
DisplayBiTree(root-&rchild,nLayer+3);
for(i=0;i&nLi++)
printf(& &);
printf(&%c\n&,root-&data );
DisplayBiTree(root-&lchild,nLayer+3 );
void LevelOrderTraverse(BiTree root)
pLinkQueue q=InitLinkQueue();
EnLinkQueue(q , root);
while(! IsLinkQueueEmpty(q )
DeLinkQueue(q,&ptr );
Visit(ptr-&data);
if(ptr-&lchild)
EnLinkQueue(q, ptr-&lchild );
if(ptr-&rchild)
EnLinkQueue(q, ptr-&rchild);
DestroyLinkQueue(q);
int main()
BiTree T=CreateBiTree();
DisplayBiTree( T );
BiTree T1=CreateBiTree();
// BiTree T1=CopyBiTree(T) ;
BiTree T1=Swap(T);
bool result=IsEqualBiTree(T,T1);
if( result==0 )
printf(&\nthe two trees are
not equal.\n&);
printf(&\nthe two trees are equal.\n &);
printf(&PreOrderTraverse :\n&);
PreOrderTraverse(T);
printf(&\n&);
PreOrderTraverse(T1);
printf(&\n&);
printf(&InOrderTraverse :\n&);
InOrderTraverse(T);
printf(&\n&);
InOrderTraverse(T1);
printf(&\n&);
printf(&PostOrderTraverse :\n&);
PostOrderTraverse(T);
printf(&\n&);
PostOrderTraverse(T1);
printf(&\n&);
printf(&LevelOrderTraverse
LevelOrderTraverse(T);
printf(&\n&);
printf(&PreOrderTraverse2 非递归形式的先序遍历:\n&);
PreOrderTraverse2(T);
printf(&\n&);
printf(&InOrderTraverse2 非递归形式的中序遍历:\n&);
InOrderTraverse2(T);
printf(&\n&);
DataType x='a';
BiTree p=SearchBiTree(T,x);
if(p==NULL)
printf(&don't search the %c \n&,x);
printf(&can search the %c\n&,p-&data) ;
p=SearchBiTree2(T,x);
if(p==NULL)
printf(&don't search the %c \n&,x);
printf(&can search the %c\n&,p-&data) ;
printf(&the tree's height : %d\n&,TreeHeight(T));
printf(&the tree's height 非递归层次遍历形式 : %d\n&,TreeHeight2(T));
printf(&the tree's height 非递归采用用户栈形式 : %d\n&,TreeHeight3(T));
printf(&the tree's countleaf:%d\n&,CountLeaf(T));
printf(&the tree's countleaf 非递归形式:%d\n&,CountLeaf2(T));
printf(&the tree's CountDoubleson :%d\n& ,CountDoubleson(T));
printf(&the tree's Nodes:%d\n&,CountNodes(T));
DestroyBiTree(T);
看过本文的人也看了：
我要留言技术领域：
取消收藏确定要取消收藏吗？
删除图谱提示你保存在该图谱下的知识内容也会被删除，建议你先将内容移到其他图谱中。你确定要删除知识图谱及其内容吗？
删除节点提示无法删除该知识节点，因该节点下仍保存有相关知识内容！
删除节点提示你确定要删除该知识节点吗？