#include <stdio.h>
#include <stdlib.h>
#define Maxsize 100
typedef char ElemType;
//二叉树的链式存储结构
typedef struct BitNode
{
ElemType data;
struct BitNode *lchild,*rchild;
}BitNode,*BitTree;
//二叉树的NLR递归创建
void Create_BitTree(BitTree &tree)
{
char ch;
if ((ch=getchar())=='#')
tree=NULL;
else
{
tree=(BitNode*)malloc(sizeof(BitNode));
tree->data=ch;
Create_BitTree(tree->lchild);
Create_BitTree(tree->rchild);
}
}
/*
* 二叉树的遍历部分
*/
//二叉树的先序递归遍历 NLR
void PreOrder(BitTree tree)
{
if (tree==NULL)
return; //什么也不做
else
{
printf("%c ",tree->data); //先输出根节点
PreOrder(tree->lchild); //在输出左子树
PreOrder(tree->rchild); //在输出右子树
}
}
//二叉树的中序递归遍历 NLR
void InOrder(BitTree tree)
{
if (tree==NULL)
return;
else
{
InOrder(tree->lchild); //先输出左子树
printf("%c ",tree->data); //在输出根节点
InOrder(tree->rchild); //最后输出右子树
}
}
//二叉树的后序递归遍历 LRN
void LastOrder(BitTree tree)
{
if (tree==NULL)
return;
else
{
LastOrder(tree->lchild);
LastOrder(tree->rchild);
printf("%c ",tree->data);
}
}
//二叉树的先序非递归遍历 NLR--- 栈 (用一维数组模拟)
void PreOrder1(BitTree tree)
{
BitTree Stack[Maxsize]; //创建大小为100的顺序栈
int top=-1; //栈顶指针
while (tree!=NULL || top!=-1) //二叉树非空或栈非空循环
{
if (tree)
{
printf("%c ",tree->data); //输出根节点
Stack[++top]=tree; //入栈
tree=tree->lchild; //访问左子树
}
else
{
tree=Stack[top--]; //出栈操作
tree=tree->rchild; //访问右子树
}
}
}
//二叉树的中序非递归遍历 LNR -- 栈
void InOrder1(BitTree tree)
{
BitTree Stack[Maxsize]; //顺序栈
int top=-1; //栈顶指针,初始为-1,同时,top==-1表示空栈
while (tree!=NULL || top!=-1) //二叉树非空,或者栈非空时循环
{
if (tree) //结点存在
{
Stack[++top]=tree; //入栈操作
tree=tree->lchild; //访问左子树
}
else //结点不存在
{
tree=Stack[top--]; //出栈操作
printf("%c ",tree->data); //输出左子树结点
tree=tree->rchild; //访问右子树
}
}
}
//二叉树的层次遍历 --队列
void CengOrder(BitTree tree)
{
BitTree Qunue[Maxsize];
int rear,front;
rear=front=-1;
Qunue[++rear]=tree;
while (rear>front) //队列不空
{
tree=Qunue[++front];
printf("%c ",tree->data);
if (tree->lchild)
Qunue[++rear]=tree->lchild;
if (tree->rchild)
Qunue[++rear]=tree->rchild;
}
}
//二叉树的深度 -- 队列非递归
void Level_Depth(BitTree tree)
{
int rear,front,last,level;
BitTree Qunue[Maxsize];
rear=front=-1;
level=0;
Qunue[++rear]=tree; //入队列
last=rear;
while (rear>front)
{
tree=Qunue[++front]; //出队列
if (tree->lchild)
Qunue[++rear]=tree->lchild;
if (tree->rchild)
Qunue[++rear]=tree->rchild;
if (front==last)
{
level++;
last=rear;
}
}
printf("二叉树高度是:%d
",level);
}
//二叉树的递归求深度 递归具有自我增长性,调用一次返回值+1 (前提是不修改返回值)
int Depth(BitTree tree)
{
int left;
int right;
if (tree==NULL)
return 0;
else
{
left=Depth(tree->lchild);
right=Depth(tree->rchild);
}
return left>right?(left+1):(right+1);
}
//求二叉树中某结点的指针地址
BitTree Address(BitTree tree,ElemType value)
{
BitTree p;
if (tree==NULL)
return NULL;
else if (tree->data==value)
return tree;
else
{
p=Address(tree->lchild,value);
if (p!=NULL)
return p;
else
return Address(tree->rchild,value);
}
}
//递归复制一棵二叉树
BitTree Copy(BitTree tree,BitTree &tree1)
{
if (tree==NULL)
tree1=NULL;
else
{
tree1=(BitTree)malloc(sizeof(BitNode));
tree1->data=tree->data; //先复制根节点
Copy(tree->lchild,tree1->lchild); //先复制左子树
Copy(tree->rchild,tree1->rchild); //在复制右子树
}
}
//递归交换二叉树的左右子树 NLR --不修改自身结构(tree1,是自身的一个副本)
void Swap_l_r(BitTree tree,BitTree &tree1)
{
if (tree==NULL)
tree1=NULL;
else
{
tree1->data=tree->data; //先交换根节点
Swap_l_r(tree->lchild,tree1->rchild); //在交换左子树
Swap_l_r(tree->rchild,tree1->lchild); //在交换右子树
}
}
//递归求出二叉树的所有叶子节点
void Leaves(BitTree tree)
{
if (tree==NULL)
return;
else
{
if (tree->lchild==NULL && tree->rchild==NULL) //先判断根节点是不是叶子节点
printf("%c ",tree->data);
Leaves(tree->lchild); //判断左子树是不是叶子节点
Leaves(tree->rchild); //判断右子树有没有叶子节点
}
}
//递归销毁二叉树 LRN
void DestoryBitTree(BitTree &tree)
{
if (tree==NULL)
return;
else
{
DestoryBitTree(tree->lchild); //销毁左子树
DestoryBitTree(tree->rchild); //销毁右子树
free(tree); //销毁根节点
}
}
int main()
{
BitTree tree,tree1;
Create_BitTree(tree);
LastOrder(tree);
Copy(tree,tree1);
putchar('
');
Swap_l_r(tree,tree1);
LastOrder(tree1);
printf("叶子节点为:");
Leaves(tree);
DestoryBitTree(tree);
DestoryBitTree(tree1);
return 0;
}