二叉树

81 阅读 0 评论 54 点赞

我是靠谱客的博主无辜大雁，最近开发中收集的这篇文章主要介绍二叉树，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。
二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^{i-1}个结点；深度为k的二叉树至多有2^k-1 个结点。

满二叉树:一棵深度为k，且有2^k-1个节点称之为满二叉树。也就是除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
完全二叉树：深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应时，称之为完全二叉树
平衡二叉树:平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
二叉排序树：二叉排序树又叫二叉查找树或者二叉搜索树，它首先是一个二叉树，而且必须满足下面的条件：
若左子树不空，则左子树上所有结点的值均小于它的根节点的值；
若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
左、右子树也分别为二叉排序树；
没有键值相等的节点
二叉树性质
性质1：二叉树第i层上的结点数目最多为 2{i-1} (i≥1)
证明：下面用"数学归纳法"进行证明。
(01) 当i=1时，第i层的节点数目为2{i-1}=2{0}=1。因为第1层上只有一个根结点，所以命题成立。
(02) 假设当i>1，第i层的节点数目为2{i-1}。这个是根据(01)推断出来的！
下面根据这个假设，推断出"第(i+1)层的节点数目为2{i}“即可。
由于二叉树的每个结点至多有两个孩子，故"第(i+1)层上的结点数目” 最多是 “第i层的结点数目的2倍”。即，第(i+1)层上的结点数目最大值=2×2{i-1}=2{i}。
故假设成立，原命题得证！
性质2：深度为k的二叉树至多有2{k}-1个结点(k≥1)
证明：在具有相同深度的二叉树中，当每一层都含有最大结点数时，其树中结点数最多。利用"性质1"可知，深度为k的二叉树的结点数至多为：
20+21+…+2k-1=2k-1
故原命题得证！

性质3：包含n个结点的二叉树的高度至少为log2 (n+1)
证明：根据"性质2"可知，高度为h的二叉树最多有2{h}–1个结点。反之，对于包含n个节点的二叉树的高度至少为log2(n+1)。

性质4：在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1

证明：因为二叉树中所有结点的度数均不大于2，所以结点总数(记为n)=“0度结点数(n0)” + “1度结点数(n1)” + “2度结点数(n2)”。由此，得到等式一。
(等式一) n=n0+n1+n2
　另一方面，0度结点没有孩子，1度结点有一个孩子，2度结点有两个孩子，故二叉树中孩子结点总数是：n1+2n2。此外，只有根不是任何结点的孩子。故二叉树中的结点总数又可表示为等式二。
(等式二) n=n1+2n2+1
由(等式一)和(等式二)计算得到：n0=n2+1。原命题得证！

java构建二叉树以及前序遍历、中序遍历、后序遍历

package test;

import java.util.ArrayDeque;
import java.util.Queue;

public class BinaryTree {
	
	//根节点
	private Node root;
	
	/**
	 * 构建二叉排序树
	 * @param data
	 */
	public void insert(int data) {
		root = insert(root,data);
	}
	
	
	private Node insert(Node node, int data) {
		if(node==null) {
			node = new Node(data,null,null);
		}else {
			if(data>node.getData()) {
				node.setRightNode(insert(node.getRightNode(), data));
			}else {
				node.setLeftNode(insert(node.getLeftNode(), data));
			}
		}
		return node;
	}
	
	/**
	 * 先序遍历
	 * @param node
	 */
	public static void preOrderTraverse(Node node) {
		if(node!=null) {
			System.out.print(node.getData()+",");
			preOrderTraverse(node.getLeftNode());
			preOrderTraverse(node.getRightNode());
		}
	}
	
	/**
	 * 中序遍历
	 * @param node
	 */
	public static void inOrderTraverse(Node node) {
		if(node!=null) {
			preOrderTraverse(node.getLeftNode());
			System.out.print(node.getData()+",");
			preOrderTraverse(node.getRightNode());
		}
	}
	
	/**
	 * 后序遍历
	 * @param node
	 */
	public static void postOrderTraverse(Node node) {
		if(node!=null) {
			preOrderTraverse(node.getLeftNode());
			preOrderTraverse(node.getRightNode());
			System.out.print(node.getData()+",");
		}
	}
	
	/**
	 * 层次遍历
	 * @param node
	 */
	public static void LevelOrder(Node node) {
		Queue<Node> queue = new ArrayDeque<>();
		queue.add(node);
		while(!queue.isEmpty()) {
			Node poll = queue.poll();
			System.out.print(poll.getData()+",");
			if(poll.getLeftNode()!=null) queue.add(poll.getLeftNode());
			if(poll.getRightNode()!=null) queue.add(poll.getRightNode());
		}
	}
	
	/**
	 * 计算深度--递归，依次计算其左右子树的深度，选其大者
	 * @param node
	 * @return
	 */
	public static int deep(Node node){
		if(node==null) return 0;
		int leftDeep = 1,rightDeep = 1;
		if(node.getLeftNode()!=null)
			leftDeep += deep(node.getLeftNode());
		if(node.getRightNode()!=null)
			rightDeep += deep(node.getRightNode());
		return leftDeep>rightDeep?leftDeep:rightDeep;
	}
	
	public static void main(String[] args){
        BinaryTree tree = new BinaryTree();
        tree.insert(3);
        tree.insert(6);
        tree.insert(1);
        tree.insert(2);
        tree.insert(9);
        tree.insert(8);
        tree.insert(10);
        preOrderTraverse(tree.root);
        System.out.println();
        inOrderTraverse(tree.root);
        System.out.println();
        postOrderTraverse(tree.root);
        //层次遍历
        System.out.println();
        LevelOrder(tree.root);
        System.out.println();
        int deep = deep(tree.root);
        System.out.println("该二叉树的深度为："+deep);
    }


	/**
	 * 二叉树节点
	 */
	private static class Node{
		private int data;
		private Node leftNode;
		private Node rightNode;
		public Node(int data, Node leftNode, Node rightNode) {
			super();
			this.data = data;
			this.leftNode = leftNode;
			this.rightNode = rightNode;
		}
		public int getData() {
			return data;
		}
		public Node getLeftNode() {
			return leftNode;
		}
		public void setLeftNode(Node leftNode) {
			this.leftNode = leftNode;
		}
		public Node getRightNode() {
			return rightNode;
		}
		public void setRightNode(Node rightNode) {
			this.rightNode = rightNode;
		}
		
	}

}

参考：https://blog.csdn.net/liubenlong007/article/details/54972770
https://www.cnblogs.com/willwu/p/6007555.html