数据结构与算法(树)

数据结构与算法(树)

首语

  • 树(Tree)是n(n≥0)个结点的有限集。n=0时称为空树。在任意一颗非空树中:(1)有且仅有一个特定的称为根(Root)的结点;(2)当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1、T2、........Tm,其中每一个集合本身又是一棵树,并且称为根的子树(SubTree)。
    树

结点的度

  • 结点拥有的子树数称为结点的度。度为0的节点称为叶子结点或终端结点,度不为0的结点称为非终端结点或分支结点。除根结点以外,分支结点也称为内部结点。树的度是树内各节点的度的最大值。

层次与深度

  • 结点的层次(Level)从根开始定义起,根为第一层,根的孩子为第二层。若某结点在第一层,则其子树的根就在l+1层。其双亲在同一层的结点互为堂兄弟。显然图中的D、E、F是堂兄弟,而G、H、I、J也是。树中结点的最大层次称为树的深度(Depth)或高度,当前树的深度为4。

有序与无序树

  • 如果将树中结点的各子树看成从左至右是有次序的,不能互换的,则称该树为有序树,否则称为无序树。

森林

  • 森林(Forest)是m(m≥0)棵互不相交的树的集合。

树的存储结构

  • 简单的顺序存储不能满足树的实现。
  • 结合顺序存储和链式存储来实现。

三种表示方法

1、双亲表示法

  • 在每个结点中,附设一个指示器指示其双亲结点到链表中的位置。

2、孩子表示法

  • 方案一
  • 方案二
  • 最终方案
           把每个结点的孩子结点排列起来,以单链表作为存储结构,则n个结点有n个孩子链表,如果是叶子结点则此单链表为空,然后n个头指针又组成一个线性表,采用顺序存储结构,存放在一个一维数组中。

3、孩子兄弟表示法

  • 任意一棵树,它的结点的第一个孩子如果存在就是唯一的,它的右兄弟如果存在也是唯一的。因此,我们设置两个指针,分别指向该结点的第一个孩子和此结点的右兄弟。

二叉树

  • 二叉树(Binary Tree)是n(n≥0)个结点的有限集合,该集合或者为空集(称为二叉树),或者由一个根节点和两颗互不相交的、分别称为根节点的左子树和右子树的二叉树组成。

斜树(特殊二叉树)

  • 所有的结点都只有左子树的叫做左斜树。所有结点都是右子树的二叉树叫右斜树。这两者统称为斜树。
    在这里插入图片描述

满二叉树

  • 在一颗二叉树中,如果所有分支结点都存在左子树和右子树,并且所有叶子都在同一层上,这样的二叉树称为满二叉树。

完全二叉树

  • 对一颗具有n个结点的二叉树按层序编号,如果编号为i(1≤i≤n)的结点与同样深度的满二叉树找那个编号为i的结点在二叉树中位置相同,则这棵二叉树称为完全二叉树。

二叉树的性质

  • 性质1:在二叉树的第i层上至多有2的i-1次方个结点(i≥1)。
  • 性质2:深度为k的二叉树至多有2的k-1次方个结点(k≥1)。
  • 性质3:对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点为n2,则n0=n2+1。
    证明: 设n为总结点数,n1为度为1的结点树,n2位度为2 的结点树,n0为终端结点树。
               n=n0+n1+n2,而分支线总数=n-1=n1+2n2。
              推出n0+n1+n2-1=n1+2
    n2。即n0=n2+1。
  • 性质4:具有n个结点的完全二叉树深度[㏒2ⁿ]+1([x]表示不大于x的最大整数)。
  • 性质5:如果对一颗有n个结点的完全二叉树(其深度为[㏒2ⁿ]+1)的结点按层序编号(从第1层到第
    [㏒2ⁿ]+1层,每层从左到右),对任意一个结点i(1≤i≤n)有:
    1、如果i=1,则结点i是二叉树的根,无双亲;如果i>1,则其双亲是结点[i/2].
    2、如果2i>n,则结点i无左孩子(结点i为叶子结点);否则其左孩子是结点2i。
    3、如果2i+1>n,则结点i无右孩子;否则其右孩子是结点2i+1。

顺序存储

  • 完全二叉树

  • 一般二叉树

二叉链表

  • lchild—>data—>rchild

