第五章编程任务与二叉树基本操作
基本内容
该代码包含树的基本操作和智慧树编程任务
1. 树的基本操作：
①空二叉树初始化
②.广义表创建二叉树
③.查找某节点
④找左右孩子节点
⑤.递归求树的高度
⑥.广义表形式输出二叉树
⑦.二叉树销毁
⑧.访问二叉树节点
⑨.递归前/中/后/层序遍历二叉树
2. 智慧树编程任务
非递归实现前中后序遍历
注意事项
注意事项
①.不要抄不要抄不要抄
②.写这的目的是为了方便学习，方便复习
③.自己手敲，不要一不会就找，实在实在没办法了可以参考下，也不要只看这个，多看看很多相关博文，收获会很大
④.b站懒猫老师的树讲的很好，有时间可以去看看，然后自己有时间把功能实现
⑤.暂时没空写具体的函数的步骤了，遇到不会的去推荐看b站懒猫老师视频(力推)
代码
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
typedef struct BTNode
{
struct BTNode *lchild;
struct BTNode *rchild;
char data;
}BTNode;
typedef struct elem
{
BTNode *ptr;
int flag;
}Elem;
//空二叉树初始化
void init(BTNode *&T)
{
T = NULL;
}
//广义表创建二叉树
void creatBiTree(BTNode *&T, char str[])
{
BTNode *st[MAXSIZE], *p = NULL;
int tag, top = -1;
T = NULL;
for(int i = 0; str[i]; i++)
{
char c = str[i];
switch(c)
{
case '(':
st[++top] = p;
tag = 1;//表明后面遇到的节点为左孩子
break;
case ')':
top--;
break;
case ',':
tag = 2;//表明后面遇到的孩子为右孩子
break;
default:
p = (BTNode *)malloc(sizeof(BTNode));
p -> data = c;
p -> lchild = p -> rchild = NULL;
if(T == NULL)
T = p;
else
{
switch(tag)
{
case 1:
st[top] -> lchild = p;
// printf("st[top] -> data = %c,st[top] -> lchild -> data = %c\n",st[top] -> data,st[top] -> lchild -> data);
break;
case 2:
st[top] -> rchild = p;
// printf("st[top] -> data = %c,st[top] -> rchild -> data = %c\n",st[top] -> data,st[top] -> rchild -> data);
break;
}
}
break;
}
}
}
//查找某节点
BTNode *FindNode(BTNode *T, char x)//递归返回值BTNode *
{
BTNode *p;
//递归终止条件
if(T == NULL) return NULL;//未找到终止条件
else if(T -> data == x) return T;//找到终止条件
else
{
//本级递归
p = FindNode(T -> lchild,x);//左子树查找
if(p != NULL) return p;
else return FindNode(T -> rchild,x);//右子树查找
}
}
//找左孩子节点
BTNode *LchildNode(BTNode *p)
{
return p -> lchild;
}
//找右孩子节点
BTNode *RchildNode(BTNode *p)
{
return p -> rchild;
}
//递归求树的高度，
int BiTreeDepth(BTNode *T)//递归返回值，本层高度
{
int ldepth,rdepth;
if(T == NULL) return 0; //递归终止条件：空树
else
{
ldepth = BiTreeDepth(T -> lchild);
rdepth = BiTreeDepth(T -> rchild);
return ldepth > rdepth ? (ldepth + 1) : (rdepth + 1);
}
}
//输出二叉树
void printBiTree(BTNode *T)
{
if(T == NULL) return;
else
{
printf("%c",T -> data);
if(T -> lchild || T -> rchild)
{
printf("(");
printBiTree(T -> lchild);
if(T -> rchild) printf(",");
printBiTree(T -> rchild);
printf(")");
}
}
}
//欠：横向输出二叉树
//销毁二叉树
void destroyBiTree(BTNode *T)
{
if(T == NULL) return;
else
{
destroyBiTree(T -> lchild);
destroyBiTree(T -> rchild);
free(T);
}
}
//访问二叉树节点
void visit(BTNode *p)
{
printf("%c",p -> data);
}
//前序遍历二叉树
void preOrderTraverse(BTNode *T)
{
if(T == NULL) return;
else
{
visit(T);
preOrderTraverse(T -> lchild);
preOrderTraverse(T -> rchild);
}
}
//中序遍历二叉树
void inOrderTraverse(BTNode *T)
{
if(T == NULL) return;
else
{
inOrderTraverse(T -> lchild);
visit(T);
inOrderTraverse(T -> rchild);
}
}
//后序遍历二叉树
void postOrderTraverse(BTNode *T)
{
if(T == NULL) return;
else
{
postOrderTraverse(T -> lchild);
postOrderTraverse(T -> rchild);
visit(T);
}
}
//层序遍历二叉树
void levelTraverse(BTNode *T)
{
BTNode *q[MAXSIZE];
int tt = 0, hh = 0;
q[tt++] = T;//入队
while(hh != tt)//判断队列是否为空
{
BTNode *p = q[hh++];//出队，并判断hh
if(hh == MAXSIZE) hh = 0;
printf("%c",p -> data);
if(p -> lchild)
{
if(tt == MAXSIZE) tt = 0;//判断tt，并入队
q[tt++] = p -> lchild;
}
if(p -> rchild)
{
if(tt == MAXSIZE) tt = 0;
q[tt++] = p -> rchild;
}
}
}
//前序遍历非递归算法
void preOrderTraverseNRE(BTNode *T)
{
BTNode *st[MAXSIZE];
BTNode *p = T;
int tt = 0;
while(p != NULL || tt > 0)
{
while(p != NULL)
{
printf("%c",p -> data);
st[++tt] = p;
p = p -> lchild;
}
if(tt > 0)
{
p = st[tt--];
p = p -> rchild;
}
}
}
//中序遍历非递归实现
void inOrderTraverseNRE(BTNode *T)
{
BTNode *st[MAXSIZE];
BTNode *p = T;
int tt = 0;
while(p != NULL || tt > 0)
{
while(p != NULL)
{
st[++tt] = p;
p = p -> lchild;
}
if(tt > 0)
{
p = st[tt--];
printf("%c",p->data);
p = p -> rchild;
}
}
}
//后序遍历非递归实现
void postOrderTraverseNRE(BTNode *T)
{
Elem st[MAXSIZE];
BTNode *p = T;
int tt = 0;
while(p != NULL || tt > 0)
{
//访问左子树，并入栈
while(p != NULL)
{
st[++tt].ptr = p;
st[tt].flag = 1;
p = p -> lchild;
}
//左子树访问结束，取栈顶元素，①访问右子树，②.访问栈顶节点值s
Elem elem = st[tt--];
p = elem.ptr;
if(elem.flag == 1)//说明只访问过左子树,取出栈顶节点，访问右子树
{
elem.flag = 2;
st[++tt] = elem;
p = p -> rchild;
}
else//已经访问过右子树，可以获取子树根节点的值
{
visit(p);
p = NULL;
}
}
}
int main()
{
BTNode *T;
char str[30] = "A(B(D,E(G,)),C(,F)";
init(T);
creatBiTree(T,str);
printf("=====高度测试=====\n");
int depth = BiTreeDepth(T);
printf("depth = %d\n",depth);
printf("=====查找节点测试=====\n");
BTNode *p = FindNode(T,'E');
// printf("%c -> lchild -> data = %c\n",p -> data,p -> lchild -> data);
// printf("%c -> rchild -> data = %c\n",p -> data,p -> rchild -> data);
printf("=====左孩子测试=====\n");
p = LchildNode(p);
if(p == NULL) printf("无左孩子\n");
else printf("左孩子为：%c\n",p -> data);
printf("=====右孩子测试=====\n");
p = LchildNode(p);
if(p == NULL) printf("无右孩子\n");
else printf("右孩子为：%c\n",p -> data);
printf("=====打印二叉树测试=====\n");
printBiTree(T);
printf("\n");
// printf("=====释放二叉树测试=====\n");
// destroyBiTree(T);
printf("\n\n\n");
printf("=====前序遍历二叉树测试=====\n");
preOrderTraverse(T);
printf("\n");
printf("=====中序遍历二叉树测试=====\n");
inOrderTraverse(T);
printf("\n");
printf("=====后序遍历二叉树测试=====\n");
postOrderTraverse(T);
printf("\n");
printf("=====层序遍历二叉树测试=====\n");
levelTraverse(T);
printf("\n\n\n");
printf("=====前序遍历(非递归)二叉树测试=====\n");
preOrderTraverseNRE(T);
printf("\n");
printf("=====中序遍历(非递归)二叉树测试=====\n");
inOrderTraverseNRE(T);
printf("\n");
printf("=====后序遍历(非递归)二叉树测试=====\n");
postOrderTraverseNRE(T);
printf("\n");
}