二叉树的动态链式存储实现—C语言

WindCoder

发布于 2018-09-20 10:33:42

2K0

发布于 2018-09-20 10:33:42

文章被收录于专栏：WindCoderWindCoder

头文件

ElemType.h

/***
*ElemType.h - ElemType的定义
*
****/

#ifndef ELEMTYPE_H
#define ELEMTYPE_H

typedef char ElemType;

int compare(ElemType x, ElemType y);
void visit(ElemType e);

#endif /* ELEMTYPE_H */

DynaLnkBiTree.h

/***
*DynaLnkBiTree.h - 动态链式二叉树的定义
*
****/

#if !defined(DYNALNKBITREE_H)
#define DYNALNKBITREE_H

#include "ElemType.h"

/*------------------------------------------------------------
// 二叉树结构的定义
------------------------------------------------------------*/

typedef struct BiNode
{
	ElemType data;				// 结点数据元素
	struct BiNode *l;			// 结点的左孩子指针
	struct BiNode *r;			// 结点的右孩子指针
} BinTNode, *BinTree;

enum LR {LEFT, RIGHT};


/*------------------------------------------------------------
// 二叉树的基本操作
------------------------------------------------------------*/

bool InitBinTree(BinTree *T);
void DestroyBinTree(BinTree *T);
bool CreateBinTree(BinTree *T);
void ClearBinTree(BinTree *T);
bool BinTreeEmpty(BinTree T);
int  BinTreeDepth(BinTree T);
BinTNode *Root(BinTree T);
bool NodeExist(BinTree T, BinTNode* n);
ElemType Value(BinTree T, BinTNode* n);
void Assign(BinTree T, BinTNode* n, ElemType e);
BinTNode* Parent(BinTree T, BinTNode* n);
BinTNode* LeftChild(BinTree T, BinTNode* n);
BinTNode* RightChild(BinTree T, BinTNode* n);
BinTNode* LeftSibling(BinTree T, BinTNode* n);
BinTNode* RightSibling(BinTree T, BinTNode* n);
void InsertNode(BinTree T, BinTNode* p, LR d, BinTNode* n);
void DeleteNode(BinTree T, BinTNode* p, LR d);
void PreOrderTraverse(BinTree T, void (*fp)(ElemType));
void InOrderTraverse(BinTree T, void (*fp)(ElemType));
void PostOrderTraverse(BinTree T, void (*fp)(ElemType));
void LevelOrderTraverse(BinTree T, void (*fp)(ElemType));

#endif /* DYNALNKBITREE_H */

主函数

Lab.cpp

#include <stdio.h>
#include <stdlib.h>
#include "DynaLnkBiTree.h"

int main()
{
	BinTree T,V;
	InitBinTree(&T);
    InitBinTree(&V);
	CreateBinTree(&T);
	system("pause");
	return 0;
}

#include <iostream>
using namespace std;

int main(void)
{



	system("pause");
	return 0;
}

实现函数

ElemType.cpp

/***
*ElemType.cpp - ElemType的实现
*
****/

#include <stdio.h>
#include "ElemType.h"

int compare(ElemType x, ElemType y)
{
	return(x-y);
}

void visit(ElemType e)
{
	printf("%cn", e);
}

DynaLnkBiTree.cpp

/***
*DynaLnkBiTree.cpp - 动态链式二叉树，即二叉树的动态链式存储实现
*
*
*题目：实验6-1 二叉树的动态链式存储实现
*
*
****/

#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>
#include <memory.h>
#include <assert.h>
#include "DynaLnkBiTree.h"

/*------------------------------------------------------------
操作目的：	初始化二叉树
初始条件：	无
操作结果：	构造空二叉树
函数参数：
		BinTree *T	待初始化的二叉树
返回值：
		bool		操作是否成功
------------------------------------------------------------*/
bool InitBinTree(BinTree *T)
{


	*T = NULL;
	return true;

}

/*------------------------------------------------------------
操作目的：	销毁二叉树
初始条件：	二叉树T已存在
操作结果：	销毁二叉树
函数参数：
		BinTree *T	待销毁的二叉树
返回值：
		无
------------------------------------------------------------*/
void DestroyBinTree(BinTree *T)
{
	assert(T != NULL);

	DestroyBinTree(&(*T)->l);
	DestroyBinTree(&(*T)->r);
	free(T);
	*T = NULL;
}

