【非线性结构】树

港控/mmm° 2022-04-08 09:54 272阅读 0赞

## 一、树 ##

### 1、什么是树 ###

什么是树结构？从形状来看，树结构是现实中的树倒立得到的结构。现实生活中有很多这种结构，如，一个家族的家谱、一个机构的组织架构。

![2018121317464227.png][]   ![20181213172327382.png][]

从定义来说，树是一些节点的集合，这个集合要么是空集，要么是一个根节点加上n个非空子树（n≥0），这是递归的定义方式。

这个节点包含数据域、指向n个子树的n条边。如下面所示，树T是根节点T+4个子树，同样，4个子树也分别可以看成类似的方式。

![20181213182821142.png][]        ![20181213183835146.png][]

### 2、树的相关概念 ###

**（1）树节点之间的关系**

叶节点：没有子节点的节点

根节点：没有父节点的节点，一棵树只有一个。如果单独看树的各个子树的话，每个子树也有一个根节点（只要不是空树）。

兄弟节点：有相同的父节点的节点互为兄弟节点

堂兄弟节点：父节点是兄弟节点的节点互为堂兄弟

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzMwOTczNDMx_size_16_color_FFFFFF_t_70][]

**（2）路径**

节点n1到节点nk的路径：是一个包括n1和nk序列。如上图节点A到节点D的路径为：A，B，D （A、D包括在序列里面）

路径的长：是该路径边的个数（路径节点个数-1）。如路径A，B，D的长为3 - 1 = 2

**（3）节点的高度、深度、层 以及 树的高度、深度**

节点的深度：根到该节点的路径的长。注意：这条路径是唯一的。

节点的高度：该节点到它可到达的叶子节点的所有路径的长的最大值。注意：由于从一个节点可到达的叶子节点可能不只一个，所以路径不只一条，因此要取最大值。

节点的层数：层数与深度类似，只不过起点是1。层是一个集合，某一层包含多个节点。

关于深度、高度，可以用生活的概念来理解。在生活中，说到高度，就是从下往上度量的，起点都是地面。树中的高度也是一样，从最底层开始计数，并且计数的起点是0。

而生活中说到深度，是从上往下去度量的，比如水深多少米，起点是水平面。树中的深度也是一样，以根节点为“水平面”，计数起点也是1。

树中的2种特殊结点：叶节点的高度为0；根节点的深度为0

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzMwOTczNDMx_size_16_color_FFFFFF_t_70 1][]

树的高度：是根节点的高度，上面的树的高度为3

树的深度：是树最深的叶节点的深度，上面的树的深度为3。树的深度总等于树的高度

## 二、二叉树 ##

### 1、二叉树的定义 ###

二叉树：每个节点最多有2个“分叉”的树，即每个节点最多只能有2个子节点

### 2、一些特殊的二叉树 ###

**（1）5种形态**

**（2）完全二叉树 和 满二叉树**

完全二叉树：叶节点在最下面2层，最后一层的叶节点都**靠左排列**，并且除了最后一层，其它层的节点个数都要达到最大。

满二叉树：叶节点都在最底层，除了叶节点之外，每个节点都有2个子节点。换句话说，满二叉树没有子节点个数为1的节点。

### 3、二叉树的两种存储（表示）方式 ###

**（1）链式存储**

如下图所示，我们用3个字段来表示一个节点。一个存储数据，另外2个存储指向左右子节点的地址。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzMwOTczNDMx_size_16_color_FFFFFF_t_70 2][]

大部分二叉树都是通过这种结构来实现的。通过这种方式，只要我们知道根节点，就可以通过其指向左右子节点的两个地址域，将整棵树串起来。

**（2）顺序存储**

如下图所示，我们把树存到一个数组中，**利用数组下标来表示节点之间的关系**（父节点、子节点）。我们把根节点存储在下标为 i =1的位置，根节点的左子节点存储在下标为2 \* i = 2的位置，根节点的右子节点存储在下标为2 \* i + 1=3的位置。以此类推。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzMwOTczNDMx_size_16_color_FFFFFF_t_70 3][]

我们可以看到，如果节点X存储在数组中下标为 i 的位置，那么下标为2 \* i 的位置就是它的左子节点，下标为2 \* i + 1的位置就是它的右子节点；反过来，下标为 i / 2的位置就是它的父节点。通过这种方式，我们可以通过下标计算，把整棵树都串起来。

顺序存储一般针对完全二叉树或者比较接近完全二叉树的二叉树，这也就是为什么要单独提出完全二叉树这个概念的原因，也是为什么在定义完全二叉树时，要强调最后一层的叶节点**靠左排列**。

