严蔚敏《数据结构》——二叉树_二叉树严

        几乎还原了严奶奶版数据结构中的代码

        二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个结点最多只能有两棵子树，且有左右之分。

        二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点

二叉树的遍历：

1.先序遍历： 遍历顺序：ABDECF，遍历规则：先访问根节点，然后遍历左子树，最后遍历右子树。

2.中序遍历：遍历顺序：DBEAFC，遍历规则：先遍历左子树，然后访问根节点，最后遍历右子树。

3.后序遍历：遍历顺序：DEBFCA，遍历规则：先遍历左子树，再遍历右子树，最后访问根节点。

所需要的的存储空间，由于树的遍历有递归和非递归两大类，非递归遍历需要栈的内容，所以存储结构中有栈的存储结构。

#include<cstdio>
#include<cstdlib>
 
#define OK 1;
#define ERROR 0; //为和教材内容贴合，OK的值设为1，ERROR的值设为0
#define Status int
#define TElemType int
#define MAX_TREE_SIZE 100//二叉树最大节点数
#define MAXSIZE 1000	//链表的最大长度 
#define SElemType int 
#define STACK_INIT_SIZE 100//定义栈的最大节点数
#define STACKINCREMENT 10 //存储空间分配增量
using namespace std;
typedef TElemType SqBiTree[MAX_TREE_SIZE];
SqBiTree bt;
 
typedef struct BiTNode {
	TElemType data;		//数据域
	struct BiTNode* lchild, * rchild;//指针域（左右孩子指针）
}BiTNode, *BiTree;
/*------所需要的的栈的存储空间------*/
typedef struct {
	SElemType* base;//栈底指针
	SElemType* top;//栈顶指针
	int stacksize;//栈的长度
}SqStack;

所需要的栈的函数

/*------所需要的的栈的函数------*/
栈的初始化
Status InitStack(SqStack& S) {
	S.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));//分配存储空间
	if (!S.base) printf("存储分配失败！"); exit(OVERFLOW);
	S.top = S.base;//栈顶=栈底
	S.stacksize = STACK_INIT_SIZE;
	printf("栈初始化成功！");
	return OK;
}
//入栈
Status Push(SqStack& S, SElemType e) {
	if (S.top - S.base > S.stacksize) {//判断栈的大小是否够用，不够用的话重新分配存储空间
		S.base = (SElemType*)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType));
	}
	if (!S.base) printf("存储分配失败！"); exit(OVERFLOW);
	S.top = S.base + S.stacksize;
	S.stacksize += STACKINCREMENT;
	return OK;
}
//出栈
Status Pop(SqStack& S,SElemType &e) {
	if (S.top = S.base) printf("这是一个空栈！"); return 0;
	e = *--S.top;
	printf("出栈成功！");
	return OK;
}
//判断栈空
bool StackEmpty(SqStack S) {
	if (S.top=S.base) {
		printf("栈空\n");
		return true;
	}
	else {
		printf("栈非空\n");
		return false;
	}
}
//获取栈顶元素
Status GetTop(SqStack S, SElemType e) {
	//判断栈空 
	if (StackEmpty(S)) {
		return 0;
	}
	else {
		e = *(S.top - 1);
		printf("栈顶元素为%d\n", e);
		return 0;
	}
	return OK;
}
/*--------------------------------------------------------*/

输出树的当前节点

void visit(BiTree &T) {
	printf("%d", T->data);//输出树的当前节点
}

二叉树的初始化

//二叉树初始化
void InitBiTree(BiTree &T) {
	T->lchild = NULL;
	T->rchild = NULL;
}

创建二叉树

//创建二叉树
Status CreateBiTree(BiTree &T) {
	int ch;
	scanf_s("%d", & ch);
	if (ch == ' ') {//出入空格表示当前结束
		T = NULL;
	}
	else {
		if (!(T = (BiTNode * )malloc(sizeof(BiTNode)))) exit(OVERFLOW);
		T->data = ch;
		CreateBiTree(T->lchild);
		CreateBiTree(T->rchild);
	}
	return OK;
}

先序遍历

//先序遍历
Status PreOrderTraverse(BiTree T) {
	if (T) {
		if (T->data) {
			visit(T);
			PreOrderTraverse(T->lchild);
			PreOrderTraverse(T->rchild);
		}
		return ERROR;
	}
	else return ERROR;
	return OK;
}

中序遍历

// 中序遍历
Status InOrderTraverse(BiTree T) {
	if (T) {
		if (T->data) {
			InOrderTraverse(T->lchild);
			visit(T);
			InOrderTraverse(T->lchild);
		}
	}
}

后序遍历

// 后序遍历
Status PostOrderTraverse(BiTree T) {
	if (T) {
		if (T->data) {
			PostOrderTraverse(T->lchild);
			PostOrderTraverse(T->rchild);
			visit(T);
		}
	}
}