/*------------------------------------------------------------
操作目的：	创建二叉树
初始条件：	二叉树T已存在
操作结果：	销毁二叉树
函数参数：
		BinTree *T	二叉树T
返回值：
		bool		操作是否成功
参考提示：
			请按照教材131页算法6.4的方式来创建二叉树。
------------------------------------------------------------*/
bool CreateBinTree(BinTree *T)
{
	char c=NULL;
	scanf("%c",c);
	fflush(stdin);
	if (c == ' ')
	{
		*T = NULL;
		return true;
	}
	else
	{
		T = (BinTree*)malloc(sizeof(BinTNode));
		if (*T == NULL)
		{
			return false;
		}
		(*T)->data = c;

		CreateBinTree(&(*T)->l);
		CreateBinTree(&(*T)->r);
	}
	return true;
}

/*------------------------------------------------------------
操作目的：	清空二叉树
初始条件：	二叉树T已存在
操作结果：	清空二叉树
函数参数：
		BinTree *T	待清空的二叉树
返回值：
		无
------------------------------------------------------------*/
void ClearBinTree(BinTree *T)
{
	assert( T != NULL);
	ClearBinTree(&(*T)->l);
	ClearBinTree(&(*T)->r);
	T = NULL;

}

/*------------------------------------------------------------
操作目的：	二叉树判空
初始条件：	二叉树T已存在
操作结果：	若T为空，则返回true；否则返回false
函数参数：
		BinTree T	二叉树T
返回值：
		bool		二叉树是否为空
------------------------------------------------------------*/
bool BinTreeEmpty(BinTree T)
{
	if (T)
	{
		return false;
	}
	return true;
}

/*------------------------------------------------------------
操作目的：	二叉树求深度
初始条件：	二叉树T已存在
操作结果：	返回二叉树T的深度
函数参数：
		BinTree T	二叉树T
返回值：
		int			二叉树的深度
------------------------------------------------------------*/
int BinTreeDepth(BinTree T)
{
    int l,r;
	if (T == NULL)
	{
		return 0;
	}
	if (T->l == NULL && T->r == NULL)
	{
		return 1;
	}

	l = BinTreeDepth(T->l) + 1;
	r = BinTreeDepth(T->r) + 1;
	return l>r ? l:r;
}

/*------------------------------------------------------------
操作目的：	得到二叉树的根结点
初始条件：	二叉树T已存在
操作结果：	返回二叉树T的根结点
函数参数：
		BinTree T	二叉树T
返回值：
		BinTNode*	二叉树的根结点指针
------------------------------------------------------------*/
BinTNode *Root(BinTree T)
{

	assert(T != NULL);
	return T;
}

/*------------------------------------------------------------
操作目的：	判断结点n是否为树T的合法结点
初始条件：	二叉树T已存在
操作结果：	n为T的结点返回true，否则返回false
函数参数：
		BinTree T	二叉树T
		BinTNode* n	二叉树的结点n
返回值：
		bool		结点n是否存在与二叉树T中
------------------------------------------------------------*/
bool NodeExist(BinTree T, BinTNode* n)
{
	assert(T != NULL);
	assert(n != NULL);
	if (T == n)
	{
		return true;
	}
	else if (NodeExist(T->l,n))
	{
		return true;
	}
	else if (NodeExist(T->r,n))
	{
		return true;
	}
	else
	{
        return false;
	}

}

/*------------------------------------------------------------
操作目的：	得到二叉树指定结点的值
初始条件：	二叉树T已存在，n是二叉树T中的结点
操作结果：	返回结点n的值
函数参数：
		BinTree T	二叉树T
		BinTNode* n	二叉树结点n
返回值：
		ElemType	结点n的值
------------------------------------------------------------*/
ElemType Value(BinTree T, BinTNode* n)
{
	assert(n != NULL);

	if (NodeExist(T,n))
	{
		return n->data;
	}
}

/*------------------------------------------------------------
操作目的：	对二叉树的指定结点赋值
初始条件：	二叉树T已存在，n是二叉树T中的结点
操作结果：	操作成功返回true，操作失败返回false
函数参数：
		BinTree T	二叉树T
		BinTNode* n	二叉树结点n
		ElemType e	结点值
返回值：
		无
------------------------------------------------------------*/
void Assign(BinTree T, BinTNode* n, ElemType e)
{
	assert(T !=NULL);
	assert(n != NULL);
	if (NodeExist(T,n))
	{
		T->data = e;

	}


}

