当前位置 博文首页 > xiexiexiexieqing的博客：二叉树的 高度 和 最值（非递归）
（非递归）高度和最值 用 出入栈就可以解决
先 准备
#include <stdio.h>
#include <stdlib.h>
//数据 结构体
struct DATA
{
int a;
char a1[20];
};
//节点 结构题
struct node
{
struct DATA data;
struct node*left;
struct node*right;
} ;
//搜索树 结构体
struct TREE{
struct node*root;
};
//创建节点
struct node*createnode(struct DATA data)
{
struct node*newnode=(struct node*)malloc(sizeof(struct node));
newnode->data=data;
newnode->left=NULL;
newnode->right=NULL;
return newnode;
}
//创建 搜索树
struct TREE*createtree()
{
struct TREE*tree=(struct TREE*)malloc(sizeof(struct TREE));
tree->root=NULL;
return tree;
}?
在操作
//高度 非递归
int h(struct node*root)
{
struct node*a[20];
struct node*pnode=root;
int i=-1;
int h=0; //初始化 高度
struct node*x=NULL; //标记
while(pnode)
{
a[++i]=pnode; //入栈
pnode=pnode->left;
}
while(i!=-1)
{
pnode=a[i--]; //出栈
if(pnode->right==NULL || pnode->right==x) //只要 节点 的右边为空 或者 被标记
{
//printf("%3d:%s",pnode->data.a,pnode->data.a1); 后续遍历--打印 当前节点的值
x=pnode; // 把 当前节点 标记
}
else
{
a[++i]=pnode; // 入栈
pnode=pnode->right;
while(pnode)
{
a[++i]=pnode; //重复 节点向左的动作
pnode=pnode->left;
}
if(i>h) // 当 节点的上一个循环（节点无路可走时 结构体数组的 下标为当前 最大）
h=i;
}
}
return h+1; //返回的是 h+1 因为 结构体数组的 下标是从0开始 而高度从1开始
}
// 最大值 非递归 （前/中 序）
int max(struct node*root)
{
struct node*a[20];
struct node*pnode=root;
int max=root->data.a; //先 假设 根节点 的数据为最大
int i=-1;
while(i!=-1 || pnode)
{
while(pnode)
{
if(pnode->data.a > max) // max和循环内的所有几点比较
max=pnode->data.a;
a[++i]=pnode; //入栈
pnode=pnode->left;
}
if(i!=-1)
{
pnode=a[i--]; //出栈
pnode=pnode->right;
}
}
return max;
} ?
cs