书中的一种先序遍历方法以及两种中序遍历方法 非递归法（有错误，正在调试中...）

/*------书中的一种先序遍历方法以及两种中序遍历方法------*/
//先序遍历
Status preOrderTraverse(BiTree T, Status(*Visit)(TElemType e)) {
 
}
// 中序遍历1
Status inOrderTraverse_1(BiTree T, Status(*Visit)(TElemType e)){
	SqStack S;//定义S为SqStack类型的值
	BiTNode p;
	InitStack(S); Push(S, T->data);//初始化栈，并且将T节点入栈
	while (!StackEmpty(S)) {
		while (GetTop(S, T->data) && T) {//取栈顶元素
			Push(S, p->lchild);
		}
		Pop(S, T->data);
		if (!StackEmpty(S)) {
			Pop(S, T->data);
			if (!Visit(T->data)) return 0;
			Push(S, T->lchild);
		}
	}
	return 1;
}
// 中序遍历2
Status inOrderTraverse_2(BiTree T, Status(*Visit)(TElemType e)) {
	SqStack S;
	InitStack(S);
	BiTree p = T;
	while (p || !StackEmpty(S)) {
		if (p) {
			Push(S, p->data);
			p = p->lchild;
		}
		else {
			Pop(S, p->data); if (!Visit(p->data)) return 0;
			p = p->rchild;
		}
	}
	return 1;
}

清空二叉树

Status ClearBiTree(BiTree& T) {
	PreOrderTraverse(T);
	T->lchild = NULL;
	T->rchild = NULL;
}

销毁二叉树

Status DestroyBiTree(BiTree &T) {
	if (T->data != NULL) {
		DestroyBiTree(T->lchild);
		DestroyBiTree(T->lchild);
		delete T;
	}
	else {
		printf("这本来就是一颗空树！");
	}
	return 1;
}

判空

bool BiTreeEmpty(BiTree &T) {
	if (T->data == NULL) {
		printf("这是一个空的二叉树！");
		return true;
	}
	else {
		printf("这不是一个空的二叉树！");
		return false;
	}
}

查询二叉树的深度

Status BiTreeDepth(BiTree T) {
	int leftDepth, rightDepth, maxDepth;
	if (T != NULL) {
		leftDepth = BiTreeDepth(T->lchild);
		rightDepth = BiTreeDepth(T->rchild);
		maxDepth = leftDepth > rightDepth ? leftDepth : rightDepth;
		printf("该二叉树的深度为：%d", maxDepth + 1);
		return maxDepth + 1;
	}
}

返回二叉树的根节点

//返回该树的根
Status Root(BiTree& T) {
	int root = T->data;
	if (!T || BiTreeEmpty(T)) {
		printf("该树不存在！");
		return ERROR;
	}
	else {
		int root = T->data;
		printf("该树的根为：%d", root);
	}
	return root;
}

返回节点的父节点

//返回节点的双亲
BiTree Parent(BiTree T, BiTree ch) {
	int parent, c;
	parent = T->data;
	printf("请输入所需查找双亲的元素：");
	scanf_s("%d", &ch);
	if (T->data == NULL || T->rchild == ch || T->lchild == ch) return ch;
	BiTree left = Parent(T->lchild, ch);
	if (left != NULL) return left;
	BiTree right = Parent(T->lchild, ch);
	if (right != NULL) return right;
	return left;
}

返回节点的左右孩子

//该节点的左孩子
Status LeftChild(BiTree T) {
	int ch;
	int leftchild;
	scanf_s("%d", &ch);
	if (PreOrderTraverse(T) == ch) {
		leftchild = T->data;
	}
	printf("结点%d的双亲是%d",leftchild);
}
//该节点的右孩子
Status RightChild(BiTree T) {
	int ch;
	int leftchild;
	scanf_s("%d", &ch);
	if (PreOrderTraverse(T) == ch) {
		leftchild = T->data;
	}
	printf("结点%d的双亲是%d", leftchild);
}

排除该节点的左右子树

//删除该节点的左子树或右子树
Status DeleteChild(BiTree T) {
	int ch;
	scanf_s("%d", &ch);
	if (PreOrderTraverse(T) == ch) {
		DestroyBiTree(T);
	}
	printf("结点%d的左右子树销毁成功！", ch);
	return OK;
}

还差插入元素和访问该节点的左右兄弟...

 main交给各位写了，我实现了没有问题的，有问题的请联系我。

学艺不精，若有错误还请多多指教，谢谢。

p.s.在使用Visual Studio编译器的时候输入scanf()方法要用scanf_s()

更多内容请移步公众号 手撕算法。谢谢

所使用编译器为：Visual Studio2019 链接：https://pan.baidu.com/s/1eg8CNrqrP1jn7GRzHfYXxA
                                                                    提取码：1234

推荐新手使用dev cpp                        链接：https://pan.baidu.com/s       /1XZp_8lVE7X6tMLmvXRbYhw
                                                                     提取码：1234