一.遍历算法应用

1.输出二叉树中的结点

void PreOrder(BiTree root)
{ if(root != NULL) { printf("%d",root->data); // 假设数据为int类型 PreOrder(root->RChild); // 遍历左子树 PreOrder(root->RChild); // 遍历右子树 //上例为先序遍历，中序遍历和后序遍历，只是printf()位置不同。 }
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
 

2.输出二叉树中的叶子结点

void PreOrder(BiTree root)
{ if(root != NULL) { if(root->LChild == NULL && root->RChild == NULL) { printf("%d",root->data); } PreOrder(root->LChild); PreOrder(root->RChild); }
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
 

3.统计叶子结点数目

int LeafCount = 0; 

void leaf(BiTree root)
{ if(root != NULL) { leaf(root->LChild); leaf(root->RChild); if(root->LChild == NULL && root->RChild == NULL) { LeafCount++; } }
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
 

4.建立二叉链表方式存储的二叉树

void CreateBiTree(BiTree * bt)
{ char ch; ch = getchar(); if(ch == '.') { *bt = NULL; } else { *bt = (BiTree)malloc(sizeof(BiTree)); (*bt)->data = ch; CreateBiTree(&((*bt)->LChild)); CreateBiTree(&((*bt)->RChild)); }
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
 

5.求二叉树的高度

// 先序遍历求二叉树的高度
int PostTreeDepth(BiTree bt, int h)
{ if(bt != NULL) { if(h>depth) { depth = h; } PostTreeDepth(bt->LChild，h+1); PostTreeDepth(bt->RChild，h+1); }
}


// 后序遍历求二叉树的高度
int PostTreeDepth(BiTree bt)
{ int hl,hr,max; if( bt != NULL) { hl = PostTreeDepth(bt->LChild); hr = PostTreeDepth(bt->RChild); max = hl>hr?hl:hr; return max+1; } else return 0;
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
 

6.按树状打印二叉树

void PrintfTree(BiTree bt,int nLayer)
{
if(bt == NULL)return ;
PrintfTree(bt->RChild,nLayer+1);
for(int i = 0;i<nLayer;i++)
{ printf(" ");
}
printf("%c\n",bt->data);
PrintfTree(bt->LChild,nLayer+1);
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
 

若有错误，欢迎指正批评，欢迎评论。
每文一句：欲戴王冠，必承其重。哪有什么好命天赐，不都是一路披荆斩棘才换来的。

文章来源: zxfdog.blog.csdn.net，作者：Fdog_，版权归原作者所有，如需转载，请联系作者。

原文链接：zxfdog.blog.csdn.net/article/details/105009469