#include <stdio.h>
#include <stdlib.h>
typedef struct Treenode* Bintree;
typedef Bintree Position;
struct Treenode
{
int date;
struct Treenode* left;
struct Treenode* right;
};
//二叉树的遍历
//1.先序遍历：遇到根节点先打印出来，然后去访问它的左节点，接着是右节点
//就是打印出根结点之后，先序遍历左子树，然后先序遍历右子树
void PreOrderTraveral(Bintree T)
{
if (T != NULL)
{
printf("%d", T->date);
PreOrderTraveral(T->left);
PreOrderTraveral(T->right);
}
}
//2.中序遍历：先访问树的左子树，然后打印根节点，在访问右子树
//就是说，先中序遍历树的左子树，然后打印根节点，再中序遍历右子树
void InOrderTraveral(Bintree T)
{
if (T != NULL)
{
InOrderTraveral(T->left);
printf("%d", T->date);
InOrderTraveral(T->right);
}
}
//3.后序遍历：先访问树的左子树，然后访问树的右子树，然后打印根节点
//就是说，先后序遍历左子树，然后后序遍历右子树，最后打印根节点
void PostOrderTraveral(Bintree T)
{
if (T != NULL)
{
PostOrderTraveral(T->left);
PostOrderTraveral(T->right);
printf("%d", T->date);
}
}
//以上都是递归的遍历算法
//接下来看看非递归实现
//非递归实现中序遍历（使用堆栈）
//遇到一个节点，将其压入堆栈，然后去遍历他的左子树
//当左子树遍历结束后，从栈顶弹出根节点并访问（打印）
//然后按照其右指针去遍历该节点的右子树
//层序遍历：1.根节点入队
// 2.访问该元素所指节点
// 3.若该元素所指节点的左右节点非空，则将其左右节点的指针顺序入队
//输出二叉树的叶子节点
//思路：只需要在二叉树的遍历算法中增加一个判断叶子结点的条件即可
int PerOrderTraveral(Bintree T)
{
if (T != NULL)
{
if (T->left == NULL && T->right == NULL)//判断是否为叶子节点
printf("%d", T->date);
PerOrderTraveral(T->left);
PerOrderTraveral(T->right);
}
}
//求二叉树的高度
//思路：采用递归算法，树的高度等于左子树和右子树高度的最大值+1
int PostOrderGetHight(Bintree T)
{
int HL, HR, MAXH;
if (T != NULL)
{
HL = PostOrderGetHight(T->left);
HR = PostOrderGetHight(T->right);
MAXH = (HL > HR) ? HL : HR;
return (MAXH + 1);
}
else
return 0;
}
//由两种任意序遍历得到的序列能否唯一确定一颗二叉树？
//答：中序和先序或者后序序列可以确定的，而后序和先序不行
//原因：中序遍历的第一段序列一定是根节点的，只需要在后面找相应的序列，然后就可以分清楚
//二叉搜索树：
//1.非空左子树的值一定小于其根节点
//2.非空右子树的值一定大于其根节点
//3.根节点的左右子树一定是二叉搜索树
//二叉搜索树的查找
//1.从根节点开始，若树为空，返回NULL;
//2.根据搜索树的特点，若x大于左子树，则往右边找，小于就往左边找，等于就找着了
Bintree Find(Bintree T, int x)
{
if (T == NULL)
{
printf("树为空");
return NULL;
}
else
{
if (T->date > x)
Find(T->left, x);
else if (T->date < x)
Find(T->right, x);
else
{
printf("找着了");
return T;
}
}
}
//非递归实现二叉搜索树的查找
Bintree Find(Bintree T, int x)
{
while (T)
{
if (T->date > x)
T = T->left;
else if (T->date < x)
T = T->right;
else
return T;
}
return NULL;
}
//查找二叉搜索树中的最大最小值问题
//二叉搜索树的最左边的节点里面就是最小值
//最右边的节点里面就是最大值
Bintree FindMax(Bintree T)
{
while (T)
{
T = T->right;
}
return T;
}
Bintree FindMin(Bintree T)
{
while (T)
{
T = T->left;
}
return T;
}
//二叉搜索树的插入
Bintree Insert(Bintree T, int x)
{
if (T == NULL)
{
Bintree BT = (Bintree)malloc(sizeof(struct Treenode));
if (BT == NULL)
{
printf("无法开辟空间");
return 0;
}
else
{
BT->left = NULL;
BT->right = NULL;
BT->date = x;
}
}
else
{
if (T->date > x)
Insert(T->left, x);
else
Insert(T->right, x);
}
return T;
}
//二叉搜索树的删除
//分为三种情况
//1.要删除的节点没有子节点
//2.要删除的节点有一个子节点
//3.要删除的节点有两个子节点
//第一种情况很好处理，指向它的节点的相应指针直接设置为NULL,并释放被删除的节点
//第二种情况也差不多，可以直接让指向它的节点的相应指针直接指向他的那一个子节点
//也就是说，让他的子节点代替他，并释放被删除的节点即可
//第三种情况比较复杂一点，待删除结点有两个子节点
//和第二种情况思路相似，找子节点来代替它即可
//可以在它的左子树上找最大值来代替，也可以在右子树上找最小值来代替
Bintree Delete(Bintree T, int x)
{
Bintree newT;
if (!T) printf("要删除的元素未找到");
else if (T->date > x)
T->left = Delete(T->left, x);
else if (T->date < x)
T->right = Delete(T->right, x);
else//(T->date = x)
{
if (T->left && T->right)//有两个节点
{
newT = FindMin(T->right);
T->date = newT->date;
T->right = Delete(T->right, T->date);
}
else
{
newT = T;
if (!T->left)
T = T->right;
else if (!T->right)
T = T->left;
free(newT);
}
}
return T;
}