devbox
Gausst松鼠会
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Java数据结构-树_java树结构

作者：Gausst松鼠会 | 2024-04-20 12:02:55

赞

踩

java树结构

目录

一、简介

树是我们计算机中非常重要的一种数据结构，同时使用树这种数据结构，可以描述现实生活中的很多事物，例如家谱、单位的组织架构、等等。
树是由n（n>=1）个有限结点组成一个具有层次关系的集合。把它叫做“树”，是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

在这里插入图片描述

树具有以下特点：

  1. 每个结点有零个或多个子结点；
  2. 没有父结点的结点为根结点；
  3. 每一个非根结点只有一个父结点；
  4. 每个结点及其后代结点整体上可以看做是一棵树，称为当前结点的父结点的一个子树；

二、相关术语

结点的度：
一个结点含有的子树的个数称为该结点的度；
叶结点：
度为0的结点称为叶结点，也可以叫做终端结点
分支结点：
度不为0的结点称为分支结点，也可以叫做非终端结点
结点的层次：
从根结点开始，根结点的层次为1，根的直接后继层次为2，以此类推
结点的层序编号：
将树中的结点，按照从上层到下层，同层从左到右的次序排成一个线性序列，把他们编成连续的自然数。
树的度：
树中所有结点的度的最大值
树的高度(深度)：
树中结点的最大层次
森林：
m（m>=0）个互不相交的树的集合，将一颗非空树的根结点删去，树就变成一个森林；给森林增加一个统一的根结点，森林就变成一棵树
孩子结点：
一个结点的直接后继结点称为该结点的孩子结点
双亲结点(父结点)：
一个结点的直接前驱称为该结点的双亲结点
兄弟结点：
同一双亲结点的孩子结点间互称兄弟结点

三、二叉树

1. 相关概念

二叉树就是度不超过2的树(每个结点最多有两个子结点)

在这里插入图片描述

2. 特殊二叉树

（1）满二叉树

一个二叉树，如果每一个层的结点树都达到最大值，则这个二叉树就是满二叉树。满二叉树的叶子结点都集中在二叉树的最下一层，并且除叶子结点之外的每个结点度数均为 2。

在这里插入图片描述

（2）完全二叉树

叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。
在这里插入图片描述

（3）二叉排序树

左子树上所有结点的关键字均小于根结点的关键字;右子树上的所有结点的关键字均大于根结点的关键字;左子树和右子树又各是一棵二叉排序树。

（4）平衡二叉树

树上任一结点的左子树和右子树的深度之差不超过1。

3. 二叉查找树的创建

二叉查找树是二叉树中一种常用的一种类型。二叉查找树是为了实现快速查找产生的。不过，它不仅支持快速查找，还支持快速插入和删除。这主要归功于二叉查找树的一个特性，那就是树中任一节点，这个节点的左子树的值总是小于这个节点的值，这个节点右子树的值总是大于这个节点的值。
在这里插入图片描述

二叉查找树API设计

在这里插入图片描述

（1）二叉树的结点类

根据对图的观察，我们发现二叉树其实就是由一个一个的结点及其之间的关系组成的，按照面向对象的思想，我们设计一个结点类来描述结点这个事物。

private class Node {
	// 存储键
	public Key key;
	// 存储值
	private Value value;
	// 记录左子结点
	public Node left;
	// 记录右子结点
	public Node right;
	