/*------------------------------------------------------------
操作目的：	得到二叉树指定结点的父结点
初始条件：	二叉树T已存在，n是二叉树T中的结点
操作结果：	如果二叉树结点n有父结点则返回父结点指针，否则返回NULL
函数参数：
		BinTree T	二叉树T
		BinTNode* n	二叉树结点n
返回值：
		BinTNode*	父结点指针
------------------------------------------------------------*/
BinTNode* Parent(BinTree T, BinTNode* n)
{
	assert(n!=NULL);
    //空、
    if (T==NULL)
    {
		return NULL;
    }
	if (T->l == NULL && T->r == NULL)
	{
		return NULL;
	}
	if(T->l == n || T->r == n)
	{
        return T;
	}
    //3.有左右
	BinTree tmp;
    if (tmp == Parent(T->l,n)!=NULL)
    {
		return tmp;
    }
	if (tmp == Parent(T->r,n)!=NULL)
	{
		return tmp;
	}

}

/*------------------------------------------------------------
操作目的：	得到二叉树指定结点的左孩子
初始条件：	二叉树T已存在，n是二叉树T中的结点
操作结果：	如果二叉树结点n有左孩子则返回左孩子结点指针，否则返回NULL
函数参数：
		BinTree T	二叉树T
		BinTNode* n	二叉树结点n
返回值：
		BinTNode*	左孩子结点指针
------------------------------------------------------------*/
BinTNode* LeftChild(BinTree T, BinTNode* n)
{
	assert(T != NULL);
	assert(n != NULL);

    if (LeftChild(T->l,n))
    {
		return T->l;
    }
	return NULL;
}

/*------------------------------------------------------------
操作目的：	得到二叉树指定结点的右孩子
初始条件：	二叉树T已存在，n是二叉树T中的结点
操作结果：	如果二叉树结点n有右孩子则返回右孩子结点指针，否则返回NULL
函数参数：
		BinTree T	二叉树T
		BinTNode* n	二叉树结点n
返回值：
		BinTNode*	右孩子结点指针
------------------------------------------------------------*/
BinTNode* RightChild(BinTree T, BinTNode* n)
{
	assert(T != NULL);
	assert(n != NULL);

	if (RightChild(T->r,n))
	{
		return T->r;
	}
	return NULL;
}

/*------------------------------------------------------------
操作目的：	得到二叉树指定结点的左兄弟
初始条件：	二叉树T已存在，n是二叉树T中的结点
操作结果：	如果二叉树结点n有左兄弟则返回左兄弟结点指针，否则返回NULL
函数参数：
		BinTree T	二叉树T
		BinTNode* n	二叉树结点n
返回值：
		BinTNode*	左兄弟结点指针
------------------------------------------------------------*/
BinTNode* LeftSibling(BinTree T, BinTNode* n)
{
	BinTree tmp;
	tmp = Parent(T,n);
	if (tmp->l)
	{
		return tmp->l;
	}
	return NULL;
}

/*------------------------------------------------------------
操作目的：	得到二叉树指定结点的右兄弟
初始条件：	二叉树T已存在，n是二叉树T中的结点
操作结果：	如果二叉树结点n有右兄弟则返回右兄弟结点指针，否则返回NULL
函数参数：
		BinTree T	二叉树T
		BinTNode* n	二叉树结点n
返回值：
		BinTNode*	右兄弟结点指针
------------------------------------------------------------*/
BinTNode* RightSibling(BinTree T, BinTNode* n)
{
	BinTree tmp;
	tmp = Parent(T,n);
	if (tmp->r)
	{
		return tmp->r;
	}
	return NULL;
}

