精华内容
下载资源
问答
  • 使用java构建数据结构,实现二叉树的遍历

    经过对二叉树的简单学习之后,使用java进行简单些了二叉树的类

    简单实现一下功能:

    1. 通过可选属性进行构建二叉树(层序构建)
    2. 获取二叉树的深度(递归)
    3. 获取二叉树的节点数(递归)
    4. 前序遍历(递归)
    5. 前序遍历(非递归)
    6. 中序遍历(递归)
    7. 中序遍历(非递归)
    8. 后序遍历(递归)
    9. 后序遍历(非递归)
    10. 层序遍历(非递归)
    11. 二叉树节点
    下面上代码,有学习的小伙伴,可以联系我,一起学习
    import java.util.LinkedList;
    import java.util.Stack;
    
    public class BinaryTree<T> {
    
    	/**
    	 * 根节点
    	 */
    	public TreeEntry<T> root;
    
    	/**
    	 * 构造函数初始化根节点
    	 * @param rootData
    	 */
    	public BinaryTree(T rootData) {
    		root = new TreeEntry<T>(1, rootData);
    	}
    
    	/**
    	 * 根据层序构建二叉树
    	 * @param a 可选参数
    	 */
    	public void newBinaryTreeByIndex(T... a) {
    		TreeEntry<T> buffer = root;
    
    		// 通过队列构造二叉树
    		LinkedList<TreeEntry<T>> child = new LinkedList<TreeEntry<T>>();
    
    		// 将根节点插入队列
    		child.offer(buffer);
    
    		// 第一个节点的序号为2
    		int i = 2;
    
    		// 遍历可选参数
    		for (T data : a) {
    
    			// 根据当前序号选择左孩子还是右孩子
    			switch (i % 2) {
    
    			// 可以被2整除为做孩子
    			case 0:
    
    				// 取出父节点
    				buffer = child.peek();
    
    				// 通过当前序号和数据构建节点,并设置为父节点的左孩子
    				buffer.leftChild = new TreeEntry<T>(i, data);
    
    				// 将左孩子插入到队列
    				child.offer(buffer.leftChild);
    				break;
    
    			// 除2余1为右孩子
    			case 1:
    
    				// 取出父节点,并移除父节点(弹出)
    				// 因为二叉树每个节点只有两个孩子节点,所以当添加右孩子节点以后可以移除
    				buffer = child.poll();
    
    				// 通过当前序号和数据构建节点,并设置为父节点的右孩子
    				buffer.rightChild = new TreeEntry<T>(i, data);
    
    				// 将右孩子插入到队列
    				child.offer(buffer.rightChild);
    				break;
    
    			default:
    				new RuntimeException("构建二叉树错误!");
    				break;
    			}
    
    			// 自增序号
    			i++;
    
    		}
    	}
    
    	/**
    	 * 得到当前树的深度
    	 * @return 深度
    	 */
    	public int getHeight() {
    
    		return getHeright(root);
    
    	}
    
    	/**
    	 * 递归二叉树深度私有方法
    	 * @param tree 父节点
    	 * @return 深度
    	 */
    	private int getHeright(TreeEntry<T> tree) {
    		// 如果父节点点为空,则返回0
    		if (tree == null) {
    			return 0;
    		} else {
    
    			// i为左子树的深度,j为右子树的深度
    			int i = 0, j = 0;
    
    			// 递归得到左子树的深度
    			i = getHeright(tree.leftChild);
    
    			// 递归的得到右子树的深度
    			j = getHeright(tree.rightChild);
    
    			// 返回左右子树深度更深的一个并加当前层数
    			return i >= j ? i + 1 : j + 1;
    		}
    	}
    
    	/**
    	 * 得到当前树的节点数
    	 * @return
    	 */
    	public int getSize() {
    		return getSize(root);
    	}
    
    	/**
    	 * 递归二叉树节点数方法
    	 * @param tree 父节点
    	 * @return 节点数
    	 */
    	private int getSize(TreeEntry<T> tree) {
    		// 如果节点为空,则返回0
    		if (tree == null) {
    			return 0;
    		} else {
    
    			// i为左子树的节点数,j为右子树的节点数
    			int i = 0, j = 0;
    
    			// 递归得到左子树节点数
    			i = getSize(tree.leftChild);
    
    			// 递归得到右子树节点数
    			j = getSize(tree.rightChild);
    
    			// 返回子树节点数并加当前节点
    			return i + j + 1;
    		}
    	}
    
    	/**
    	 * 递归前序遍历当前树
    	 */
    	public void preOrder() {
    		preOrder(root);
    	}
    
    	/**
    	 * 递归二叉树前序遍历方法
    	 * @param tree
    	 */
    	private void preOrder(TreeEntry<T> tree) {
    		// 如果为空则返回
    		if (tree == null) {
    			return;
    		} else {
    			// 前序遍历的顺序为,根左右
    
    			// 输出根的数据
    			System.out.println(tree.data);
    
    			// 前序遍历左子树
    			preOrder(tree.leftChild);
    
    			// 前序遍历右子树
    			preOrder(tree.rightChild);
    		}
    	}
    
    	/**
    	 * 非递归前序遍历当前树
    	 */
    	public void nonRecPreOrder() {
    		nonRecPreOrder(root);
    
    	}
    
    	/**
    	 * 非递归二叉树前序遍历方法
    	 * @param tree
    	 */
    	private void nonRecPreOrder(TreeEntry<T> tree) {
    		// 通过栈遍历二叉树
    		Stack<TreeEntry<T>> child = new Stack<TreeEntry<T>>();
    
    		// 将根节点压如栈中
    		child.push(tree);
    
    		// 构建临时引用变量
    		TreeEntry<T> temp;
    
    		// 前序遍历的顺序为,根左右
    		// 如果栈不为空则循环
    		while (!child.isEmpty()) {
    
    			// 将栈顶元素弹出到临时变量
    			temp = child.pop();
    
    			// 输出根元素
    			System.out.println(temp.data);
    
    			// 因为栈是后入先出,所以要想先遍历左孩子节点,就要先插入右孩子节点
    			if (temp.rightChild != null) {
    
    				// 将右孩子节点压入栈中
    				child.push(temp.rightChild);
    			}
    
    			if (temp.leftChild != null) {
    
    				// 将左孩子节点压入栈中
    				child.push(temp.leftChild);
    			}
    		}
    
    	}
    
    	/**
    	 * 递归中序遍历当前树
    	 */
    	public void midOrder() {
    		midOrder(root);
    	}
    
    	/**
    	 * 递归二叉树中序遍历方法
    	 * @param tree
    	 */
    	private void midOrder(TreeEntry<T> tree) {
    		// 如果节点为空,则返回
    		if (tree == null) {
    			return;
    		} else {
    
    			// 中序遍历的顺序为,左根右
    
    			// 中序遍历左子树
    			midOrder(tree.leftChild);
    
    			// 输出根节点
    			System.out.println(tree.data);
    
    			// 中序遍历右子树
    			midOrder(tree.rightChild);
    		}
    	}
    
    	/**
    	 * 非递归中序遍历当前树
    	 */
    	public void nonRecMidOrder() {
    
    		nonRecMidOrder(root);
    
    	}
    
    	/**
    	 * 非递归二叉树中序遍历方法
    	 * @param tree
    	 */
    	private void nonRecMidOrder(TreeEntry<T> tree) {
    		// 通过栈遍历二叉树
    		Stack<TreeEntry<T>> child = new Stack<TreeEntry<T>>();
    
    		// 构建临时引用变量
    		TreeEntry<T> temp = tree;
    
    		// 中序遍历顺序,左根右
    
    		// 如果临时变量不为空 或 栈不为空则循环
    		while (temp != null || !child.isEmpty()) {
    
    			// 遍历节点,将当前节点的左孩子节点压入栈中,直到没有左孩子节点为止
    			// 如果临时变量不为空则循环
    			while (temp != null) {
    
    				// 将当前遍历压入栈中
    				child.push(temp);
    
    				// 将临时变量设置为左孩子节点
    				temp = temp.leftChild;
    			}
    
    			// 遍历每个节点的右孩子节点
    			// 如果栈不为空
    			if (!child.isEmpty()) {
    
    				// 将栈顶元素弹出到临时变量
    				temp = child.pop();
    
    				// 输出当前节点的数据
    				System.out.println(temp.data);
    
    				// 将临时变量设置为右孩子节点,使循环后右孩子节点进行遍历左孩子节点
    				temp = temp.rightChild;
    			}
    		}
    	}
    
    	/**
    	 * 递归后序遍历当前树
    	 */
    	public void postOrder() {
    		postOrder(root);
    	}
    
    	/**
    	 * 递归二叉树后续遍历方法
    	 * @param tree
    	 */
    	private void postOrder(TreeEntry<T> tree) {
    		// 如果当前节点为空则返回
    		if (tree == null) {
    			return;
    		} else {
    			// 后续遍历的顺序为,左右根
    
    			// 后续遍历左子树
    			postOrder(tree.leftChild);
    
    			// 后续遍历右子树
    			postOrder(tree.rightChild);
    
    			// 输出根元素
    			System.out.println(tree.data);
    		}
    	}
    
    	/**
    	 * 非递归后续遍历当前树
    	 */
    	public void nonRecPostOrder() {
    		nonRecPostOrder(root);
    
    	}
    
    	/**
    	 * 非递归二叉树后续遍历
    	 * @param tree
    	 */
    	private void nonRecPostOrder(TreeEntry<T> tree) {
    		// 通过栈后序遍历二叉树
    		Stack<TreeEntry<T>> child = new Stack<TreeEntry<T>>();
    
    		// 创建临时节点 和 上一个遍历的节点,并赋值为根节点
    		TreeEntry<T> temp = tree, prev = tree;
    
    		// 如果临时节点不为空 或 栈不为空则继续遍历则循环
    		while (temp != null || !child.isEmpty()) {
    
    			// 遍历节点,将当前节点的左孩子节点压入栈中,直到没有左孩子节点为止
    			// 如果临时变量不为空则循环
    			while (temp != null) {
    				child.push(temp);
    				temp = temp.leftChild;
    			}
    
    			// 遍历每个节点的右孩子节点
    			// 如果栈不为空
    			if (!child.isEmpty()) {
    
    				// 取出栈顶元素的右孩子节点设置为临时右孩子节点
    				TreeEntry<T> tempRight = child.peek().rightChild;
    
    				// 如果临时右孩子节点为空,或者临时右孩子节点是上一个遍历的节点,则遍历父节点
    				// 否则,临时右孩子节点不为空,遍历临时右孩子节点的子树
    				if (tempRight == null || tempRight == prev) {
    
    					// 弹出栈顶元素(临时右孩子节点的父节点),并设置为临时节点
    					temp = child.pop();
    
    					// 输出临时节点的数据
    					System.out.println(temp.data);
    
    					// 将临时节点设置为上一个遍历的节点
    					prev = temp;
    
    					// 将临时节点设置为空
    					temp = null;
    				} else {
    
    					// 将临时右孩子节点设置为临时节点,进入下一个循环时,遍历临时右孩子节点的子树
    					temp = tempRight;
    				}
    			}
    		}
    	}
    
    	/**
    	 * 递归层序遍历当前树
    	 */
    	public void indOrder() {
    		indOrder(root);
    	}
    
    	/**
    	 * 递归二叉树层序遍历方法
    	 * @param tree
    	 */
    	private void indOrder(TreeEntry<T> tree) {
    
    		// 如果当前节点为空,则返回
    		if (tree == null) {
    			return;
    		} else {
    
    			// 通过队列进行层序宾利
    			LinkedList<TreeEntry<T>> child = new LinkedList<TreeEntry<T>>();
    
    			// 将根节点存入队列
    			child.offer(tree);
    
    			// 设置临时节点变量
    			TreeEntry<T> temp;
    
    			// 输出当前节点
    			System.out.println(tree.data);
    
    			// 如归队首节点不为空,则循环
    			while ((temp = child.poll()) != null) {
    
    				// 如果临时节点的左孩子节点不为空
    				if (temp.leftChild != null) {
    
    					// 输出左孩子节点的数据
    					System.out.println(temp.leftChild.data);
    
    					// 将左孩子节点存入队列
    					child.offer(temp.leftChild);
    				}
    
    				// 如果临时节点的右孩子节点不为空
    				if (temp.rightChild != null) {
    
    					// 输出右孩子节点的数据
    					System.out.println(temp.rightChild.data);
    
    					// 将右孩子节点的存入队列
    					child.offer(temp.rightChild);
    				}
    
    			}
    
    		}
    	}
    
    	public class TreeEntry<T> {
    		private int index;
    		private T data;
    		private TreeEntry leftChild;
    		private TreeEntry rightChild;
    
    		public TreeEntry(int index) {
    			super();
    			this.index = index;
    		}
    
    		public TreeEntry(int index, T data) {
    			super();
    			this.index = index;
    			this.data = data;
    		}
    
    		public int getIndex() {
    			return index;
    		}
    
    		public void setIndex(int index) {
    			this.index = index;
    		}
    
    		public T getData() {
    			return data;
    		}
    
    		public void setData(T data) {
    			this.data = data;
    		}
    
    		public TreeEntry getLeftChild() {
    			return leftChild;
    		}
    
    		public void setLeftChild(TreeEntry leftChild) {
    			this.leftChild = leftChild;
    		}
    
    		public TreeEntry getRightChild() {
    			return rightChild;
    		}
    
    		public void setRightChild(TreeEntry rightChild) {
    			this.rightChild = rightChild;
    		}
    
    		@Override
    		public String toString() {
    			return data.toString();
    		}
    
    	}
    }
    


    展开全文
  • 主要介绍了Java二叉树建立和各种遍历实例代码,涉及树节点的定义,后序遍历,层序遍历,深度优先和广度优先等相关内容,具有一定借鉴价值,需要的朋友可以参考下
  • 1. 前言 1.1 二叉树定义 二叉树是N个结点的有限集合,该集合或者为空集,或者由一个根节点跟两棵互不相交的、分别称为根节点的左子树或者右子树...2. java构建二叉树代码示例 2.1 二叉树的存储结构 以二叉链表存储为例

    1. 前言

    1.1 二叉树定义

    二叉树是N个结点的有限集合,该集合或者为空集,或者由一个根节点跟两棵互不相交的、分别称为根节点的左子树或者右子树的二叉树组成。

    1.2 二叉树的特点

    • 每个结点最多有两个子树
    • 左子树跟右子树是有序的
    • 树中某个结点只有一棵子树,也要区分是左子树还是右子树

    1.3 二叉树的形态

    • 空二叉树

    • 只有一个根结点

    • 根结点只有左子树

    • 根结点只有右子树

    • 根结点既有左子树,又有右子树

    2. java构建二叉树代码示例

    2.1 二叉树的存储结构

    以二叉链表存储为例
    在这里插入图片描述

    2.2 示例

    以下是构建一个普通二叉树的代码,根结点的左叶子结点会小于根结点,右叶子结点反之。

    public class BinaryTree {
    
    	//根结点,默认为null
    	private Node root = null;
    
    	public Node getRoot() {
    		return root;
    	}
    
    	//通过内部类,构建结点
    	private class Node{
    		//左节点
    		private Node left;
    		//数据域
    		private int data;
    		//右节点
    		private Node right;
    
    		public Node(int data) {
    			this.data = data;
    		}
    
    		public Node getLeft() {
    			return left;
    		}
    
    		public void setLeft(Node left) {
    			this.left = left;
    		}
    
    		public int getData() {
    			return data;
    		}
    
    		public void setData(int data) {
    			this.data = data;
    		}
    
    		public Node getRight() {
    			return right;
    		}
    
    		public void setRight(Node right) {
    			this.right = right;
    		}
    	}
    
    
    	/**
    	 * 创建人:贺小五
    	 * 创建时间:2017-09-16 00:54:52
    	 * 描述:
    	 * 		构建二叉树
    	 * 	    Node 为结点,
    	 * 	    data 为数据
    	 */
    	private void buildBiTree(Node node,int data){
    		//如果根结点是空,那么设置根结点,并且设置数据域
    		if(root == null){
    			root = new Node(data);
    		}else{
    			/**
    			 * 根结点不为空,那么判断数据是否小于当前结点的数据
    			 */
    			if(data<node.getData()){
    				//如果小于,判断当前结点是否有左叶子结点
    				if(node.getLeft()==null){
    					//左叶子结点为空,设置左叶子结点,并且设置数据
    					node.setLeft(new Node(data));
    				}else{
    					//左叶子结点不为空,递归调用构建二叉树的函数
    					buildBiTree(node.getLeft(),data);
    				}
    			}else{
    				//如果大于或等于,判断当前结点是否存在右叶子结点
    				if(node.getRight()==null){
    					//右叶子结点为空,设置右叶子结点,并且设置数据域
    					node.setRight(new Node(data));
    				}else{
    					//右叶子几点不为空,递归调用构建二叉树的函数
    					buildBiTree(node.getRight(),data);
    				}
    			}
    		}
    	}
    
    	/**
    	 * 创建人:贺小五
    	 * 创建时间:2017-09-16 01:01:30
    	 * 描述:
    	 * 		创建二叉树函数
    	 * 		int[] 是个int类型的数组
    	 * 		通过循环调用,往二叉树插入数据
    	 */
    	public static BinaryTree createBiTree(int[] datas){
    		BinaryTree binaryTree = new BinaryTree();
    		for (int data : datas) {
    			binaryTree.buildBiTree(binaryTree.getRoot(),data);
    		}
    
    		return binaryTree;
    	}
    }
    

    然后我们上一段测试代码,往该树插入数据:

    	public static void main(String[] args) {
    
    		int[] datas = {72,37,29,55,51,80};
    
    
    		BinaryTree biTree = BinaryTree.createBiTree(datas);
    
    	}
    

    执行测试代码后,结构应该是如下图(测试的同学可以debug 看树的结构)
    在这里插入图片描述

    展开全文
  • Java实现二叉树

    2021-03-17 19:52:28
    Java实现二叉树 主要内容: 二叉树的链表表示法, 二叉树的先根、中根和后根三种遍历方法。 二叉树的查找、插入和构建。 二叉查找树BST的查找、插入、删除和构建。 平衡二叉树的查找、插入和构建代码完美可以运行...

    Java实现二叉树

    主要内容:

    二叉树的链表表示法,
    二叉树的先根、中根和后根三种遍历方法。
    二叉树的查找、插入和构建。
    二叉查找树BST的查找、插入、删除和构建。
    平衡二叉树的查找、插入和构建。
    代码完美可以运行,暂时不写基础内容了,直接上代码。

    package com.tree.binary_Tree;
    
    //递归定义
    /* 要不没有根节点 是一颗空树
    要不由根结点 左子树 和 右子树构成 且左右子树均为二叉树*/
    
    import com.sun.org.apache.bcel.internal.generic.IF_ACMPEQ;
    import org.junit.Test;
    
    import java.util.LinkedList;
    
    //物理结构  链表  ————> 二叉链表
    class BinaryNode {
        private int data;  //数据域
        private int layer;  //层次
        private int height;  //高度,AVL需要结点高度计算平衡因子
        private BinaryNode lchild;  //左子树
        private BinaryNode rchild;  //右子树
    
        public BinaryNode() {   //无参构造
        }
    
        /*
        public BinaryNode(int data) {
            this.data = data;
        }
    
        public BinaryNode(int data, BinaryNode lchild, BinaryNode rchild) {
            this.data = data;
            this.lchild = lchild;
            this.rchild = rchild;
        }*/    //构造方法先去掉吧
    
        public int getHeight(){return height; }
    
        public void setHeight(int height){this.height = height; }
    
        public int getLayer() {return layer; }
    
        public void setLayer(int layer){this.layer = layer; }
    
        public int getData() {
            return data;
        }
    
        public void setData(int data) {
            this.data = data;
        }
    
        public BinaryNode getLchild() {
            return lchild;
        }
    
        public void setLchild(BinaryNode lchild) {
            this.lchild = lchild;
        }
    
        public BinaryNode getRchild() {
            return rchild;
        }
    
        public void setRchild(BinaryNode rchild) {
            this.rchild = rchild;
        }
    }
    
    
    //二叉树的操作类
    public class BinaryTree {
    
        //创建一个新结点
        public static BinaryNode newNode(int data){
            BinaryNode binaryNode = new BinaryNode();  //先new出实例
            binaryNode.setData(data);
            binaryNode.setLchild(null);
            binaryNode.setRchild(null);
            binaryNode.setHeight(1);  //新生成的结点初始高度为1 这是为了AVL树相关内容,其他内容不受次代码影响
            return binaryNode;
        }
    
    
        //二叉树的遍历
        //1> 先根遍历 参数为root 是一颗给定二叉树的根结点
        public static void preOrder(BinaryNode root){
            if (root == null) {
                return;
            }
            System.out.println(root.getData());   //根
            preOrder(root.getLchild());  //左
            preOrder(root.getRchild());  //右
        }
        //2> 中根遍历
        public static void inOrder(BinaryNode root){
            if (root == null) {
                return;
            }
            inOrder(root.getLchild());  //左
            System.out.println(root.getData());    //根
            inOrder(root.getRchild());  //右
        }
        //3> 后根遍历
        public static void postOrder(BinaryNode root){
            if (root == null) {
                return;
            }
            postOrder(root.getLchild()); //左
            postOrder(root.getRchild()); //右
            System.out.println(root.getData());     //根
        }
        //4> 难点 层次遍历
        //思想 利用队列 BFS思想
        public static void layerOrder(BinaryNode root){
            //搞个队列
            LinkedList list = new LinkedList();
            if (root != null){  //先把根插入队列里
                list.add(root);
            }
            while (!list.isEmpty()){
                BinaryNode node = (BinaryNode) list.getFirst();  //取出队首的元素
                list.removeFirst();    //将队首元素移除
                System.out.println(node.getData());   //访问它
                if (node.getLchild() != null){     //如果它有左右子树,则把它们分别依次加入队列中
                    list.add(node.getLchild());
                }
                if (node.getRchild() != null){
                    list.add(node.getRchild());
                }
            }
        }
    
        //5> 常考 要求记录各个结点的层数 这样的情况下需要修改BinaryNode结点的结构,附加一个层次信息如下
        /*class BinaryNode{
            private int data;  //数据域
            private int layer;  //层次
            private com.tree.binary_Tree.BinaryNode lchild;  //左子树
            private com.tree.binary_Tree.BinaryNode rchild;  //右子树
        }*/
        //下面函数层次遍历二叉树,并且给出每个结点的层数
        public static void getNodelayer(BinaryNode root){
            LinkedList list = new LinkedList();
            if (root != null){
                root.setLayer(0);   //根结点设成第0层
                list.add(root);
            }
            while (!list.isEmpty()){
                BinaryNode node = (BinaryNode) list.getFirst();
                list.removeFirst();   //弹出队首元素
                System.out.println(node.getData() + "层数为:" + node.getLayer());
                if (node.getLchild() != null){
                    node.getLchild().setLayer(node.getLayer() + 1);
                    list.add(node.getLchild());
                }
                if (node.getRchild() != null){
                    node.getRchild().setLayer(node.getLayer() + 1);
                    list.add(node.getRchild());
                }
            }
        }
    
        //6> 给定一个二叉树的先序序列和中序序列 重建这棵树 递归思想
        //参数说明 【preL, preR】是先序序列的端点 【inL, inR】是中序序列的端点
        // 假设序列里没有重复数值 int[] pre 是先序数组, int[] in 是中序数组
        //基本思想是每次通过一对儿【preL, preR】,【inL, inR】能唯一确定一个结点的位置
    
        public static BinaryNode create(int preL, int preR, int inL, int inR, int[] pre, int[] in){
            if (preL > preR){   //递归基线 区间长度为0即可退出
                return null;
            }
            int num = pre[preL];  //根结点值域
            BinaryNode root = new BinaryNode();
            root.setData(num);   //设置根结点的值域
            int k = 0;   //在中根序列中找根结点的位置 用k记录
            for (int i = inL; i <= inR; ++i) {  // (注意这个i 不是丛0 到 in.length-1)
                if (in[i] == num){
                    k = i;
                    break;
                }
            }
            int numLeft = k - inL;  //计算一下左子树的区间长度
            //对于左子树 递归区间为 【preL + 1, preL + numLeft】 + 【inL, k-1】 递归数组不用变还是int[] pre和 int[] in
            root.setLchild(create(preL + 1, preL + numLeft, inL, k-1, pre, in));
            //对于右子树 递归区间为 【preL + numLeft + 1, preR】 + 【k + 1, inR】
            root.setRchild(create(preL + numLeft + 1, preR, k + 1, inR, pre, in));
            return root;  //返回根的地址
        }
    
    
        // 7> 查找某一个结点  二叉树的遍历
        /* 查找是否有数据域等于给定key的结点  如果有则将其值改为newkey
        * 参数 BinaryNode root 以root为根的一颗二叉树
        * int key  待查找值*/
        public static void search(BinaryNode root, int key, int newkey){
            if (root == null){
                return;
            }
            if (root.getData() == key){
                root.setData(newkey);
            }
            search(root.getLchild(), key, newkey);
            search(root.getRchild(), key, newkey);
        }
    
        //8> 二叉查找树
        //8.1> 查找 值为key 的结点 没有找到则给出信息 递归 复杂度O(logn)
        public static void search(BinaryNode root, int key){
            if (root == null){
                System.out.println("NO!");
                return;
            }
            if (root.getData() == key){
                System.out.println("找到了" + key + "!");
            } else if (key < root.getData()){
                search(root.getLchild(), key);
            } else {
                search(root.getRchild(), key);
            }
        }
    
        /*// 8.2> 插入结点 跟差找流程一样,只不过在查找失败时说明在这个位置应该插入新的结点
        //  这个代码块跳出去之后树没有发生改变,只发生了值传递
        public static void insert(BinaryNode root, int key){
            if (root == null){
                root = BinaryTree.newNode(key);
                System.out.println(root.getData());
                System.out.println("==================");
                return;
            }
            if (root.getData() == key){
                System.out.println("已经有" + key + "了!");
                return;
            } else if (key < root.getData()){
                insert(root.getLchild(), key);
            } else {
                insert(root.getRchild(), key);
            }
        }*/
    
        // 8.2.1> 插入结点 跟差找流程一样,只不过在查找失败时说明在这个位置应该插入新的结点
        public static BinaryNode insert(BinaryNode root, int key){
            if (root == null){
                root = newNode(key);
                return root;
            }
            if (root.getData() == key){
                System.out.println("已经有" + key + "了!");
            } else if (key < root.getData()) {
                root.setLchild(insert(root.getLchild(), key));
            } else {
                root.setRchild(insert(root.getRchild(), key));
            }
            return root;
        }
    
        //  8.3> 二叉查找树的构建 不使用双序列构建,直接用插入的方式在插入结点的过程中就自然地构建好了二叉查找树
        //参数 int[] data 元素互不相同,但是不需要保证是递增的 顺序是任意的 但是同一组数据的不同排序会构建出不同的二叉树
        public static BinaryNode createBST(int[] data){
            BinaryNode root = null;   //根结点 初始为空
            for (int i = 0; i < data.length; i++) {
                root = BinaryTree.insert(root, data[i]);   // 这是难点
                //这root本质就是个初值为null的指针,每执行insert(root, data[i])一次就生成
                //一个新的二叉树,只需要用root指向它的根结点,就能保证找到这个树
            }
            return root;
        }
    
        //9> 二叉查找树的删除
        //9.1> 寻找root为根的二叉查找树中的最小权值和最大权值结点
        //最小结点即二叉排序树最左边的结点,最大结点即是二叉树中最右的结点
        //最小结点丛root开始,一直沿着lChild链找直到lChild为空 最大结点丛root开始一直沿着rChild链找直到rChild为空
        public static BinaryNode findMax(BinaryNode root){
            while (root.getRchild() != null){
                root = root.getRchild();
            }
            return root;
        }
    
        public static BinaryNode findMin(BinaryNode root){
            while (root.getLchild() != null){
                root = root.getLchild();
            }
            return root;
        }
    
        //删除二叉查找树数值域为key的结点,如果删的是叶节点则直接删除即可,如果待删除的结点有左子树时,用它的前驱代替删除了的结点
        //并在它的左子树里删除前驱结点,如果待删除的结点没有左子树但是有右子树,则用它的后继代替它,并在其右子树中删除其后继
        //前驱是小于它的最大点,后继是大于它的最小点
        public static BinaryNode deleteNode(BinaryNode root, int key){
            if (root == null){
                return null;
            }
            if (root.getData() == key){
                if (root.getLchild() == null && root.getRchild() == null){
                    root = null;    //是叶节点,直接删除
                    return root;
                } else if (root.getLchild() != null){
                    BinaryNode preNode = BinaryTree.findMax(root.getLchild());  //找前驱
                    root.setData(preNode.getData());    //用前驱的数值代替待删除结点数值
                    root.setLchild(deleteNode(root.getLchild(), preNode.getData()));  //在左子树中递归删除前驱结点
                } else {    //无左子树但是有右子树
                    BinaryNode nextNode = BinaryTree.findMin(root.getRchild()); //到后继结点
                    root.setData(nextNode.getData());   //换数值
                    root.setRchild(deleteNode(root.getRchild(), nextNode.getData()));  //在右子树中递归删除后继结点
                }
            } else if (key < root.getData()){  //去左子树中递归删除
                root.setLchild(deleteNode(root.getLchild(), key));
            } else {   //去右子树中递归删除
                root.setRchild(deleteNode(root.getRchild(), key));
            }
            return root;
        }
    
    
        //10> AVL树走起!
        //这个函数获取以root为根的树的高度
        public static int getHeight(BinaryNode root){
            if (root == null){
                return 0;
            }
            return root.getHeight();
        }
    
        //计算结点root的平衡因子
        public static int getBalanceFacter(BinaryNode root){
            if (root == null){
                return 0;
            }
            if (root.getLchild() != null && root.getRchild() != null){
                return root.getLchild().getHeight() - root.getRchild().getHeight();
            } else {
                if (root.getLchild() == null){
                    return - root.getRchild().getHeight();
                }else {
                    return root.getLchild().getHeight();
                }
            }
        }
    
        //更新root结点的高度,即左右子树的最大高度再加一
        public static void updateHeight(BinaryNode root){
            if (root.getLchild() != null && root.getRchild() != null){
                root.setHeight(Math.max(root.getLchild().getHeight(), root.getRchild().getHeight()) + 1);
            } else {
                if (root.getLchild() == null){
                    root.setHeight(root.getRchild().getHeight() + 1);
                } else {
                    root.setHeight(root.getLchild().getHeight() + 1);
                }
            }
        }
    
        // 10.1> AVL树的查找
        //直接用二叉查找树的查找代码即可
    
        // 10.2> AVL树的插入操作
        //左旋
        public static BinaryNode leftRotation(BinaryNode root){
            BinaryNode temp = root.getRchild();  //标记root的右儿子,即将成为根结点
            root.setRchild(temp.getLchild());   // temp的左子树接为root的右子树
            temp.setLchild(root);    //temp的左子树变为root
            // 这两布很关键,root和temp的左右子树都调整了,需要重新更新它们的height
            updateHeight(root);
            updateHeight(temp);
            root = temp;   //temp结点变为根结点
            return root;
        }
    
        //右旋
        public static BinaryNode rightRotation(BinaryNode root){
            BinaryNode temp = root.getLchild();  //标记root的左儿子,即将成为根结点
            root.setLchild(temp.getRchild());   // temp的左子树接为root的右子树
            temp.setRchild(root);    //temp的左子树变为root
            // 这两布很关键,root和temp的左右子树都调整了,需要重新更新它们的height
            updateHeight(root);
            updateHeight(temp);
            root = temp;   //temp结点变为根结点
            return root;
        }
    
        // 插入代码 在普通的二叉查找树基础上进行旋转树
        public static BinaryNode insertAVL(BinaryNode root, int key){
            if (root == null){   //为空时说明没有找到key,此处就是插入位置
                root = newNode(key);
                return root;
            }
            if (root.getData() == key){
                System.out.println("已经有" + key + "了!");
            } else if (key < root.getData()){    //要在左子树里插入
                root.setLchild(insertAVL(root.getLchild(), key));
                updateHeight(root);  //更新树高
                if (getBalanceFacter(root) == 2){    //不平衡了 需要调整
                    if (getBalanceFacter(root.getLchild()) == 1){   //LL型
                        root = rightRotation(root);    //一次右旋搞定
                    } else if (getBalanceFacter(root.getLchild()) == -1){  //LR型
                        root.setLchild(leftRotation(root.getLchild()));  //先给root的左子树左旋
                        root = rightRotation(root);   //然后root右旋
                    }
                }
            } else {     //要在右子树里插入
                root.setRchild(insertAVL(root.getRchild(), key));  //递归插入
                updateHeight(root);   //更新高度
                if (getBalanceFacter(root) == -2){   //不平衡需要调整了
                    if (getBalanceFacter(root.getRchild()) == -1){  //RR型
                        root = leftRotation(root);    //root一次左旋
                    } else if (getBalanceFacter(root.getRchild()) == 1){   //RL型
                        root.setRchild(rightRotation(root.getRchild()));
                        root = leftRotation(root);
                    }
                }
            }
            return root;
        }
    
        //最后就是AVL树的数组建立方法 基于二叉查找树,边插入 边建树 边调整 三步同时进行
        public static BinaryNode createAVL(int[] data){
            BinaryNode root = null;  //根结点初始化为空
            for (int i = 0; i < data.length; i++) {
                root = insertAVL(root, data[i]);
            }
            return root;
        }
    
        //AVL的删除操作比较复杂 暂时不予涉猎
    }
    
    //测试一般二叉树的构建和遍历
    class Test01{
        public static void main(String[] args) {
            int[] pre = new int[]{1,2,4,5,3,6,7};
            int[] in = new int[]{4,2,5,1,6,3,7};
            BinaryNode root = BinaryTree.create(0, 6, 0, 6, pre, in);
            BinaryTree.preOrder(root);
            System.out.println("==============");
            BinaryTree.postOrder(root);
            System.out.println("==============");
            BinaryTree.layerOrder(root);
        }
    }
    //测试二叉查找树的构建和验证
    class Test02{
        public static void main(String[] args) {
            int[] pre = new int[]{4,3,2,9,6,11};
            int[] in = new int[]{2,3,4,6,9,11};
            BinaryNode root = BinaryTree.create(0, 5, 0, 5, pre, in);
            /*BinaryTree.search(root,4);
            BinaryTree.search(root,8);*/
            root = BinaryTree.insert(root, 7);
            root = BinaryTree.insert(root, 10);
            BinaryTree.inOrder(root);
        }
    }
    //测试二叉查找树的数组构建
    class Test03{
        public static void main(String[] args) {
            //同一组数据的不同排列
            int[] data1 = new int[]{1,2,4,6,8,13,55,100};
            int[] data2 = new int[]{2,4,1,8,13,6,100,55};
            BinaryNode root1 = BinaryTree.createBST(data1);
            BinaryNode root2 = BinaryTree.createBST(data2);
            //两者的中根序是一样的
            BinaryTree.inOrder(root1);
            System.out.println("===");
            BinaryTree.inOrder(root2);
            //但是两者别的遍历结果不一样说明树结构是不一样的
            System.out.println("===");
            BinaryTree.preOrder(root1);
            System.out.println("===");
            BinaryTree.preOrder(root2);
        }
    }
    //测试二叉查找树的删除操作
    class Test04{
        public static void main(String[] args) {
            int[] data = new int[]{2,4,1,8,13,6,100,55};
            BinaryNode root = BinaryTree.createBST(data);
            BinaryTree.preOrder(root);
            System.out.println("===");
            root = BinaryTree.deleteNode(root,13);
            BinaryTree.preOrder(root);
        }
    }
    
    //测试AVL
    class Test05{
        public static void main(String[] args) {
            int[] data = new int[]{8,4,9,1,6};
            BinaryNode root = BinaryTree.createBST(data);
            BinaryTree.preOrder(root);
            System.out.println("===");
            root = BinaryTree.insertAVL(root,3);
            BinaryTree.preOrder(root);
        }
    }
    

    知识小结

    二叉树的三种遍历中
    1 前和后其实性质类似,能够确定出二叉树的根结点
    2 只有通过中遍历才能确定出左右子树
    3 因此至少要知道中 和 前后任意一者才能确定出二叉树
    4 这个结论前提是二叉树的数值域各不相同

    完全二叉树的数组存储法
    1 完全二叉树有k层 (根为第1层)
    2 结点个数为2^k - 1 个
    3 整个数组 大小为2^k 即比结点个数多1
    4 先将根结点的值域存放在数组下标1处 数组第一个元素空开不存数据或者设个其他默认值
    5 之后按层次遍历依次存放剩余结点
    6 数组放好后,对任意结点,其下标为i,则其左右结点分别为2i 和2i + 1
    7 叶结点的判断条件为其下标 i*2 > 结点总数 即2^k - 1

    二叉查找树相关
    1 是二叉树
    2 左子树的值小于等于根
    3 右子树的值大于根
    4 用来排序的 排序结果用中序遍历 由小到大
    5 便于查找 O(h)
    6 用数组构建二叉查找树时,不同的排序方式构造出的树结构不一样
    7 如果数组元素是递增排序,则构建出的二叉树是退化树
    即它们的中根序一样,但是别的遍历结果不一样

    二叉查找树的删除其他注意问题
    1 本代码是递归删除法 容易理解
    2 还有一种删除前驱或者后继的思路 这也是最开始习惯于想到的思路
    那就是记录后继next结点的父节点p,则next一定是p的左儿子,这时next本身是一定没有左子树了
    如果也没有右子树那么直接让p的左儿子指针赋值空就ok,如果next结点有右子树,则将next的右子树
    接到p的左子树即可。
    3 删除前驱是同理的。前驱结点pre必定是其父节点的右儿子且本身没有右子树,考察它有无左子树就ok
    4 这个方法需要额外能向上查询到父节点
    5 本代码实现其实是优先删除前驱了,即有左子树的情况下肯定删前驱
    这样操作多了会导致二叉查找树不平衡,退化成一条链
    6 5中的解决方法,1> 交替删除前驱或后继 2> 记录子树高度,优先删较高的一枝子树

    二叉查找树引出平衡二叉树
    二叉查找树具有高效的查找功能,尽可能保证每个结点均有左右子节点最好
    这种形态的二叉查找树高度最小,故查找复杂度才低

    展开全文
  • Java创建二叉树java

    2016-08-17 15:45:39
    代码实现: 二叉树的查找、插入、删除和输出根节点到当前节点的路径 二叉树的前序遍历,中序遍历和后续遍历 TreeNode.java --定义树节点 Mytree.java----创建树结构和上述功能函数 TestTree.java --测试上述的功能
  • 测试时,二叉树是采用逐个节点搭建的方法构建的 Node类:树的节点类 public class Node { private int no; private Node left; private Node right; public Node() { } public Node(int no) { this.no =...

    测试时,二叉树是采用逐个节点搭建的方法构建的

    Node类:树的节点类

    public class Node {
        private int no;
        private Node left;
        private Node right;
    
        public Node() {
        }
    
        public Node(int no) {
            this.no = no;
        }
    
        public int getNo() {
            return no;
        }
    
        public void setNo(int no) {
            this.no = no;
        }
    
        public Node getLeft() {
            return left;
        }
    
        public void setLeft(Node left) {
            this.left = left;
        }
    
        public Node getRight() {
            return right;
        }
    
        public void setRight(Node right) {
            this.right = right;
        }
    
        @Override
        public String toString() {
            return "Node{" +
                    "no=" + no +
                    '}';
        }
        //前序遍历
        public void preOrder(){
            System.out.println(this);
            if(this.left != null){
                this.left.preOrder();
            }
            if(this.right != null){
                this.right.preOrder();
            }
        }
        //中序遍历
        public void infixOrder(){
            if(this.left != null){
                this.left.infixOrder();
            }
            System.out.println(this);
            if(this.right != null){
                this.right.infixOrder();
            }
        }
        //后序遍历
        public void postOrder(){
            if(left != null){
                left.postOrder();
            }
            if(right != null){
                right.postOrder();
            }
            System.out.println(this);
        }
    }
    

    BinaryTree类:二叉树类

    public class BinaryTree {
        private Node root;
    
        public void setRoot(Node root) {
            this.root = root;
        }
    
        public Node getRoot() {
            return root;
        }
    
        public void preOrder(){
            if(root == null){
                System.out.println("二叉树为空");
                return;
            }
            root.preOrder();
        }
    
        public void infixOrder(){
            if(root == null){
                System.out.println("二叉树为空");
                return;
            }
            root.infixOrder();
        }
    
        public void postOrder(){
            if(root == null){
                System.out.println("二叉树为空");
                return;
            }
            root.postOrder();
        }
    }
    

    UseBinaryTree类:二叉树遍历测试类

    public class UseBinaryTree {
        public static void main(String[] args) {
            Node n1 = new Node(1);
            Node n2 = new Node(2);
            Node n3 = new Node(3);
            Node n4 = new Node(4);
            Node n5 = new Node(5);
            Node n6 = new Node(6);
            BinaryTree bt = new BinaryTree();
            bt.setRoot(n1);
            bt.getRoot().setLeft(n2);
            bt.getRoot().setRight(n3);
            n2.setLeft(n4);
            n2.setRight(n5);
            n3.setLeft(n6);
            bt.preOrder();
            bt.infixOrder();
            bt.postOrder();
        }
    }
    

    欢迎讨论

    展开全文
  • 在学数据结构的时候基本没有自己实现过树的代码,现在基本把原理也丢的差不多了,打算陆续做个整理,毕竟温故而知新二叉树二叉树是每个节点最多有两个子树的树结构。通常子树被称作 “左子树” 和 “右子树”。比如...
  • * 二叉树结点有三个属性; * 一个int存放数据,leftchild指向左孩子,rightchild指向右孩子 */ class BinaryTreeNode{ private int data; private BinaryTreeNode leftChild; private BinaryTreeNode right...
  • Java二叉树建立以及遍历
  • 首先我们要明白先中后序遍历的特点: 先序遍历中 第一个一定是根结点。 中序遍历中 根结点左子树的...根据先序遍历和中序遍历构建二叉树 解题细想: 设置变量inedx 方便从preorder数组中获取元素构建结点。 判断i...
  • 1、二叉树的数据结构:二叉链表 package BT; public class BinearyTree&lt;E&gt; {  E data;   BinearyTree&lt;E&gt; lchild;  BinearyTree&lt;E&gt; rchild;  public BinearyTree(E...
  • java表达式二叉树构建

    千次阅读 2018-09-12 20:50:59
    通过自然表达式的优先级顺序,构建出与表达式相应的二叉树模型,这样的二叉树模型就是表达式二叉树。 例如:(a*c+b)-d*e 这样的一个表达式,表达式二叉树的存放规则是:数据放在子节点位置,符号放在父节点(或根...
  • 建树假设现在有个二叉树,如下:此时遍历顺序是:PreOrder: GDAFEMHZInOrder: ADEFGHMZPostOrder: AEFDHZMG现在给出先序(preOrder)和中序(InOrder),建立一颗二叉树或者给出中序(InOrder)和后序(PostOrder),建立二.....
  • java实现二叉树

    2017-12-05 18:54:51
    需求:构建二叉树,实现先序遍历、中序遍历、BFS、DFS。分析:1、与完全二叉树类似,只是有些非最后一层的节点只有左儿子或者右儿子,或者没有儿子节点。仍然可以参照完全二叉树,采用宽度优先遍历将所有节点信息写...
  • Java实现二叉树的3种方式,顺序二叉树的实现,二叉树的三叉链表存储,二叉树的二叉链表实现
  • 当一个白嫖党太久了,今儿写个作业,发现java顺序二叉树的删除的帖子不怎么多,于是乎打算自己也写一下。 二叉树建立、遍历等暂且不论,直接搞上核心删除部分,但总感觉怪麻烦的,归根结底还是too vegetable,哎~~...
  • Java重建二叉树

    2017-03-15 16:37:05
    输入前序和中序二叉树遍历的结果,重建出该二叉树。 直接上代码,可以参考代码中的相关注释。 首先定义树的结点结构,如下:package tree; public class Tree { public int val; public Tree left_child; ...
  • java 二叉树

    2017-06-22 21:28:49
    java 二叉树 leetcode(一)首先来看看 java 生成二叉树 直接上代码 生成二叉树步骤 创建二叉树节点对象 创建存储所有二叉树节点的集合 list 使用LinkedList是因为这是链表数组结构 add 和 remove 操作比arrayList ...
  • java初始化和构建二叉树

    千次阅读 2019-05-19 13:37:13
    首先请看如下什么叫做完全二叉树,本人认为以完全二叉树的方法构建二叉树算比较的简单,易实现。。 下面,我们就按照构建完全二叉树的形式来构建我们的二叉树: 主干代码为: import java.util.ArrayList; ...
  • Java实现二叉树,方便刷leetcode

    千次阅读 2020-12-19 12:55:14
    最近在leetcode上刷树和dfs的题,简单题中经常遇到二叉树这种数据结构,因为实在太菜,肉眼debug太困难,为了找错方便我在本地建立了与leetcode上相同的二叉树结构,提供了层序建立二叉树和递归建立二叉树两种方法,...
  • java实现二叉树的遍历算法 用java实现二叉树的遍历算法,编写二叉树类BinaryTree 代码如下: package package2; public class BinaryTree { int data; //根节点数据 BinaryTree left; //左子树 BinaryTree right; ...
  • 我们来用java构造一下下图中的二叉树,并实现该二叉树的前序、中序和后序遍历。二叉树都是由节点组成的,所以我们首先要有个节点类。TreeNode类代码:public class TreeNode { private int num; private TreeNode ...
  • Java 创建二叉树

    千次阅读 2018-04-04 10:27:39
    在leetcode做了那么多道树的题,却发现自己连创建二叉树都写不出来,绝望.jpg,点开leetcode的debug界面,看到人家写的创建二叉树代码,简洁又优雅,学习 public static TreeNode stringToTreeNode(String ...
  • 使用Java实现二叉树及其遍历操作 实现二叉树 首先实现二叉树的结点元素 此处结点元素定义为树结点的值和二叉树结点类型的左孩子和右孩子 操作为构建、遍历操作(前序遍历、中序遍历、后续遍历) 代码如下 ...
  • java 重建二叉树

    2021-01-16 11:55:44
    利用先序和中序遍历结果数组 pre 和 in,重建二叉树 首先考虑初始情况,即两个初始数组 pre,in pre[0] 作为先序遍历的第一个节点,也是树根节点,把 in 划分为左右子树两个区间 inleft 和 inright 根据 in 中 pre[0...
  • Java实现二叉树的遍历

    2017-03-26 21:09:46
    目录:  1.把一个数组的值赋值给一颗二叉树  ...Java代码  package tree;    import java.util.LinkedList;  import java.util.List;    /**   * 功能:把一个数组的值存入二叉树中,
  • 转载为了方便以后重看,请看原文:... 目录:  1.把一个数组的值赋值给一颗二叉树  2.具体代码  ...1.树的构建方法  ...2.具体代码  ...Java代码  package tree;    import java.util.LinkedList;  i

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 26,055
精华内容 10,422
关键字:

java构建二叉树代码

java 订阅