本文共 4500 字,大约阅读时间需要 15 分钟。
emmmmmm复习一下二叉树的知识
一、树的定义
树是一种数据结构,它是由n(n>=1)个有限结点组成一个具有层次关系的集合。
树具有的特点有:
(1)每个结点有零个或多个子结点
(2)没有父节点的结点称为根节点
(3)每一个非根结点有且只有一个父节点
(4)除了根结点外,每个子结点可以分为多个不相交的子树。
树的基本术语有:
若一个结点有子树,那么该结点称为子树根的“双亲”,子树的根称为该结点的“孩子”。有相同双亲的结点互为“兄弟”。一个结点的所有子树上的任何结点都是该结点的后裔。从根结点到某个结点的路径上的所有结点都是该结点的祖先。
结点的度:结点拥有的子树的数目
叶子结点:度为0的结点
分支结点:度不为0的结点
树的度:树中结点的最大的度
层次:根结点的层次为1,其余结点的层次等于该结点的双亲结点的层次加1
树的高度:树中结点的最大层次
森林:0个或多个不相交的树组成。对森林加上一个根,森林即成为树;删去根,树即成为森林。
这些都是书上的基本概念
二、二叉树
1、二叉树的定义
二叉树是每个结点最多有两个子树的树结构。
五种基本形态:二叉树可以是空集;根可以有空的左子树或右子树;或者左、右子树皆为空。
2、二叉树的性质
三、满二叉树、完全二叉树和二叉查找树
1、满二叉树
定义:高度为h,并且由2h-1个结点组成的二叉树,称为满二叉树
2、完全二叉树定义:一棵二叉树中,只有最下面两层结点的度可以小于2,并且最下层的叶结点集中在靠左的若干位置上,这样的二叉树称为完全二叉树。
特点:叶子结点只能出现在最下层和次下层,且最下层的叶子结点集中在树的左部。显然,一棵满二叉树必定是一棵完全二叉树,而完全二叉树未必是满二叉树。
3、二叉查找树
定义:二叉查找树又被称为二叉搜索树。设x为二叉查找树中的一个结点,x结点包含关键字key,结点x的key值计为key[x]。如果y是x的左子树中的一个结点,则key[y]<=key[x];如果y是x的右子树的一个结点,则key[y]>=key[x]
二叉查找树的基本性质:Node:
package priv.qcy.tree;public class Node { public int value;// 数据域 public Node left, right; public Node(Node left, Node right, int value) { super(); this.value = value; this.left = left; this.right = right; } public Node() { } public Node(int value) { this(null, null, value); } public int getValue() { return value; } public void setValue(int value) { this.value = value; } 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; }}
BinarySortTree:
package priv.qcy.tree;import java.util.Stack;public class BinarySortTree { private Node root = null; /** 查找二叉排序树中是否有key值 */ public boolean searchBST(int key) { Node pNode = root; while (pNode != null) { if (key == pNode.getValue()) { return true; } else if (key < pNode.getValue()) { pNode = pNode.getLeft(); } else { pNode = pNode.getRight(); } } return false; } /** 向二叉排序树中插入结点 */ public void insertBST(int key) { Node pNode = root; Node prev = null; while (pNode != null) { prev = pNode; if (key < pNode.getValue()) { pNode = pNode.getLeft(); } else if (key > pNode.getValue()) { pNode = pNode.getRight(); } else { return; } } if (root == null) { root = new Node(key); } else if (key < prev.getValue()) { prev.setLeft(new Node(key)); } else { prev.setRight(new Node(key)); } } /** * 删除二叉排序树中的结点 分为三种情况:(删除结点为*p ,其父结点为*f) (1)要删除的*p结点是叶子结点,只需要修改它的双亲结点的指针为空 * (2)若*p只有左子树或者只有右子树,直接让左子树/右子树代替*p (3)若*p既有左子树,又有右子树 * 用p左子树中最大的那个值(即最右端S)代替P,删除s,重接其左子树 */ public void deleteBST(int key) { deleteBST(root, key); } private boolean deleteBST(Node node, int key) { if (node == null) return false; else { if (key == node.getValue()) { return delete(node); } else if (key < node.getValue()) { return deleteBST(node.getLeft(), key); } else { return deleteBST(node.getRight(), key); } } } private boolean delete(Node node) { Node temp = null; /** * 右子树空,只需要重接它的左子树 如果是叶子结点,在这里也把叶子结点删除了 */ if (node.getRight() == null) { temp = node; node = node.getLeft(); } /** 左子树空, 重接它的右子树 */ else if (node.getLeft() == null) { temp = node; node = node.getRight(); } /** 左右子树均不为空 */ else { temp = node; Node s = node; /** 转向左子树,然后向右走到“尽头” */ s = s.getLeft(); while (s.getRight() != null) { temp = s; s = s.getRight(); } node.setValue(s.getValue()); if (temp != node) { temp.setRight(s.getLeft()); } else { temp.setLeft(s.getLeft()); } } return true; } /** * 中序非递归遍历二叉树 获得有序序列 */ public void dlrTraverse() { Stackstack = new Stack (); Node node = root; while (node != null || !stack.isEmpty()) { while (node != null) { stack.push(node); node = node.getLeft(); } node = stack.pop(); System.out.print(node.getValue() + " "); node = node.getRight(); } System.out.println(); } public static void main(String[] args) { BinarySortTree bst = new BinarySortTree(); /** 构建的二叉树没有相同元素 */ int[] num = { 45, 12, 37, 24, 3, 53, 100, 61, 55, 90, 78 }; for (int i = 0; i < num.length; i++) { bst.insertBST(num[i]); } bst.dlrTraverse(); System.out.println(bst.searchBST(37)); System.out.println("-------------------------------"); bst.deleteBST(12); bst.dlrTraverse(); System.out.println(bst.searchBST(12)); }}
作为个人学习复习记录,方便复习!!
转载地址:http://jinwi.baihongyu.com/