Java——二叉树的基本构造以及函数
·
Java源代码：
public class BinaryTreeNode {
private int data;
private BinaryTreeNode left;
private BinaryTreeNode right;
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public BinaryTreeNode getLeft() {
return left;
}
public void setLeft(BinaryTreeNode left) {
this.left = left;
}
public BinaryTreeNode getRight(){
return right;
}
public void setRight(BinaryTreeNode right){
this.right = right;
}
}
public class BinarySearchTreeNode {
private int data;
private BinarySearchTreeNode left;
private BinarySearchTreeNode right;
public int getData(){
return data;
}
public void setData(int data){
this.data =data;
}
public BinarySearchTreeNode getLeft(){
return left;
}
public void setLeft(BinarySearchTreeNode left){
this.left = left;
}
public BinarySearchTreeNode getRight(){
return right;
}
public void setRight(BinarySearchTreeNode right){
this.right = right;
}
BinarySearchTreeNode FindMax(BinarySearchTreeNode root){
if(root == null){
return null;
}
else{
if(root.getRight()==null){
return root;
}
else{
return FindMax(root.getRight());
}
}
}
BinarySearchTreeNode Delete(BinarySearchTreeNode root, int data){
BinarySearchTreeNode temp;
if(root == null){
System.out.println("Element not there in tree");
}
else if(data < root.data){
root.left = Delete(root.getLeft(),data);
}
else if(data > root.data){
root.right = Delete(root.getRight(),data);
}
else{
if(root.getLeft()!=null&&root.getRight()!=null){
temp = FindMax(root.getLeft());
root.data=temp.data;
root.left =Delete(root.getLeft(), root.getData());
}
else{
temp = root;
if(root.getLeft()==null){
root = root.getRight();
}
if(root.getRight()==null){
root=root.getLeft();
}
}
}
return root;
}
常用功能单独拿出来：
public class Find {
BinarySearchTreeNode Find(BinarySearchTreeNode root, int data){
if(root == null){
return null;
}
if(data < root.getData()){
return Find(root.getLeft(),data);
}
else if(data > root.getData()){
return Find(root.getRight(), data);
}
return root;
}
}
public class Find2 {
BinarySearchTreeNode Find2(BinarySearchTreeNode root, int data){
if(root == null){
return null;
}
while(root!=null){
if(data == root.getData()){
return root;
}
else if(data > root.getData()){
root = root.getRight();
}
else{
root = root.getLeft();
}
}
return null;
}
}
递归虽然常写，但性能还是非递归更好——考虑的情况更细，更省
public class FindMax {
BinarySearchTreeNode FindMax(BinarySearchTreeNode root){
if(root == null){
return null;
}
else{
if(root.getRight()==null){
return root;
}
else{
return FindMax(root.getRight());
}
}
}
}
public class FindMax2 {
BinarySearchTreeNode FindMax2(BinarySearchTreeNode root){
if(root == null){
return null;
}
while(root.getRight()!=null){
root =root.getRight();
}
return root;
}
}
public class FindMin {
BinarySearchTreeNode FindMin(BinarySearchTreeNode root){
if(root == null){
return null;
}
else{
if(root.getLeft() == null){
return root;
}
else{
return FindMin(root.getLeft());
}
}
}
}
public class FindMin2 {
BinarySearchTreeNode FindMin2(BinarySearchTreeNode root){
if(root == null){
return null;
}
while(root.getLeft()!=null){
root = root.getLeft();
}
return root;
}
}
public class Insert {
BinarySearchTreeNode Insert(BinarySearchTreeNode root, int data){
if( root == null){
root = new BinarySearchTreeNode();
if(root == null){
System.out.println("Memory Error!");
return null;
}
else{
root.setData(data);
root.setLeft(null);
root.setRight(null);
}
}
else{
if(data < root.getData()){
root.setLeft(Insert(root.getLeft(),data));
}
else if(data > root.getData()){
root.setRight(Insert(root.getRight(),data));
}
}
return root;
}
}
线索二叉树
public class ThreadedBinaryTreeNode {
public ThreadedBinaryTreeNode left;
public int LTag;
public int data;
public int RTag;
public ThreadedBinaryTreeNode right;
public ThreadedBinaryTreeNode getLeft() {
return left;
}
public void setLeft(ThreadedBinaryTreeNode left) {
this.left = left;
}
public int getLTag() {
return LTag;
}
public void setLTag(int LTag) {
this.LTag = LTag;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public int getRTag() {
return RTag;
}
public void setRTag(int RTag) {
this.RTag = RTag;
}
public ThreadedBinaryTreeNode getRight() {
return right;
}
public void setRight(ThreadedBinaryTreeNode right) {
this.right = right;
}
ThreadedBinaryTreeNode InorderSuccessor(ThreadedBinaryTreeNode P){
ThreadedBinaryTreeNode Position;
if(P.RTag ==0){
return P.getRight();
}else{
Position = P.getRight();
while(Position.getLTag() == 1){
Position = Position.getLeft();
}
return Position;
}
}
void InorderTraversal(ThreadedBinaryTreeNode root){
ThreadedBinaryTreeNode P = InorderSuccessor(root);
while(P!=root){
P = InorderSuccessor(P);
System.out.println(P.getData());
}
}
ThreadedBinaryTreeNode PreorderSuccessor(ThreadedBinaryTreeNode P){
ThreadedBinaryTreeNode Position;
if(P.getLTag() == 1){
return P.getLeft();
}else{
Position = P;
while(Position.getRTag() == 0){
Position = Position.getRight();
}
return Position.getRight();
}
}
void PreorderTraversal1(ThreadedBinaryTreeNode root){
ThreadedBinaryTreeNode P;
P = PreorderSuccessor(root);
while(P!=root){
P = PreorderSuccessor(P);
System.out.println(P.getData());
}
}
void PreorderTraversal2(ThreadedBinaryTreeNode root){
ThreadedBinaryTreeNode P = root;
while(true){
P = PreorderSuccessor(P);
if(P == root){
return;
}
System.out.println(P.getData());
}
}
void InsertRightInInorderTBT(ThreadedBinaryTreeNode P,ThreadedBinaryTreeNode Q){
ThreadedBinaryTreeNode Temp;
Q.setRight(P.getRight());
Q.setRTag(P.getRTag());
Q.setLeft(P);
Q.setRTag(1);
if(Q.getRTag()==1){
Temp = Q.getRight();
while(Temp.getLTag()!=0){
Temp =Temp.getLeft();
}
Temp.setLeft(Q);
}
}
}
更多推荐
0
0- 0
已为社区贡献1条内容
所有评论(0)