2 weixin 37134286 weixin_37134286 于 2017.01.04 09:49 提问

求二叉树叶子结点个数交换二叉树左右子树结果不对

// 二叉树的遍历与应用算法的设计与实现.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"

int _tmain(int argc, _TCHAR* argv[])
{
return 0;
}
//节点动态生成,可以充分利用存储空间
#include
#include
#include
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define STACK_INIT_SIZE 10//存储空间初始分配量
#define STACK_INCREAMENT 2//存储空间分配增量
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef char TElemType;
//二叉树的二叉链表存储结构
struct BiTNode
{
char data;//节点中的数据的类型
BiTNode lchild, *rchild;//左右孩子指针,指向节点自身
};
typedef BiTNode *BiTree;
/
**************************************栈的操作****************************************/
//栈的顺序存储结构
struct SqStack
{
BiTree base;//栈底指针
BiTree *top;//栈顶指针
int stacksize;//当前已分配的存储空间
};
//构造一个空栈S-------------------------《数据结构》P47
void InitStack(SqStack &S)
{
S.base = (BiTree
)malloc(STACK_INIT_SIZE*sizeof(BiTree));
if (!S.base)
exit(OVERFLOW);//存储空间分配失败
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
}
//若栈S为空,则返回TRUE,若栈S不空则返回FALSE
Status StackEmpty(SqStack S)
{
if (S.base == S.top)
return TRUE;
else
return FALSE;
}
//插入元素e为新的栈顶元素(入栈)
void Push(SqStack &S, BiTree e)
{
if (S.top - S.base >= S.stacksize)//栈满,追加存储空间
{
S.base = (BiTree*)realloc(S.base, (S.stacksize + STACK_INCREAMENT)*sizeof(BiTree));
if (!S.base)
exit(OVERFLOW);
S.top = S.base + S.stacksize;
S.stacksize += STACK_INCREAMENT;
}
//插入栈顶元素
(S.top) = e;
S.top++;//栈顶指针指向下一个
}
//若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK(出栈)
Status Pop(SqStack &S, BiTree &e)
{
if (S.top == S.base)
return ERROR;
else
e = *(--S.top);
return OK;
}
/
****************************************栈的操作部分END****************************************/
/*****************************************二叉树的操作部分****************************************/
//构造一个空的二叉树T
void InitBiTree(BiTree &T)
{
T = NULL;
}
//二叉树T存在,销毁二叉树T
void DestroyBiTree(BiTree &T)
{
if (T)
{
if (T->lchild)
DestroyBiTree(T->lchild);//销毁左孩子子树
if (T->rchild)
DestroyBiTree(T->rchild);//销毁右孩子子树
free(T);//释放根节点
T = NULL;
}
}
//构造二叉链表表示的二叉树T--------------------------------《数据结构》P131
//按照先序次序输入二叉树中节点的值,空格字符表示空树
void CreateBiTree(BiTree &T)
{
char h;//节点的数据的类型
scanf_s("%c", &h);
if (h == ' ')
T = NULL;
else
{
T = (BiTree)malloc(sizeof(BiTNode));
if (!T)
exit(OVERFLOW);
T->data = h;
CreateBiTree(T->lchild);//构造左子树
CreateBiTree(T->rchild);//构造右子树
}
}
//先序遍历中的(*visit函数),也就是一个输出函数
Status PrintElement(TElemType &e)
{
printf("%c", e);
return OK;
}
//用递归算法先序遍历二叉树
int PreOrderTraverse(BiTree T, Status(*Visit)(TElemType &e))
{

if (T)//二叉树不空
{
if (Visit(T->data))//访问根结点
{
if (PreOrderTraverse(T->lchild, Visit))//遍历左子树
{
if (PreOrderTraverse(T->rchild, Visit))//遍历右子树
{
return OK;
}
}
}
return ERROR;
}
else
{
return OK;
}
}

