二叉树实现问题

C语言 码拜 4年前 (2017-05-02) 738次浏览
代码如下:

#include<stdio.h>
#include<stdlib.h>
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) {           /*求二叉树深度*/
	if (T) {
		int leftdeep = deep(T->lchild);
		int rightdeep = deep(T->rchild);
		return leftdeep >= rightdeep ? leftdeep + 1 : rightdeep + 1;
	}
	else {
		return 0;
	}
}
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) {    /*二叉树左右子树交换*/
	if (T) {
		BiTree temp = T->lchild;
		T->lchild = T->rchild;
		T->rchild = temp;
		Exchange(T->lchild);
		Exchange(T->rchild);
	}
}
BiTree InorderLastNode(BiTree T) {   /*找二叉树中序遍历最后一个结点*/
	datatype s;
	if (T) {
		InorderLastNode(T->lchild);
		s = T->data;
		InorderLastNode(T->rchild);
	}
	return s;
}
int main() {
	BiTree T;
	T = CreateTree();
	printf("\n以前序遍历的二叉树:");
	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("1度结点数=%d\n", OneChild(T));
	printf("2度结点数=%d\n", TwoChild(T));
	Exchange(T);
	printf("\n");
	InorderLastNode(T);
	return 0;
}

报错:
1>d:\visual studio 2015\projects\20170401\20170401\sy14.cpp(132): error C2440: “return”: 无法从“datatype”转换为“BiTree”
1>  d:\visual studio 2015\projects\20170401\20170401\sy14.cpp(132): note: 从整型转换为指针类型要求 reinterpret_cast、C 样式转换或函数样式转换
高手讨教,怎么修改

解决方案

100

可以这样改:

#include<stdio.h>
#include<stdlib.h>
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);   /*二叉树左右子树交换*/
datatype 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) {           /*求二叉树深度*/
	if (T) {
		int leftdeep = deep(T->lchild);
		int rightdeep = deep(T->rchild);
		return leftdeep >= rightdeep ? leftdeep + 1 : rightdeep + 1;
	}
	else {
		return 0;
	}
}
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) {    /*二叉树左右子树交换*/
	if (T) {
		BiTree temp = T->lchild;
		T->lchild = T->rchild;
		T->rchild = temp;
		Exchange(T->lchild);
		Exchange(T->rchild);
	}
}
datatype InorderLastNode(BiTree T) {   /*找二叉树中序遍历最后一个结点*/
	datatype s;
	if (T) {
		InorderLastNode(T->lchild);
		s = T->data;
		InorderLastNode(T->rchild);
	}
	return s;
}
int main() {
	BiTree T;
	T = CreateTree();
	printf("\n以前序遍历的二叉树:");
	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("1度结点数=%d\n", OneChild(T));
	printf("2度结点数=%d\n", TwoChild(T));
	Exchange(T);
	printf("\n");
	InorderLastNode(T);
	return 0;
}

50

BiTree InorderLastNode(BiTree T) {   /*找二叉树中序遍历最后一个结点*/
    datatype s;
    if (T) {
        InorderLastNode(T->lchild);
        s = T->data;
        InorderLastNode(T->rchild);
    }
    return s;
}

这段程序也可以这样改

BiTree *InorderLastNode(BiTree T) {   /*找二叉树中序遍历最后一个结点*/
    BiTree *Result =NULL;
    if(T->lchild) {
        Result = InorderLastNode(T->lchild);
    } else if(T->rchild) {
        Result = InorderLastNode(T->lchild);
    } else {
        Result = T;
    }
    return Result;
}

CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明二叉树实现问题
喜欢 (0)
[1034331897@qq.com]
分享 (0)