#include
#include
typedef char datatype;
typedef struct tnode {
datatype data;
struct tnode *lchild, *rchild;
} BiTNode, *BiTree;
void visit(BiTree p); /*输出p指针指向的结点*/
void Preorder(BiTree T); /*前序遍历*/
void Inorder(BiTree T); /*中序遍历*/
void Postorder(BiTree T); /*后序遍历*/
BiTree CreateTree(); /*以前序遍历的顺序建立二叉树*/
int deep(BiTree T); /*求二叉树深度*/
int leaf(BiTree T); /*求叶子结点数*/
int OneChild(BiTree T); /*求1度结点数*/
int TwoChild(BiTree T); /*求2度结点数*/
void Exchange(BiTree T); /*二叉树左右子树交换*/
BiTree InorderLastNode(BiTree T); /*找二叉树中序遍历最后一个结点*/
void visit(BiTree p) { /*输出p指针指向的结点*/
if (p->data != ' ') {
printf("%c ", p->data);
}
}
void Preorder(BiTree T) { /*前序遍历*/
if (T != NULL) {
visit(T); //访问根节点
Preorder(T->lchild); //访问左子节点
Preorder(T->rchild); //访问右子节点
}
}
void Inorder(BiTree T) { /*中序遍历*/
if (T != NULL) {
Inorder(T->lchild); //访问左子节点
visit(T); //访问根节点
Inorder(T->rchild); //访问右子节点
}
}
void Postorder(BiTree T) { /*后序遍历*/
if (T != NULL) {
Postorder(T->lchild); //访问左子节点
Postorder(T->rchild); //访问右子节点
visit(T); //访问根节点
}
}
BiTree CreateTree() { /*以前序遍历的顺序建立二叉树*/
char ch;
BiTree T;
if ((ch = getchar()) == ' ') {
return NULL;
}
else {
T = (BiTree)malloc(sizeof(BiTNode)); //生成根节点
T->data = ch;
T->lchild = CreateTree(); //构造左子树
T->rchild = CreateTree(); //构造右子树
return T;
}
}
int deep(BiTree T) { /*求二叉树深度*/
int lh, rh;
if (T == NULL) {
return 0;
}
else {
lh = deep(T->lchild);
rh = deep(T->rchild);
}
return (lh > rh ? lh : rh) + 1;
}
int leaf(BiTree T) { /*求叶子结点数*/
int m, n;
if (!T) { /*空树没有叶子*/
return 0;
}
else if (!T->lchild && !T->rchild) { /*叶子结点*/
return 1;
}
else { /*左子树的结点数加上右子树的结点数*/
m = leaf(T->lchild);
n = leaf(T->rchild);
return m + n;
}
}
int OneChild(BiTree T) { /*求1度结点数*/
int n = 0;
if (T == NULL) {
return 0;
}
else if ((T->lchild == NULL&&T->rchild != NULL) || (T->lchild != NULL&&T->rchild == NULL)) {
n = 1;
}
return OneChild(T->lchild) + OneChild(T->rchild) + n;
}
int TwoChild(BiTree T) { /*求2度结点数*/
int n = 0;
if (T == NULL) {
return 0;
}
else if ((T->lchild != NULL&&T->rchild != NULL))
{
n = 1;
}
return TwoChild(T->lchild) + TwoChild(T->rchild) + n;
}
void Exchange(BiTree T) { /*二叉树左右子树交换*/
BiTree temp;
if (T) {
temp = T->lchild;
T->lchild = T->rchild;
T->rchild = temp;
Exchange(T->lchild);
Exchange(T->rchild);
}
}
BiTree InorderLastNode(BiTree T) { /*找二叉树中序遍历最后一个结点*/
if(T)
while (T->rchild)
{
T = T->rchild;
}
return T;
}
int main() {
BiTree T;
printf("以前序遍历的二叉树:");/*一个空格表示该结点只有右孩子，无空格表示该结点有左孩子，两个空格表示上述结点有右孩子，三个空格表示输入结束*/
T = CreateTree();
printf("\n先序遍历:");
Preorder(T);
printf("\n");
printf("\n中序遍历:");
Inorder(T);
printf("\n");
printf("\n后序遍历:");
Postorder(T);
printf("\n");
printf("\n树的深度=%d\n", deep(T));
printf("叶子结点数=%d\n", leaf(T));
printf("1度结点数=%d\n", OneChild(T));
printf("2度结点数=%d\n", TwoChild(T));
printf("\n二叉树中序遍历最后一个结点为:%c", InorderLastNode(T));
printf("\n");
printf("\n交换后的二叉树先序遍历为:");
Exchange(T); Preorder(T);
printf("\n交换后的二叉树中序遍历为:");
Inorder(T);
printf("\n交换后的二叉树后序遍历为:");
Postorder(T);
printf("\n");
return 0;
}
二叉树如图所示：
运行代码如下图所示：
中序遍历最后一个结点什么都没有，请大神帮忙指正