/*------------------------------------------------------------
操作目的：	在二叉树中插入结点
初始条件：	二叉树T已存在，p是二叉树T中的结点，n为待插入的结点
操作结果：	在二叉树的p结点之前插入结点n
函数参数：
		BinTree T	二叉树T
		BinTNode* p	二叉树结点p
		LR d		二叉树结点p成为新结点n的左孩子或者右孩子
		BinTNode* p	待插入结点n
返回值：
		无
------------------------------------------------------------*/
void InsertNode(BinTree T, BinTNode* p, LR d, BinTNode* n)
{
	assert(n != NULL);
	//2.找p的位置，找p的父节点
	BinTree tmp;
	tmp = Parent(T,p);
	if (tmp != NULL)
	{
		 if (tmp->l == p)
		 {
			 tmp->l = n;
			 n->l = p;
			 n->r = NULL;
		 }
		 if (tmp->r == p)
		 {
			 tmp->r = n;
			 n->r = p;
			 n->l = NULL;
		 }
	}


}

/*------------------------------------------------------------
操作目的：	在二叉树中删除结点
初始条件：	二叉树T已存在，p是二叉树T中的结点
操作结果：	删除二叉树的p结点
函数参数：
		BinTree T	二叉树T
		BinTNode* p	二叉树结点p
		LR d		结点p的左孩子或者右孩子来取代p
返回值：
		无
------------------------------------------------------------*/
void DeleteNode(BinTree T, BinTNode* p, LR d)
{
	assert(NodeExist(T,p));
	BinTree tmp;
	tmp = Parent(T,p);
	if (tmp != NULL)
	{
		if (tmp->l == p)
		{
			tmp->l = p->l;
			tmp->l = p->r;
			free(p);
			p = NULL;
		}
		if (tmp->r == p)
		{
			tmp->r = p->l;
			tmp->r = p->r;
			free(p);
			p = NULL;
		}

	}
}

/*------------------------------------------------------------
操作目的：	先序遍历二叉树
初始条件：	二叉树T已存在
操作结果：	先序的方式，对二叉树的每个结点调用(*fp)一次且仅一次
函数参数：
		BinTree T	二叉树T
		*fp			访问函数指针
返回值：
		无
------------------------------------------------------------*/
void PreOrderTraverse(BinTree T, void (*fp)(ElemType))
{
	assert(T != NULL);
	(*fp)(T->data);
	PreOrderTraverse(T->l,fp);
	PreOrderTraverse(T->r,fp);

}

/*------------------------------------------------------------
操作目的：	中序遍历二叉树
初始条件：	二叉树T已存在
操作结果：	中序的方式，对二叉树的每个结点调用(*fp)一次且仅一次
函数参数：
		BinTree T	二叉树T
		*fp			访问函数指针
返回值：
		无
------------------------------------------------------------*/
void InOrderTraverse(BinTree T, void (*fp)(ElemType))
{
	assert(T != NULL);
	InOrderTraverse(T->l,fp);
	(*fp)(T->data);
	InOrderTraverse(T->r,fp);
}

/*------------------------------------------------------------
操作目的：	后序遍历二叉树
初始条件：	二叉树T已存在
操作结果：	后序的方式，对二叉树的每个结点调用(*fp)一次且仅一次
函数参数：
		BinTree T	二叉树T
		*fp			访问函数指针
返回值：
		无
------------------------------------------------------------*/
void PostOrderTraverse(BinTree T, void (*fp)(ElemType))
{
	assert(T != NULL);
	PostOrderTraverse(T->l,fp);
	PostOrderTraverse(T->r,fp);
	(*fp)(T->data);
}

/*------------------------------------------------------------
操作目的：	层序遍历二叉树
初始条件：	二叉树T已存在
操作结果：	层序的方式，对二叉树的每个结点调用(*fp)一次且仅一次
函数参数：
		BinTree T	二叉树T
		*fp			访问函数指针
返回值：
		无
------------------------------------------------------------*/
void LevelOrderTraverse(BinTree T, void (*fp)(ElemType))
{
		BinTree q[100];
		int front = 0;
		int rear =1;
		q[0]=T;
		while(front<rear)
		{
			if (q[front])
			{
				fp(q[front]->data);
				q[rear++] = q[front]->l;
				q[rear++] = q[front]->r;
				front++;
			}
			else
			{
				front++;
			}
		}
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2014-11-24，如有侵权请联系 cloudcommunity@tencent.com 删除

c++

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

c++

登录后参与评论

0 条评论

热度

二叉树的动态链式存储实现—C语言

二叉树的动态链式存储实现—C语言

头文件

ElemType.h

DynaLnkBiTree.h

主函数

Lab.cpp

实现函数

ElemType.cpp

DynaLnkBiTree.cpp

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