//用递归算法中序遍历二叉树
int InOrderTraverse(BiTree T, Status(*Visit)(TElemType &e))
{

if (T)//二叉树不空
{
if (InOrderTraverse(T->lchild, Visit))//遍历左子树
{
if (Visit(T->data))//访问根结点
{
if (InOrderTraverse(T->rchild, Visit))//遍历右子树
{
return OK;
}
}
}
return ERROR;
}
else
{
return OK;
}
}
//用递归算法后序遍历二叉树
int PostOrderTraverse(BiTree T, Status(*Visit)(TElemType &e))
{

if (T)//二叉树不空
{
if (PostOrderTraverse(T->lchild, Visit))//遍历左子树
{
if (PostOrderTraverse(T->rchild, Visit))//遍历右子树
{
if (Visit(T->data))//访问根结点
{
return OK;
}
}
}
return ERROR;
}
else
{
return OK;
}
}
//按照层次遍历二叉树
int front = 0, rear = 1;
void LevelOrderTraverse(BiTNode *T)
{
BiTNode *q[100];
q[0] = T;
while (front {
if (q[front])
{
printf("%c", q[front]->data);
q[rear++] = q[front]->lchild;
q[rear++] = q[front]->rchild;
front++;
}
else
{
front++;
}
}
}
//二叉树T存在,返回T的深度
int BiTreeDepth(BiTree T)
{
int i, j;
if (!T)
return 0;
if (T->lchild)
i = BiTreeDepth(T->lchild);//i为左子树的深度
else
i = 0;
if (T->rchild)
j = BiTreeDepth(T->rchild);
else
j = 0;
return i>j ? i + 1 : j + 1;//T的深度为其左右子树中的大者加1
}
//统计二叉树中结点的个数(先序)
int CountNode(BiTree T)
{
static int count = 0;
if (!T) count = 0;
else{
count = CountNode(T->lchild) + CountNode(T->rchild) + 1;
}
return count;
}
////统计二叉树中叶子结点的个数(先序)
//int CountLeaf(BiTree T, Status(*Visit)(TElemType &e))
//{
//int count = 0;
//if (T)
//{
//if ((!T->lchild) && (!T->rchild))
//{
//count++;
//}
//
//}
//else
//{
//CountLeaf(T->lchild, Visit);
//CountLeaf(T->rchild, Visit);
//}
//return count;
//}
//递归统计二叉树中叶子结点的个数(先序)
int CountLeaf(BiTree &T)
{
if (T == NULL)
{
return 0;
}
else if (T->lchild == NULL && T->rchild == NULL)
{
return 1;
}
else
{
return (CountLeaf(T->lchild) + CountLeaf(T->rchild));
}
}
//递归法将二叉树的左右子树互换
void Exchange(BiTree &T, Status(*Visit)(TElemType &e))
{
BiTNode *temp;
if (T)
{
Exchange(T->lchild, PrintElement);
Exchange(T->rchild, PrintElement);
temp = T->lchild;
T->lchild = T->rchild;
T->rchild = temp;
}
}
int main()
{
BiTree T;
InitBiTree(T);
printf("\n构造空的二叉树后,树的深度=%d\n", BiTreeDepth(T));
printf("\n请按照先序的次序输入二叉树(如:ab三个空格表示以a为根节点,b为左子树的二叉树):\n");
CreateBiTree(T);//建立二叉树T
printf("\n建立二叉树后,树的深度为:%d\n", BiTreeDepth(T));
printf("先序递归遍历二叉树:");
PreOrderTraverse(T, PrintElement);
printf("\n中序递归遍历二叉树:");
InOrderTraverse(T, PrintElement);
printf("\n后序递归遍历二叉树:");
PostOrderTraverse(T, PrintElement);
printf("\n层序递归遍历二叉树:");
LevelOrderTraverse(T);
printf("\n\n二叉树中结点的个数:%d\n", CountNode(T));
CountNode(T);
printf("\n二叉树中叶子结点的个数:%d\n", T);
CountLeaf(T);
printf("\n左右子树交换:%d\n", T);
Exchange(T, PrintElement);
system("pause");

}

1个回答

Tiger_Zhao
Tiger_Zhao   Rxr 2017.01.04 10:38
已采纳

main()中的printf(),前面还用BiTreeDepth(T)CountNode(T)做参数,后面怎么直接用T做参数了?

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
二叉树的创建,遍历,求高度,算出节点数,算出叶子节点数,左右子树的交换,二叉树的销毁。
//对二叉树的创建,遍历二叉树,求树的深度,求结点个数,求叶子结点个数 #include   #include  typedef char ElemType;   //定义树的结点类型  typedef struct BiTNode   //树的结构体定义 {     ElemType data;     struct BiTNode *lchild;    struct
实验2.2:二叉树遍历的一些应用
题目:以实验2.1的二叉链表为存储结构,编写程序实现求二叉树结点个数、叶子结点个数、二叉树的高度以及交换二叉树所有左右子树的操作。部分代码:求二叉树结点个数://求二叉树结点个数 int Size(BinaryTreeNode *t){ if(!t) return 0; return Size(t->LChild) + Size(t->RChild) + 1; }求二叉...
二叉树交换左右子树
#include #include typedef struct Node{    int data;  struct Node* LChild;  struct Node* RChild; }Tree; void createTree(Tree **T) {  int data = 1;  scanf("%d",&data);  if ( data != 0)  {
C++算法之 求二叉树中叶子节点的个数 与 判断两棵二叉树是否结构相同
//叶子节点的个数 /* (1)如果二叉树为空,返回0 (2)如果二叉树不为空且左右子树为空,返回1 (3)如果二叉树不为空,且左右子树不同时为空,返回左子树中叶子节点个数加上右子树中叶子节点个数 */ int GetLeafNodeNum(BTree* root) { if(root == NULL) return 0; if(root->m_pLeft == NUL
建立二叉树并求指定结点路径
能够按先序遍历的次序输入二叉树的各个结点,并能够输出中序遍历的序列号,以及指定的路径 和三个应用:求二叉树的深度 二叉树的叶子结点个数和将二叉树左右子树交换
二叉树(7)----求二叉树叶子节点个数,递归和非递归
1、二叉树定义: typedef struct BTreeNodeElement_t_ { void *data; } BTreeNodeElement_t; typedef struct BTreeNode_t_ { BTreeNodeElement_t *m_pElemt; struct BTreeNode_t_ *m_pLeft; struct B
数据结构课程设计 二叉树
数据结构有关二叉树的课程设计!二叉树的! 1.建立二叉树的存储结构 2.求解二叉树的中序遍历 3.求二叉树指定结点的路径 4.求二叉树的深度 5.求二叉树的叶子结点个数 6.将二叉树左右子树交换
数据结构(C语言实现) - 二叉树的基本操作(建立,遍历,结点数,叶子结点数,高度,按树状打印,输出叶子结点等)
通常,对二叉树的操作都是利用二叉链表进行的。 二叉链表:包括三个域-数据域,左孩子,右孩子的结点结构的二叉树存储结点。 二叉链表的存储结构如下: typedef char DataType; typedef struct node /*二叉树的存储结构*/ { DataType data; struct node *Lchild; struct node *Rchild;
C语言实现交换二叉树左右子树
C语言实现二叉树左右子树的交换:代码解释:     创建树:         1> 首先声明一个根结点bt,给系统输入一个字符,并进行,如果字符是'#',则返回NULL;         2> 如果字符不是'#',则给根结点建立建立结点,并将刚输入的字符赋给该结点的数据域 ch ,之后将这个结点的的递归调用下一个结点赋给这个结点的左子树;         3> 如果遇到输入的值为...
二叉树先序后序递归建立,前中后序层次非递归遍历,以及统计叶子结点个数以及树的深度
下面的代码实现了二叉树的先序或者后序递归建立,然后实现了二叉树的非递归的先序中序后序遍历,还有层次遍历,以及统计树的叶子结点个数和树的深度。其中非递归的先中后序遍历用到了链栈,层次遍历用到了队列。 编程平台为Visual Studio 2012,语言为C,但不是纯C,比如用到了C++的引用机制以及变量的随时定义(在纯C中,变量必须在函数一开始的地方全部声明)。 // 二叉树非递归遍历.cp