java 实现二叉树结构基本运算详细代码
2024-09-04 12:41:48
static final int MAXLEN = 20; //最大长度 class CBTType //定义二叉树节点类型
{ String data; //元素数据
CBTType left; //左子树节点引用
CBTType right; //右子树节点引用
} CBTType InitTree() //初始化二叉树
{
CBTType node;
if((node=new CBTType())!=null){ //申请内存
System.out.println("请输入根节点数据");
node.data=input.next();
node.left=null;
node,right=null;
if(node!=null)
{
return node;
}
else
{
return null;
}
}
return null;
} void AddTreeNode(CBTType treeNode) //添加节点
{
CBTType pnode,parent;
String data;
int menusel; if((pnode=new CBTType())!=null)
{
System.out.println("输入二叉树结点数据");
pnode.data=input.next();
pnode.left=null;
pnode,right=null;
System.out.println("输入该节点父节点的数据");
data=input.next();
parent=TreeFindNode(treeNode,data);
if(parent==null)
{
System.out.prinln("未找到父节点");
return;
}
System.out.println("1.插入到父节点左子树 2.插入到父节点右子树");\
do
{
menusel=input.neitInt();
if(menusel==1||menusel==2)
{
if(parent==null)
{
System.out.prinln("父节点不存在，请先设置父节点");
}
else
{
switch(menusel)
{
case 1:
if(parent.left!=null)
{
System.out.prinln("左子树节点不为空");
}
else
{
parent.left=pnode;
}
break;
case 2:
if(parent.right!=null)
{
System.out.prinln("右子树节点不为空");
}
else
{
parent.right=pnode;
}
break;
default:
System.out.println("无效参数");
}
}
}while(menusel!=1&&menusel!=2); } } CBTType TreeFindNode(CBTType treeNode,String data) // 查找节点
{
CBTType ptr;
if(treeNode==null)
{
return null;
}
else
{
if(treeNode.data.equals(data))
{
return treeNode
}
else
{
if((ptr=TreeFindNode(treeNode.left,data))!==null) //递归左子树
{
return ptr;
}
else if((ptr=TreeFindNode(treeNode.right))!==null) // 递归右子树
{
return ptr;
}
else
{
return null;
}
}
}
} CBTType TreeLeftNode(CBTType treeNode) //获取左子树
{
if(treeNode!=null)
{
return treeNode.left;
}
else
{
return null;
}
} CBTType TreeRightNode(CBTType treeNode) //获取右子树
{
if(treeNode!=null)
{
return treeNode.right;
}
else
{
return null;
}
} int TreeIsEmpty(CBTType treeNode) //判断空树
{
if(treeNode==null)
{
return 1;
}
else
{
return 0;
}
} int TreeDepth(CBTType treeNode) //计算二叉树深度
{
int depleft,depright;
if(treeNode==null)
{
return 0;
}
else
{
depleft=TreeDepth(treeNode.left); //左子树深度递归
depright=TreeDepth(treeNode.right); //右子树深度递归
if(depleft>depright)
{
return depleft+1；
}
else
{
return depright+1;
}
}
} void ClearTree(CBTType treeNode) //清空二叉树
{
if(treeNode!=null)
{
ClearTree(treeNode.left);
ClearTree(treeNode.right);
treeNode=null;
}
} void TreeNodeData(CBTType p) //显示当前节点数据
{
System.out.prinln("%s",p.data);
} void LevelTree(CBTType treeNode) //层次遍历
{
CBTType p;
CBTType[] q=new CBTType[MAXLEN]; //定义队列
int head= 0;
int tail= 0;
if(treeNode!=null)
{
tail=(tail+1)%MAXLEN; //计算循环队列尾序号
q[tail]=treeNode; //将二叉树根引进队列
}
while(head!=tail) //队列不为空 进行循环
{
head=(head+1)%MAXLEN;
p=q[head];
TreeNodeData(p);
if(p.left!=null)
{
tail=(tail+1)%MAXLEN;
q[tail]=p.left;
}
if(p.right!=null)
{
tail=(tail+1)%MAXLEN;
q[tail]=p.left;
}
}
} void DLRTree(CBTType treeNode) //先序遍历
{
if(treeNode!=null)
{
TreeNodeData(treeNode); //显示节点数据
DLRTree(treeNode.left);
DLRTree(treeNode,right);
}
} void LDRTree(CBTType treeNode) //中序遍历
{
if(treeNode!=null)
{
LDRTree(treeNode.left);
TreeNodeData(treeNode);
LDRTree(treeNode,right);
}
} void LRDTree(CBTType treeNode) //后序遍历
{
if(treeNode!=null)
{
LRDTree(treeNode.left);
LRDTree(treeNode.right);
TreeNodeData(treeNode);
}
}
最新文章
- iOS 按钮上的标题设置向左向右对齐的方法
- 一次pthread_kill引发的HA切换
- Json-转换
- Could not find class XXX referenced from method XXX.<YYY>
- 第4章 awk编程
- poj 3216 Repairing Company(最短路Floyd + 最小路径覆盖 + 构图)
- Cocos3.0测试版发布（中文）
- 设计模式（十）：Decorator装饰者模式 -- 结构型模式
- JavaScript之ClassName属性学习
- Flex布局语法
- Base-64编码介绍
- spring cloud 入门系列三：使用Eureka 搭建高可用服务注册中心
- 【LeetCode每天一题】Set Matrix Zeroes(设置0矩阵)
- Java Map 集合实现类
- github 快速部署
- kafka 备忘
- Uncaught DOMException: Failed to construct 'WebSocket': The URL 'xxx.xxx.com/' is invalid.
- react源码探索
- css理论
- 图形数据库 Neo4j 开发实战