## 三、二叉搜索树的实现 ##

由于使用数组表示二叉树的话，为了不浪费空间，数组只适合表示**完全二叉树、满二叉树或者与它们非常接近的树**。正因为顺序结构有着这样的局限性，所以我实现二叉树时只用链式结构。

### 1、基本实现 ###

class TreeNode {
    	public TreeNode left;  //左引用域
    	public TreeNode right; //右引用域
    	public int data;	   //数据域
    	
    	//结点的三种构造方式
    	public TreeNode() {
    	}
    	public TreeNode(int data, TreeNode left, TreeNode right) {
    		this.data = data;
    		this.left = left;
    		this.right = right;
    	}
    	public TreeNode(int data) {
    		this.data = data;
    		this.left = null;
    		this.right = null;
    	}
    	
    	//插入结点（并保持二叉搜索树的结构）
    	public static TreeNode insert(TreeNode root, int data) {
    		if (root == null) {
    			root = new TreeNode(data);
    		}
    		else if (data <= root.data) {
    			root.left = insert(root.left, data);
    		} else {
    			root.right = insert(root.right, data);
    		}
    		return root;
    	}
    	
    	//判断是否存在值为给定值的结点
    	public static boolean find(TreeNode root, int data) {
    		if(root == null) {   // 出口1
    			return false;
    		} else if (root.data == data) {    //  出口2
    			return true;
    		} else if (root.data < data) {
    			return find(root.right, data);
    		} else {
    			return find(root.left, data);
    		}
    	}
    	
    	//查找树中值最小的结点，并返回其值
    	public static int findMin(TreeNode root) {
    		if (root == null) {
    			System.out.println("这是一个空树");
    			return -10000;
    		}
    		while (root.left != null) {
    			root = root.left;
    		}
    		return root.data;
    	}
    	
    	//查找树中值最大的结点，并返回其值
    	public static int findMax(TreeNode root) {
    		if (root == null) {
    			System.out.println("这是一个空树");
    			return -10000;
    		}
    		while (root.right != null) {
    			root = root.right;
    		}
    		return root.data;
    	}
    	
    	//中序遍历树
    	public static void inOrder(TreeNode root) {
    		if (root == null) {
    			return;
    		}
    		inOrder(root.left);
    		System.out.print(root.data+"  ");
    		inOrder(root.right);
    	}
    	
    	//后序遍历树
    	public static void postOrder(TreeNode root) {
    		if (root == null) {
    			return;
    		}
    		postOrder(root.left);
    		postOrder(root.right);
    		System.out.print(root.data+"  ");
    	}
    	
    	//先序遍历树
    	public static void preOrder(TreeNode root) {
    		if (root == null) {
    			return;
    		}
    		System.out.print(root.data+"  ");
    		preOrder(root.left);
    		preOrder(root.right);
    	}
    }
    
    public class TreeTest {
    	public static void main(String[] args) {
    //插入结点，构造一棵树
    //	                    5
    //			   / \
    //			  3   10
    //			 / \   \
    //			1   4   11
    		TreeNode root = null;
    		root = TreeNode.insert(root, 5);
    		root = TreeNode.insert(root, 10);
    		root = TreeNode.insert(root, 3);
    		root = TreeNode.insert(root, 4);
    		root = TreeNode.insert(root, 1);
    		root = TreeNode.insert(root, 11);
    		
    		TreeNode.inOrder(root);  //中序遍历
    		System.out.println("\n======================================");
    		TreeNode.postOrder(root); //后序遍历
    		System.out.println("\n======================================");
    		TreeNode.preOrder(root);  // 先序遍历
    		
    		System.out.println();
    		System.out.println();
    		System.out.println(TreeNode.find(root, 11)); //查看是否有值为11的结点
    		System.out.println(TreeNode.find(root, 100));//查看是否有值为100的结点
    		System.out.println(TreeNode.findMin(root)+"		"+TreeNode.findMax(root));//打印最大值、最小值
    	}
    }

初步测试结果如下图所示，说明各个方法都实现了我们想要的效果。

![20181210104654985.png][]

再测试如果是特殊的树，该类是否还可以正常使用。

