二叉树及其应用

一、统计二叉树度为1的结点个数 

问题描述

计算二叉树中度为1的结点个数。

输入描述

按照先序遍历序列输入一行字符串，以大写字母和#分别表示结点和虚结点。

输出描述

输出对应二叉树的度为1的结点个数。

样例输入

AB#DE##F##C##                  

样例输出

1

#include<stdio.h>
typedef struct BiNode{char data;struct BiNode *lchild,*rchild;
}BiNode,*BiTree;
void CreateBiTree(BiTree&T)
{char ch;scanf("%c",&ch);if(ch=='#')T=NULL;else{T=new BiNode;T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}
}
int NodeCount(BiTree T){if(T==NULL) return 0;int m = NodeCount(T->lchild);//左子树上度为1的结点数int n = NodeCount(T->rchild);//右子树上度为1的结点数int k=0;if((T->lchild==NULL&&T->rchild!=NULL)|| (T->lchild!=NULL&&T->rchild==NULL))k=1;return m+n+k;
}
int main(){BiTree T;CreateBiTree(T);printf("%d",NodeCount(T));return 0;
}

 二、二叉树的高度

问题描述

编写递归函数，求一棵二叉树的高度。

输入描述

按照先序遍历次序输入一行字符串，以大写英文字母和#分别表示结点和虚结点。

输出描述

输出相应二叉树的高度。

样例输入

AB##CDE##F###                    

样例输出

4

#include<stdio.h>
typedef struct BiNode{char data;struct BiNode *lchild,*rchild;
}BiNode,*BiTree;
void CreateBiTree(BiTree&T)
{char ch;scanf("%c",&ch);if(ch=='#')T=NULL;else{T=new BiNode;T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}
}
int HighTree(BiTree T)
{if(T==NULL)return 0;else{int left_depth=HighTree(T->lchild);int right_depth=HighTree(T->rchild);return (left_depth>right_depth?left_depth:right_depth)+1;}
}
int main()
{BiTree T;CreateBiTree(T);printf("%d",HighTree(T));return 0;
}

 三、交换二叉树中每个结点的左孩子和右孩子

问题描述

以二叉链表作为二叉树的存储结构，交换二叉树中每个结点的左孩子和右孩子，

输入描述

按照先序遍历次序输入一行字符串，以大写英文字母和#分别表示结点和虚结点。

输出描述

先输出原来的二叉树的中序遍历结果，再输出交换后二叉树的中序遍历结果。

样例输入

ABC##DE#G##F###                    

样例输出

交换前的中序遍历结果为：C B E G D F A
交换后的中序遍历结果为：A F D G E B C

#include<stdio.h>
typedef struct BiNode{char data;struct BiNode *lchild,*rchild;
}BiNode,*BiTree;
void CreateBiTree(BiTree&T)
{char ch;scanf("%c",&ch);if(ch=='#')T=NULL;else{T=new BiNode;T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}
}
void SwapTree(BiTree &T)
{if(T==NULL)return;BiNode* temp=T->lchild;T->lchild=T->rchild;T->rchild=temp;SwapTree(T->lchild);SwapTree(T->rchild);
}
void PrintTree(BiTree T)
{if(T!=NULL){PrintTree(T->lchild);printf("%c ",T->data);PrintTree(T->rchild);}}
int main()
{BiTree T;CreateBiTree(T);printf("交换前的中序遍历结果为：");PrintTree(T);printf("\n");SwapTree(T);printf("交换后的中序遍历结果为：");PrintTree(T);return 0;
}