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

头文件

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++;
			}
		}
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Hongten

ArrayList VS Vector(ArrayList和Vector的区别)_面试的时候经常出现

1.4K20
来自专栏kevindroid

leetcode257 Binary Tree Paths

15950
来自专栏日常分享

Java 通过先序中序序列生成二叉树

  二叉树的前序以及后续序列,以空格间隔每个元素,重构二叉树,最后输出二叉树的三种遍历方式的序列以验证。

27410
来自专栏肖洒的博客

数据结构笔记(二)

栈是限定仅在表尾进行插入和删除操作的线性表。 队列是只允许在一段进行插入操作、而在另一端进行删除操作的线性表。

10030
来自专栏Bingo的深度学习杂货店

Q110 Balanced Binary Tree

Given a binary tree, determine if it is height-balanced. For this problem, a hei...

29550
来自专栏java闲聊

JDK1.8 ArrayList 源码解析

当运行 ArrayList<Integer> list = new ArrayList<>() ; ,因为它没有指定初始容量,所以它调用的是它的无参构造

15120
来自专栏撸码那些事

【图解数据结构】二叉查找树

13020
来自专栏C/C++基础

判断二叉树是否为平衡二叉树

解题思路: 根据二叉树的定义,我们可以递归遍历二叉树的每一个节点来,求出每个节点的左右子树的高度,如果每个节点的左右子树的高度相差不超过1,按照定义,它就是...

8720
来自专栏Android相关

平衡二叉树

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

62830
来自专栏章鱼的慢慢技术路

笔试常考题型之二叉树的遍历

20350

扫码关注云+社区

领取腾讯云代金券