二叉排序树(添加结点)

  • 时间:
  • 来源:互联网
  • 文章标签:

二叉排序树

描述

添加的结点的值小于父节点的值,放在父节点的左边,反之放在父节点的右边。
a.如果父节点无子结点,将子结点的值与父节点的值进行比较后放到相应的位置。
b.如果父节点有子结点,则将父节点的子结点看成父节点继续执行添加操作。

创建二叉树排序树

要创建二叉树必然要创建结点,创建的第一个结点为根结点。

属性

root

方法

add(Node node)//添加结点
infixOrder()//中序遍历

注:这里的add()和infixOrder()方法是针对二叉排序树的根结点,详细见代码

UML图描述

UML图

代码

class BinarySortTree{
	private Node root;
	
	public void add(Node node) {
		if(root == null) {   //如果没有root结点,则将node结点赋给root
			root = node;    
		}
		else {               //如果有root结点,则添加node
			root.add(node);  
		}
	}

	public void infixOrder() {
		if(root != null) {
			root.infixOrder();
		}
		else {
			System.out.println("该二叉排序树为空");
		}
	}
}

创建结点

属性

value
left
right

方法

add(Node) //添加结点
infixOrder() //中序遍历

注:这类的add()和infixOrder()方法是针对二叉排序树的结点。

UML图描述在这里插入图片描述

class Node{
	private int value;
	private Node left;
	private Node right;
	
	public Node(int value) {
		this.value =value;
	}
	
	//添加结点的方法
	//递归的形式添加结点,注意需要满二叉排序树的要求
	public void add(Node node) {
		if(node == null) {
			return;
		}
		
		//判断传入的结点的值,和当前子树的根结点的值的关系型
		if(node.value < this.value) {
			//如果当前结点左子结点为null
			if(this.left == null) {
				this.left = node;
			}
			else {
				//递归的向左子树添加
				this.left.add(node);
			}
		}
		else {//添加的结点的值大于当前结点的值
			if(this.right == null) {
				this.right = node;
			}
			else {
				//递归的向右子数添加
				this.right.add(node);
			}
		}
	}
	
	public void infixOrder() {
		if(this.left != null) {
			this.left.infixOrder();
		}
		System.out.println(this.value);
		if(this.right != null) {
			this.right.infixOrder();
		}
	}
	
}

最终代码

输出用中序遍历

public class BinarySortTreeDemo {

	public static void main(String[] args) {
		
		int[] arr = new int[] {4,6,8,2,3,5,0};
		
		BinarySortTree binaryTree = new BinarySortTree();
		for(int i = 0;i < arr.length;i++) {
			binaryTree.add(new Node(arr[i]));        //自动装箱
		}
		
		System.out.println("中序遍历后");
		binaryTree.infixOrder();
		
	}
}

class BinarySortTree{
	private Node root;
	
	public void add(Node node) {
		if(root == null) {   //如果没有root结点,则将node结点赋给root
			root = node;    
		}
		else {               //如果有root结点,则添加node
			root.add(node);  
		}
	}

	public void infixOrder() {
		if(root != null) {
			root.infixOrder();
		}
		else {
			System.out.println("该二叉排序树为空");
		}
	}
}

class Node{
	private int value;
	private Node left;
	private Node right;
	
	public Node(int value) {
		this.value =value;
	}
	
	public void add(Node node) {
		if(node == null) {       //如果要添加的结点为空,则返回空
			return;
		}
		else {
			if(node.value < this.value) {
				if(this.left == null) {
					this.left = node;
				}
				else {
					this.left.add(node);
				}
			}
			else {
				if(this.right == null) {
					this.right = node;
				}
				else {
					this.right.add(node);
				}
			}
		}
	}
	
	public void infixOrder() {
		if(this.left != null) {
			this.left.infixOrder();
		}
		System.out.println(this.value);
		if(this.right != null) {
			this.right.infixOrder();
		}
	}
	
}

测试结果

在这里插入图片描述

本文链接http://www.taodudu.cc/news/show-83100.html