	public Node(Key key, Value value, Node left, Node right) {
		this.key = key;
		this.value = value;
		this.left = left;
		this.right = right;
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

（2）二叉查找树插入实现

插入方法put实现思想：

  1. 如果当前树中没有任何一个结点，则直接把新结点当做根结点使用
  2. 如果当前树不为空，则从根结点开始：
  • 如果新结点的key小于当前结点的key，则继续找当前结点的左子结点；
  • 如果新结点的key大于当前结点的key，则继续找当前结点的右子结点；
  • 如果新结点的key等于当前结点的key，则树中已经存在这样的结点，替换该结点的value值即可。
// 向树中添加元素 key-value
public void put(Key key, Value value) {
	root = put(root, key, value);
}

// 向指定的树x中添加key-value,并返回添加元素后新的树
private Node put(Node x, Key key, Value value) {
	//如果 x 子树为空，
	if (x == null){
		N++;
		return new Node(key,value, null,null);
	}
	// 如果x子树不为空
	// 比较x结点的键和key的大小：
	int cmp = key.compareTo(x.key);
	if (cmp > 0){
		//如果key大于x结点的键，则继续找x结点的右子树
		x.right = put(x.right,key,value);
	}else if(cmp < 0){
		// 如果key小于x结点的键，则继续找x结点的左子树
		x.left = put(x.left,key,value);
	}else{
		// 如果key等于x结点的键，则替换x结点的值为value即可
		x.value = value;
	}
	return x;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27

（3）二叉查找树查询实现

查询方法get实现思想：
从根节点开始：

  1. 如果要查询的key小于当前结点的key，则继续找当前结点的左子结点；
  2. 如果要查询的key大于当前结点的key，则继续找当前结点的右子结点；
  3. 如果要查询的key等于当前结点的key，则树中返回当前结点的value。
// 查询树中指定key对应的value
public Value get(Key key) {
	return get(root,key);
}

// 从指定的树x中，查找key对应的值
public Value get(Node x, Key key) {
	// x树为null
	if (x == null){
		return null;
	}
	// x树不为null
	// 比较key和x结点的键的大小
	int cmp = key.compareTo(x.key);
	if (cmp > 0){
		// 如果key大于x结点的键，则继续找x结点的右子树
		return get(x.right,key);
	}else if(cmp < 0){
		// 如果key小于x结点的键，则继续找x结点的左子树
		return get(x.left,key);
	}else{
		// 如果key等于x结点的键，就找到了键为key的结点，只需要返回x结点的值即可
		return x.value;
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25

（4）二叉查找树删除实现

删除方法delete实现思想：

  1. 找到被删除结点；
  2. 找到被删除结点右子树中的最小结点minNode
  3. 删除右子树中的最小结点
  4. 让被删除结点的左子树称为最小结点minNode的左子树，让被删除结点的右子树称为最小结点minNode的右子 树
  5. 让被删除结点的父节点指向最小结点minNode
// 删除树中key对应的value
public void delete(Key key) {
	root = delete(root, key);
}

// 删除指定树x中的key对应的value，并返回删除后的新树
public Node delete(Node x, Key key) {
	// x树为null
	if (x == null){
		return null;
	}
	// x树不为null
	int cmp = key.compareTo(x.key);
	if (cmp > 0){
		// 如果key大于x结点的键，则继续找x结点的右子树
		x.right = delete(x.right,key);
	}else if(cmp < 0){
		// 如果key小于x结点的键，则继续找x结点的左子树
		x.left = delete(x.left,key);
	}else{
		// 如果key等于x结点的键，完成真正的删除结点动作，要删除的结点就是x；
		// 让元素个数-1
		N --;
		// 得找到右子树中最小的结点
		if (x.right == null){
			return x.left;
		}
		if (x.left == null){
			return x.right;
		}
		Node minNode = x.right;
		Node curNode = x.right;
		// 若右结点无左结点，则它就为替换删除结点的结点
		if (curNode.left == null){
			minNode.left = x.left;
		}else{
			// 找到右子树中最小的结点
			while (curNode.left != null){
				if (curNode.left.left == null){
					// 找到最小结点
					minNode = curNode.left;
					// 断开此最小结点
					curNode.left = null;
					break;
				}
				curNode = curNode.left;
			}
			// 让x结点的左子树成为minNode的左子树
			minNode.left = x.left;
			// 让x结点的右子树成为minNode的右子树
			minNode.right = x.right;
		}
		// 让x结点的父结点指向minNode
		x = minNode;
	}
	return x;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57

完整代码

public class BinaryTree<Key extends Comparable<Key>, Value> {

    // 记录根结点
    private Node root;
    // 记录树中元素的个数
    private int N;

    private class Node {
        // 存储键
        public Key key;
        // 存储值
        private Value value;
        // 记录左子结点
        public Node left;
        // 记录右子结点
        public Node right;

        public Node(Key key, Value value, Node left, Node right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    // 获取树中元素的个数
    public int size() {
        return N;
    }

    // 向树中添加元素 key-value
    public void put(Key key, Value value) {
        root = put(root, key, value);
    }

    // 向指定的树x中添加key-value,并返回添加元素后新的树
    private Node put(Node x, Key key, Value value) {
        //如果 x 子树为空，
        if (x == null){
            N ++;
            return new Node(key,value, null,null);
        }
        // 如果x子树不为空
        // 比较x结点的键和key的大小：
        int cmp = key.compareTo(x.key);
        if (cmp > 0){
            //如果key大于x结点的键，则继续找x结点的右子树
            x.right = put(x.right,key,value);
        }else if(cmp < 0){
            // 如果key小于x结点的键，则继续找x结点的左子树
            x.left = put(x.left,key,value);
        }else{
            // 如果key等于x结点的键，则替换x结点的值为value即可
            x.value = value;
        }
        return x;
    }

    // 查询树中指定key对应的value
    public Value get(Key key) {
        return get(root,key);
    }

    // 从指定的树x中，查找key对应的值
    public Value get(Node x, Key key) {
        // x树为null
        if (x == null){
            return null;
        }
        // x树不为null
        // 比较key和x结点的键的大小
        int cmp = key.compareTo(x.key);
        if (cmp > 0){
            // 如果key大于x结点的键，则继续找x结点的右子树
            return get(x.right,key);
        }else if(cmp < 0){
            // 如果key小于x结点的键，则继续找x结点的左子树
            return get(x.left,key);
        }else{
            // 如果key等于x结点的键，就找到了键为key的结点，只需要返回x结点的值即可
            return x.value;
        }
    }


    // 删除树中key对应的value
    public void delete(Key key) {
        root = delete(root, key);
    }

	// 删除指定树x中的key对应的value，并返回删除后的新树
	public Node delete(Node x, Key key) {
		// x树为null
		if (x == null){
			return null;
		}
		// x树不为null
		int cmp = key.compareTo(x.key);
		if (cmp > 0){
			// 如果key大于x结点的键，则继续找x结点的右子树
			x.right = delete(x.right,key);
		}else if(cmp < 0){
			// 如果key小于x结点的键，则继续找x结点的左子树
			x.left = delete(x.left,key);
		}else{
			// 如果key等于x结点的键，完成真正的删除结点动作，要删除的结点就是x；
			// 让元素个数-1
			N --;
			// 得找到右子树中最小的结点
			if (x.right == null){
				return x.left;
			}
			if (x.left == null){
				return x.right;
			}
			Node minNode = x.right;
			Node curNode = x.right;
			// 若右结点无左结点，则它就为替换删除结点的结点
			if (curNode.left == null){
				minNode.left = x.left;
			}else{
				// 找到右子树中最小的结点
				while (curNode.left != null){
					if (curNode.left.left == null){
						// 找到最小结点
						minNode = curNode.left;
						// 断开此最小结点
						curNode.left = null;
						break;
					}
					curNode = curNode.left;
				}
				// 让x结点的左子树成为minNode的左子树
				minNode.left = x.left;
				// 让x结点的右子树成为minNode的右子树
				minNode.right = x.right;
			}
			// 让x结点的父结点指向minNode
			x = minNode;
		}
		return x;
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143

4. 二叉树的遍历

很多情况下，我们可能需要像遍历数组数组一样，遍历树，从而拿出树中存储的每一个元素，由于树状结构和线性结构不一样，它没有办法从头开始依次向后遍历，所以存在如何遍历，也就是按照什么样的搜索路径进行遍历的问题。
在这里插入图片描述
我们把树简单的画作上图中的样子，由一个根节点、一个左子树、一个右子树组成，那么按照根节点什么时候被访问，我们可以把二叉树的遍历分为以下三种方式：
1. 前序遍历；
先访问根结点，然后再访问左子树，最后访问右子树
2. 中序遍历；
先访问左子树，中间访问根节点，最后访问右子树
3. 后序遍历；
先访问左子树，再访问右子树，最后访问根节点

如果我们分别对下面的树使用三种遍历方式进行遍历，得到的结果如下：
在这里插入图片描述

（1）前序遍历

我们在（3）中创建的树上，添加前序遍历的API：

  • public Deque<Key> preErgodic()：使用前序遍历，获取整个树中的所有键
  • private void preErgodic(Node x, Deque<Key> keys)：使用前序遍历，把指定树x中的所有键放入到keys队列中

实现过程中，我们通过前序遍历，把,把每个结点的键取出，放入到队列中返回即可。

实现步骤：

  1. 把当前结点的key放入到队列中
  2. 找到当前结点的左子树，如果不为空，递归遍历左子树
  3. 找到当前结点的右子树，如果不为空，递归遍历右子树
// 获取整个树中所有的键 -- 前序遍历
public Deque<Key> preErgodic(){
	Deque<Key> keys = new LinkedList<>();
	preErgodic(root, keys);
	return keys;
}

// 获取指定树x的所有键，并放到 keys 队列中
private void preErgodic(Node x, Deque<Key> keys){
	if (x == null){
		return;
	}
	// 把x结点的key放入到 队列
	keys.add(x.key);
	// 递归遍历x结点的左子树
	if (x.left != null){
		preErgodic(x.left,keys);
	}
	// 递归遍历x结点的右子树
	if (x.right!=null){
		preErgodic(x.right,keys);
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

（2）中序遍历

我们在（3）中创建的树上，添加中序遍历的API：

  • public Deque<Key> midErgodic()：使用中序遍历，获取整个树中的所有键
  • private void midErgodic(Node x, Deque<Key> keys)：使用中序遍历，把指定树x中的所有键放入到keys队列中

实现步骤：

  1. 找到当前结点的左子树，如果不为空，递归遍历左子树
  2. 把当前结点的key放入到队列中
  3. 找到当前结点的右子树，如果不为空，递归遍历右子树
// 使用中序遍历获取树中所有的键
public Deque<Key> midErgodic(){
	Deque<Key> keys = new LinkedList<>();
	midErgodic(root,keys);
	return keys;
}

// 使用中序遍历，获取指定树x中所有的键，并存放到key中
private void midErgodic(Node x,Deque<Key> keys){
	if (x==null){
		return;
	}
	// 先递归，把左子树中的键放到keys中
	if (x.left != null){
		midErgodic(x.left, keys);
	}
	// 把当前结点x的键放到keys中
	keys.add(x.key);
	// 在递归，把右子树中的键放到keys中
	if(x.right != null){
		midErgodic(x.right, keys);
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

（3）后序遍历

我们在（3）中创建的树上，添加后序遍历的API：

public Deque<Key> afterErgodic()：使用后序遍历，获取整个树中的所有键 private void afterErgodic(Node x, Deque<Key> keys)：使用后序遍历，把指定树x中的所有键放入到keys队列中

实现步骤：

  1. 找到当前结点的左子树，如果不为空，递归遍历左子树
  2. 找到当前结点的右子树，如果不为空，递归遍历右子树
  3. 把当前结点的key放入到队列中;
// 使用后序遍历，把整个树中所有的键返回
public Deque<Key> afterErgodic(){
	Deque<Key> keys = new LinkedList<>();
	afterErgodic(root,keys);
	return keys;
}

// 使用后序遍历，把指定树x中所有的键放入到keys中
private void afterErgodic(Node x,Deque<Key> keys){
	if (x == null){
		return ;
	}
	// 通过递归把左子树中所有的键放入到keys中
	if (x.left != null){
		afterErgodic(x.left, keys);
	}
	// 通过递归把右子树中所有的键放入到keys中
	if (x.right != null){
		afterErgodic(x.right, keys);
	}
	// 把x结点的键放入到keys中
	keys.add(x.key);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

（4）层次遍历

所谓的层序遍历，就是从根节点（第一层）开始，依次向下，获取每一层所有结点的值，有二叉树如下：
在这里插入图片描述

那么层序遍历的结果是：EBGADFHC
我们在（3）中创建的树上，添加层序遍历的API：

  • public Deque<Key> layerErgodic()：使用层序遍历，获取整个树中的所有键
// 使用层序遍历，获取整个树中所有的键
public Deque<Key> layerErgodic(){

	// 定义两个队列，分别存储树中的键和树中的结点
	Deque<Key> keys = new LinkedList<>();
	Deque<Node> nodes = new LinkedList<>();
	// 默认，往队列中放入根结点
	nodes.add(root);
	
	while(!nodes.isEmpty()){
		// 从队列中弹出一个结点，把key放入到keys中
		Node n = nodes.poll();
		keys.add(n.key);
		// 判断当前结点还有没有左子结点，如果有，则放入到nodes中
		if (n.left != null){
			nodes.add(n.left);
		}
		// 判断当前结点还有没有右子结点，如果有，则放入到nodes中
		if (n.right != null){
			nodes.add(n.right);
		}
	}
	return keys;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

5. 最大深度问题

给定一棵树，请计算树的最大深度（树的根节点到最远叶子结点的最长路径上的结点数）
在这里插入图片描述

上面这棵树的最大深度为4。

我们在（3）中创建的树上，添加如下的API求最大深度：

  • public int maxDepth()：计算整个树的最大深度
  • private int maxDepth(Node x):计算指定树x的最大深度
//获取整个树的最大深度
public int maxDepth(){
	return maxDepth(root);
}

//获取指定树x的最大深度
private int maxDepth(Node x){
	if (x == null){
		return 0;
	}
	// 比较左子树最大深度和右子树最大深度，取较大值+1即可
	return Math.max(maxDepth(x.left), maxDepth(x.right)) + 1;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

6. 折纸问题

请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。此时 折痕是凹下去的，即折痕突起的方向指向纸条的背面。如果从纸条的下边向上方连续对折2 次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。
给定一 个输入参数N，代表纸条都从下边向上方连续对折N次，请从上到下打印所有折痕的方向
例如：N=1时，打印： down；N=2时，打印： down down up

在这里插入图片描述

我们把对折后的纸张翻过来，让粉色朝下，这时把第一次对折产生的折痕看做是根结点，那第二次对折产生的下折痕就是该结点的左子结点，而第二次对折产生的上折痕就是该结点的右子结点，这样我们就可以使用树型数据结构来描述对折后产生的折痕。

这棵树有这样的特点：

  1. 根结点为下折痕
  2. 每一个结点的左子结点为下折痕
  3. 每一个结点的右子结点为上折痕

在这里插入图片描述

实现步骤：

  1. 定义结点类
  2. 构建深度为N的折痕树
  3. 使用中序遍历，打印出树中所有结点的内容

构建深度为N的折痕树：

  1. 第一次对折，只有一条折痕，创建根结点；
  2. 如果不是第一次对折，则使用队列保存根结点；
  3. 循环遍历队列
  • 从队列中拿出一个结点；
  • 如果这个结点的左子结点不为空，则把这个左子结点添加到队列中；
  • 如果这个结点的右子结点不为空，则把这个右子结点添加到队列中；
  • 判断当前结点的左子结点和右子结点都不为空，如果是，则需要为当前结点创建一个值为down的左子结点，一个值为up的右子结点
import java.util.Deque;
import java.util.LinkedList;

public class PagerFoldingTest {

    public static void main(String[] args) {

        // 模拟折纸过程，产生树
        Node<String> tree = createTree(3);
        // 遍历树，打印每个结点
        printTree(tree);
    }

    // 通过模拟对折 N 次纸，产生树
    public static Node<String> createTree(int N){
        // 定义根结点
        Node<String> root = null;
        for (int i = 0; i < N; i++) {
            // 当前是第一次对折
            if (i == 0){
                root = new Node<>("down",null,null);
                continue;
            }
            // 当前不是第一次对折
            // 定义一个辅助队列，通过层序遍历的思想，找到叶子结点，叶子结点添加子节点
            Deque<Node> queue = new LinkedList<>();
            queue.add(root);
            // 循环遍历队列
            while(!queue.isEmpty()){
                // 从队列中弹出一个结点
                Node<String> tmp = queue.poll();
                // 如果有左子结点，则把左子结点放入到队列中
                if (tmp.left != null){
                    queue.add(tmp.left);
                }
                // 如果有右子结点，则把右子结点放入到队列中
                if (tmp.right != null){
                    queue.add(tmp.right);
                }
                // 如果同时没有左子结点和右子结点，那么证明该节点是叶子结点，只需要给该节点添加左子结点和右子结点即可
                if (tmp.left == null && tmp.right == null){
                    tmp.left = new Node<String>("down", null,null);
                    tmp.right = new Node<String>("up",null,null);
                }
            }
        }
        return root;
    }


    // 打印树中每个结点到控制台
    public static void printTree(Node<String> root){
        // 使用中序遍历完成
        if (root == null){
            return;
        }
        // 打印左子树的每个结点
        if (root.left != null){
            printTree(root.left);
        }
        // 打印当前结点
        System.out.print(root.item + " ");
        // 打印右子树的每个结点
        if (root.right != null){
            printTree(root.right);
        }
    }
    
    // 结点类
    private static class Node<T>{
        // 存储元素
        public T item;
        public Node left;
        public Node right;

        public Node(T item, Node left, Node right) {
            this.item = item;
            this.left = left;
            this.right = right;
        }
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/457212
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号