public class TreeTest {
    	public static void main(String[] args) {
    		//构造三棵树
    		//第一棵树
    //	                    5
    //			   / 
    //			  3   
    //			 /   
    //			1      
                    //第二棵树
    //	                    5
    //			     \
    //			      10
    //			       \
    //			        11	
    		//第三棵树：空树
    		
    		TreeNode root1 = null;
    		root1 = TreeNode.insert(root1, 5);
    		root1 = TreeNode.insert(root1, 3);
    		root1 = TreeNode.insert(root1, 1);
    		
    		TreeNode root2 = null;
    		root2 = TreeNode.insert(root2, 5);
    		root2 = TreeNode.insert(root2, 10);
    		root2 = TreeNode.insert(root2, 11);
    		
    		TreeNode root3 = null;
    		
    		System.out.print("中序遍历： ");
    		TreeNode.inOrder(root1);  //中序遍历
    		System.out.print("后序遍历： ");
    		TreeNode.postOrder(root1); //后序遍历
    		System.out.print("先序遍历： ");
    		TreeNode.preOrder(root1);  // 先序遍历
    		System.out.println();
    		System.out.println(TreeNode.find(root1, 5)); //查看是否有值为5的结点
    		System.out.println(TreeNode.find(root1, 100));//查看是否有值为100的结点
    		System.out.println(TreeNode.findMin(root1)+"		"+TreeNode.findMax(root1));//打印最大值、最小值
    
    		System.out.println("\n======================================");
    		System.out.print("中序遍历： ");
    		TreeNode.inOrder(root2);  //中序遍历
    		System.out.print("后序遍历： ");
    		TreeNode.postOrder(root2); //后序遍历
    		System.out.print("先序遍历： ");
    		TreeNode.preOrder(root2);  // 先序遍历
    		System.out.println();
    		System.out.println(TreeNode.find(root2, 5)); //查看是否有值为5的结点
    		System.out.println(TreeNode.find(root2, 100));//查看是否有值为100的结点
    		System.out.println(TreeNode.findMin(root2)+"		"+TreeNode.findMax(root2));//打印最大值、最小值
    
    		System.out.println("\n======================================");
    		System.out.print("先序遍历： ");
    		TreeNode.preOrder(root3);  // 先序遍历
    		System.out.println();
    		System.out.println(TreeNode.find(root3, 5)); //查看是否有值为5的结点
    		System.out.println(TreeNode.findMin(root3)+"		"+TreeNode.findMax(root3));//打印最大值、最小值
    	}
    }

其结果如下所示，输出正常。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzMwOTczNDMx_size_16_color_FFFFFF_t_70 4][]

### 2、功能完善 ###

四、（链式存储的）二叉树的递归和非递归遍历

二叉树的遍历是实现其他几乎所有操作的前提，所以理解好遍历至关重要。由前面的讲解可以知道，链式存储的二叉树，每个节点可以通过它的2个地址域找到它的子节点。但，问题在于子节点却不能反过来找到它的父节点，而且，根节点每一次有2条路可以选择，这就造成了选择一条路之后，就不能从子节点回到根节点来选择第二条路。所以，第二条路上面的结点也就不能遍历到。

关于这个问题，有一些解决方案，比如，既然是因为子节点找不到它的父节点，那就在表示一个节点时多加一个地址域指向它的父节点（根节点的第三个地址域指向null），这是一种思路，不过，我们通常讲的前序、中序、后序遍历采用的还是最普通的2个地址域的存储结构。接下来我描述一下这些遍历的底层机制。

1、前序遍历

（1）递归实现

（2）非递归实现

2、中序遍历

（1）递归实现

（2）非递归实现

3、后序遍历

（1）递归实现

（2）非递归实现

4、层序遍历

[2018121317464227.png]: https://img-blog.csdnimg.cn/2018121317464227.png
[20181213172327382.png]: /images/20220406/f72618a0ecea49c5bddfe0ab223aaeea.png
[20181213182821142.png]: https://img-blog.csdnimg.cn/20181213182821142.png
[20181213183835146.png]: /images/20220406/48e3b7752085468f8949ceab35f85126.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzMwOTczNDMx_size_16_color_FFFFFF_t_70]: /images/20220406/2f59cd522a404769abe30645ec83f498.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzMwOTczNDMx_size_16_color_FFFFFF_t_70 1]: /images/20220406/43426c79cdf646658e196ca8476c1a8b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzMwOTczNDMx_size_16_color_FFFFFF_t_70 2]: /images/20220406/3e268bb9dae54af0a68de1c3e1623988.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzMwOTczNDMx_size_16_color_FFFFFF_t_70 3]: /images/20220406/985a3cc8b42c4205a5691327764b2957.png
[20181210104654985.png]: /images/20220406/12f6ed8c57604de0866b14b66d4adf7d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzMwOTczNDMx_size_16_color_FFFFFF_t_70 4]: /images/20220406/ef9e0aed935d4511be7cf601ef80b77d.png