赞
踩
1.树的定义
树是一类重要的非线性数据结构,是以分支关系定义的层次结构。每个结点有零个或多个子结点;没有父结点的结点称为根结点;每一个非根结点有且只有一个父结点;除了根结点外,每个子结点可以分为多个不相交的子树
2.相关概念
节点的度:一个节点含有的子树的个数称为该节点的度; 如上图:A的为6
叶节点或终端节点:度为0的节点称为叶节点; 如上图:B、C、H、I…等节点为叶节点
父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点; 如上图:A是B的父节点
孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点; 如上图:B是A的孩子节点
树的度:一棵树中,最大的节点的度称为树的度; 如上图:树的度为6
树的高度或深度:树中节点的最大层次; 如上图:树的高度为4
森林:由m(m>=0)棵互不相交的树的集合称为森林;
3.二叉树的基本概念
二叉树是结点的一个有限集合,该集合最多有两个节点,同时左子树和右子树的顺序不能乱。
4.完全二叉树、满二叉树
满二叉树:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K,且结点总数是(2^k) -1 ,则它就是满二叉树。
完全二叉树:完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。
若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数(即1~h-1层为一个满二叉树),第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。
5.二叉树的遍历
前序遍历(前根遍历):根——>左——>右
中序遍历(中根遍历):左——>根——>右
后序遍历(后根遍历):左——>右——>根
层序遍历:从根开始,逐层,从左到右遍历。
前中后是根据遍历时根所在的相对位置来命名。
6.代码实现以下二叉树及其遍历等相关操作(递归):
import java.util.LinkedList; class Node{//定义一个节点,包含自身数据,对左子树的引用,右子树的引用。 String val; Node left; Node right; public Node(String val){ this.val = val; } } public class Mytree { public static Node Tree(){ //初始化二叉树,并且手动连接 Node a = new Node("A"); Node b = new Node("B"); Node c = new Node("C"); Node d = new Node("D"); Node e = new Node("E"); Node f = new Node("F"); Node g = new Node("G"); Node h = new Node("H"); a.left = b; a.right = c; b.left = d; b.right = e; e.left = g; g.right = h; c.right = f; return a; } public static void PreOrder(Node root){ //先序遍历 if (root == null) { return; } System.out.print(root.val+" "); PreOrder(root.left); PreOrder(root.right); } public static void MidOrder(Node root){//中序遍历 if (root == null) { return; } MidOrder(root.left); System.out.print(root.val+" "); MidOrder(root.right); } public static void LastOrder(Node root){//后序遍历 if (root == null) { return; } LastOrder(root.left); LastOrder(root.right); System.out.print(root.val+" "); } public static void LevalOrder(Node root){ //层序遍历 LinkedList<Node> list = new LinkedList<>(); //定义一个链表保存遍历到的数字 if(root == null)return; //如果为空则返回 list.add(root);//不为空,将根加入链表 while (list.isEmpty() == false ) {//链表不为空的时候,循环输出链表中的元素,并且继续遍历,直到遍历结束 Node tem = list.poll(); System.out.print(tem.val+" "); if(tem.left != null){ list.add(tem.left); } if(tem.right != null){ list.add(tem.right); } } } public static int Size(Node root){ //计算链表节点个数 if(root == null)return 0; int tem = 0; tem = 1+Size(root.left)+Size(root.right); return tem; } public static int LeafNode(Node root){//计算叶子节点个数 if(root == null)return 0; if(root.left == null && root.right == null)return 1; return LeafNode(root.left)+ LeafNode(root.right); } public static int LvelSize(Node root,int k){ //计算第K层节点个数 if(k < 1 || root == null)return 0; if(k == 1)return 1; return LvelSize(root.left,k-1)+LvelSize(root.right,k-1); } public static Node Find(Node root,String a){//查找指定节点值 if(root == null)return null; if(root.val.equals(a))return root; Node result = Find(root.left,a); if(result != null) return result; else return Find(root.right,a); } public static void main(String[] args) { //测试函数 Node root = Tree(); System.out.print("先序遍历:");PreOrder(root); System.out.println(""); System.out.print("中序遍历:");MidOrder(root); System.out.println(""); System.out.print("后序遍历:");LastOrder(root); System.out.println(""); System.out.print("层序遍历:");LevalOrder(root); System.out.println(""); System.out.print("节点个数为:");System.out.print(Size(root)); System.out.println(""); System.out.print("叶子节点个数为:");System.out.print(LeafNode(root)); System.out.println(""); System.out.print("K层节点个数为:");System.out.print(LvelSize(root,3)); System.out.println(""); System.out.print("该值对应节点为:");System.out.print(Find(root,"F")); System.out.println(""); } }
运行结果:
先序遍历:A B D E G H C F
中序遍历:D B G H E A C F
后序遍历:D H G E B F C A
层序遍历:A B C D E F G H
节点个数为:8
叶子节点个数为:3
K层节点个数为:3
该值对应节点为:Node@4554617c
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。