二叉树的遍历

  • 前序遍历(根左右)
           规则是若二叉树为空,则空操作返回,否则先访问跟结点,然后前序遍历左子树,再前序遍历右子树。
  • 中序遍历(左根右)
           规则是若树为空,则空操作返回,否则从根结点开始(注意并不是先访问根结点),中序遍历根结点的左子树,然后是访问根结点,最后中序遍历右子树。
  • 后序遍历(左右根)
           规则是若树为空,则空操作返回,否则从左到右先叶子后结点的方式遍历访问左右子树,最后是访问根结点。
    在这里插入图片描述
  • 层序遍历
           规则是若树为空,则空操作返回,否则从树的第-一层,也就是根结点开始访问,从上而下逐层遍历,在同一层,按从左到右的顺序对结点逐个访问。

代码实现

  • 构建二叉树
private TreeNode  root = null;
	
	public BinaryTree(){
		root = new TreeNode(1, "A");
	}
/**
	 * 构建二叉树
	 *         A
	 *     B       C
	 * D      E        F
	 */
	public void createBinaryTree(){
		TreeNode nodeB = new TreeNode(2, "B");
		TreeNode nodeC = new TreeNode(3, "C");
		TreeNode nodeD = new TreeNode(4, "D");
		TreeNode nodeE = new TreeNode(5, "E");
		TreeNode nodeF = new TreeNode(6, "F");
		root.leftChild = nodeB;
		root.rightChild = nodeC;
		nodeB.leftChild = nodeD;
		nodeB.rightChild = nodeE;
		nodeC.rightChild = nodeF;
	}
	public class TreeNode{
		private int index;
		private String data;
		private TreeNode leftChild;
		private TreeNode rightChild;
		
		public TreeNode(int index,String data){
			this.index = index;
			this.data = data;
			this.leftChild = null;
			this.rightChild = null;
		}
	}
  • 求二叉树的高度
/**
	 * 求二叉树的高度
	 * @author yhj
	 *
	 */
	public int getHeight(){
		return getHeight(root);
	}
	
	private int getHeight(TreeNode node) {
		if(node == null){
			return 0;
		}else{
			int i = getHeight(node.leftChild);
			int j = getHeight(node.rightChild);
			return (i<j)?j+1:i+1;
		}
	}
  • 获取二叉树的结点树
/**
	 * 获取二叉树的结点数
	 * @author yhj
	 *
	 */
	public int getSize(){
		return getSize(root);
	}
	
	
	private int getSize(TreeNode node) {
		if(node == null){
			return 0;
		}else{
			return 1+getSize(node.leftChild)+getSize(node.rightChild);
		}
	}
  • 前序遍历(迭代与非迭代)
/**
	 * 前序遍历――迭代
	 * @author yhj
	 *
	 */
	public void preOrder(TreeNode node){
		if(node == null){
			return;
		}else{
			System.out.println("preOrder data:"+node.getData());
			preOrder(node.leftChild);
			preOrder(node.rightChild);
		}
	}
	
	/**
	 * 前序遍历――非迭代
	 */
	
	public void nonRecOrder(TreeNode node){
		if(node == null){
			return;
		}
		Stack<TreeNode> stack = new Stack<TreeNode>();
		stack.push(node);
		while(!stack.isEmpty()){
			//出栈和进栈
			TreeNode n = stack.pop();//弹出根结点
			//压入子结点
			System.out.println("nonRecOrder data"+n.getData());
			if(n.rightChild!=null){
				stack.push(n.rightChild);
				
			}
			if(n.leftChild!=null){
				stack.push(n.leftChild);
			}
		}
	}
  • 中序遍历
/**
	 * 中序遍历――迭代
	 * @author yhj
	 *
	 */
	public void midOrder(TreeNode node){
		if(node == null){
			return;
		}else{
			midOrder(node.leftChild);
			System.out.println("midOrder data:"+node.getData());
			midOrder(node.rightChild);
		}
	}
  • 后序遍历
/**
	 * 后序遍历――迭代
	 * @author yhj
	 *
	 */
	public void postOrder(TreeNode node){
		if(node == null){
			return;
		}else{
			postOrder(node.leftChild);
			postOrder(node.rightChild);
			System.out.println("postOrder data:"+node.getData());
		}
	}

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://www.yanghujun.com/archives/数据结构与算法树

Buy me a cup of coffee ☕.