树的相关定义
- 定义的递归定义：树或者是一颗空树，即不包含任何结点，或是一颗非空树，即至少包含一个结点。在一颗非空树中，有且只有一个根结点，其余结点被分成m颗互不相交的子树，每棵子树又是一颗树。（根据定义可知树是一种递归的数据结构）
- 结点的度：每个结点具有的子树树或者说后继结点称为该结点的度。
- 树的度：树中所有结点的度的最大值称为该树的度。
- 分枝结点：度大于0的结点
- 叶子结点：度等于0的结点
- 树既是一种递归结构，也是一种层次结构。结点的层数从树根开始定义，根结点为第1层；树中所有结点的最大层数称为树的深度或高度
树的性质
- 树中的结点数等于所有结点的度数加1.
- 度为k的树中第i层上至多有k^(i-1)个结点（i>=1）
- 深度为h的k叉树至多有(k^h -1)/(k-1)
二叉树
- 定义：二叉树指树的度为2的有序树。二叉树或者是一颗空树，或者是一棵由一个根结点和两棵互不相交的分别称做根的左子树和右子树所组成的非空树。左右子树又分别是一颗二叉树。
- 性质
性质1:二叉树上终端结点数等于双分支结点数加1。
性质2:二叉树上第i层至多又2^（i-1）个结点。
性质3:深度为h的二叉树至多有2^h - 1个结点。
- 特殊二叉树
当第i层的结点数为2^（i-1）个时，则称此层的结点数是满的，当树中的每一层都满时，则称此树为满二叉树。在一颗二叉树中，若除最后一层外其余层都是满的，并且最后一层或者是满的或者是右边却是连续的若干结点，则称此树为完全二叉树
平衡二叉树：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
在一棵二叉树中，若除最后一层外，其余层都是满的，并且最后一层上的结点可以任意分布，则称此树为理想平衡二叉树，简称理想平衡树或理想二叉树
树的运算
先序、中序、后序、按层遍历、树的深度的递归和循环实现
/**
* 翻转一棵二叉树
*/
public TreeNode invertTree(TreeNode root) {
if(root == null) return null;
TreeNode left = root.left; //左树会改变，先保存一下
root.left = invertTree(root.right); //反转右子树，赋给根的左子树
root.right = invertTree(left);
return root;
}
/**
* 层次遍历 借助队列
*/
public List<Integer> levelTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if (root == null) return res;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while(!queue.isEmpty()) {
int count = queue.size(); //当前队列中存的数量是当前这一层的结点数量
for(int i=0; i<count; i++) {
TreeNode node = queue.poll(); //出队
res.add(node.value);
if(node.left != null)queue.add(node.left); //入队
if(node.right != null) queue.add(node.right);
}
}
return res;
}
/**
* 前序遍历 借助栈
*/
//递归实现
public List < Integer > preTraversal(TreeNode root) {
List < Integer > res = new ArrayList < > ();
prehelper(root, res);
return res;
}
private void prehelper(TreeNode root, List < Integer > res) {
if (root != null) {
res.add(root.value);
if (root.left != null) {
prehelper(root.left, res);
}
if (root.right != null) {
prehelper(root.right, res);
}
}
}
//非递归实现
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root); //先把根结点入栈
while(!stack.isEmpty()) { //栈非空说明还有层级未遍历
TreeNode node = stack.pop();
if(node == null)continue; //如果是空的跳过继续
ret.add(node.value);
stack.push(node.right); //入栈先右后左，保证左子树先遍历
stack.push(node.left);
}
return ret;
}
/**
* 中序遍历
*/
//递归实现
public List < Integer > inTraversal(TreeNode root) {
List < Integer > res = new ArrayList < > ();
inHelper(root, res);
return res;
}
private void inHelper(TreeNode root, List < Integer > res) {
if (root != null) {
if (root.left != null) {
inHelper(root.left, res);
}
res.add(root.value);
if (root.right != null) {
inHelper(root.right, res);
}
}
}
//非递归实现
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode cur = root;
while(cur !=null || !stack.isEmpty()) {
while(cur != null) { //循环把左子结点先入栈
stack.push(cur);
cur = cur.left;
}
TreeNode node = stack.pop(); //出栈最后入栈的左结点
ret.add(node.value);
cur = node.right;
}
return ret;
}
/**
* 后序遍历
*/
//递归实现
public List<Integer> postTraversal(TreeNode root){
List<Integer> res = new ArrayList<Integer>();
postHelper(root, res);
return res;
}
private void postHelper(TreeNode root, List<Integer> res){
if(root != null) {
if(root.left != null) {
postHelper(root.left, res);
}
if(root.right != null) {
postHelper(root.right, res);
}
res.add(root.value);
}
}
//非递归实现 前序遍历是 root -> left -> right, 后序遍历是left ->right ->root,把前序遍历算法的left和right换一下
//就是root -> right -> left，和后序遍历就完全相反了，所以后序遍历也可有前序遍历算法稍微改一下实现
public List<Integer> postOrderTraversal(TreeNode root){
List<Integer> res = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while(!stack.isEmpty()) {
TreeNode node = stack.pop();
if(node == null)continue;
res.add(node.value);
stack.push(node.left); //先后顺序和前序相反
stack.push(node.right);
}
Collections.reverse(res);
return res;
}
- 二叉搜索树（二叉排序树）
-
定义：二叉树搜索树又称二叉排序树，它或是一颗空树，或是一颗具有如下特性的非空二叉树：
（1）若它的左子树非空，则左子树上的所有结点的关键字均小于根结点的关键字；
（2）若它的右子树非空，则右子树上的所有结点的关键字均大于根结点的关键字；
（若允许具有相同的关键字结点存在，则大于等于）
（3）左右子树本身又各是一颗二叉搜索树。 -
根据二叉搜索树的定义，对二叉搜索树进行中叙遍历得到的结点序列必然是一个有序序列。
-
二叉搜索树的运算
（1）查找
//递归实现
boolean find(BTreeNode BST, ElemType item){
if(BST == null) { //空树返回失败
return false;
}else{
if(BST.data == item){ //找到
return true;
}else if(BST.data < item){ //比根结点大，往右子树递归查找
find(BST.right, item)
}else{ //比根结点小，往左子树递归查找
find(BST.left, item)
}
}
}
//非递归实现
boolean find(BTreeNode BST, ElemType item){
while(BST != null){
if(BST.data == item){ //找到
return true;
}else if(BST.data < item){
BST = BST.right;
}else{
BST = BST.left;
}
}
return false;
}
二叉搜索树查找过程中，给定值item和树中结点比较的次数最少为1次，最多为树的深度；时间复杂度最差情况（为单支树时）为O(n),一般情况为O(lbn),因此在二叉搜索树上查找比计划或线性表查找的时间复杂度O(n)好好很多，这正是构造二叉搜索树的优势。
（2）插入
//递归实现
void insert(BTreeNode BST, ElemType item){
if(BST == null){ //按照item元素生成的新结点链接到已找到的插入位置
BTreeNode p = new BTreeNode();
p.data = item;
p.left = null;
p.right = null;
BST = p;
}else if(item < BST.data){
insert(BST.left, item);
}else{
insert(BST.right, item);
}
}
//循环实现
void insert(BTreeNode BST, ElemType item)){
BTreeNode t = BST;//指向当前待比较的结点
BTreeNode parent = null; //指向t结点的双亲结点
while(t != null){
parent = t;
if(item < t.data){
t = t.left;
}else{
t = t.right;
}
}
//建立值为item，左右指针域为空的新结点
BTreeNode p = new BTreeNode();
p.data = item;
p.left = p.right = null;
//将新结点插入到二叉搜索树BST中
if(parent == null){
BST = p;
}else if(item < parent.data){
parent.left = p;
}else{
parent.right = p;
}
}
网友评论