数据结构二叉树及遍历二叉树

ゝ一纸荒年。 2022-06-17 11:17 328阅读 0赞

# 概述 #

二叉树，是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。

![这里写图片描述][f993d8e4a5e9ada5b12cddb9ec107ac7.png]

# 二叉树的特性 #

*  在非空二叉树中，第i层的结点总数不超过2^(i-1) , i>=1；
 *  深度为h的二叉树最多有2^h个结点(h>=1)，最少有h个结点；
 *  对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；
 *  具有n个结点的完全二叉树的深度为
 *  有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：  
    若I为结点编号则 如果I>1，则其父结点的编号为I/2；  
    如果2*I<=N，则其左儿子（即左子树的根结点）的编号为2*I；若2*I>N，则无左儿子；  
    如果2*I+1<=N，则其右儿子的结点编号为2*I+1；若2*I+1>N，则无右儿子。
 *  给定N个节点，能构成h(N)种不同的二叉树。h(N)为卡特兰数的第N项。h(n)=C(2\*n，n)/(n+1)。
 *  设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i\[4\]

# 二叉树的分类 #

## 斜树 ##

所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。所以，线性表的数据结构可以理解成树的一种表达方式。

![这里写图片描述][ce5bda121087a4ae33e4cbd91e4d7028.png]

## 满二叉树 ##

在一棵树中，如果所有的分支节点都存在左子树和右子树  
，并且所有的叶子节点都在同一层上，那么这样的二叉树称之为满二叉树。

![这里写图片描述][28f5a2e84f5d1c80daf601115b8aea56.png]

## 完全二叉树 ##

对一颗具有n个节点的二叉树按层序编号，如果编号为i（1<= i <=n）的节点与同样深度的满二叉树中编号为i的节点的位置完全相同，那么这样的树，称之为完全二叉树。

![这里写图片描述][423d1b0fea1b97e5ec0689d75413f926.png]

# 二叉树的存储结构 #

![这里写图片描述][508a492e3911c557018da7423de31084.png]

顺序存储结构：  
![这里写图片描述][f3a2d569c2fc346585a56ca27c73cefc.png]

二叉链表：  
![这里写图片描述][51619904f128cd13525ab4581be06573.png]

# 二叉树的遍历 #

二叉树的数据结构中，常用的遍历方式有三种：

*  先序遍历
 *  中序遍历
 *  后序遍历

当然，二叉树还有一种不常见的遍历方式-层序遍历，这里暂不做介绍。

在树的遍历中，我们通常使用的是通过递归方式来进行遍历。

## 先序遍历 ##

规则是若二叉树为空，则空操作返回，否则先访问跟结点，然后先序遍历左子树，再先序遍历右子树。

![这里写图片描述][2282a4ab1f970a5180c0df82b6d72d85.png]

代码实现如下：

/**
    	 * 先序遍历
    	 * 
    	 * parent->left->right
    	 */
    	public void preOrder(TreeNode node) {
    		if (node == null) {
    			return;
    		}
    
    		System.out.print(node.data + "\t");
    		preOrder(node.leftChild);
    		preOrder(node.rightChild);
    	}

## 中序遍历 ##

规则是若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。

![这里写图片描述][619fcfe1364bf72cf0550a26b29b79ec.png]

代码实现如下：

/**
    	 * 中序遍历
    	 * 
    	 * left->parent->right
    	 */
    	public void midOrder(TreeNode node) {
    		if (node == null) {
    			return;
    		}
    
    		midOrder(node.leftChild);
    		System.out.print(node.data + "\t");
    		midOrder(node.rightChild);
    	}

## 后序遍历 ##

规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。

![这里写图片描述][fa48dbb6e769074236ab4e9049f6d8de.png]

代码实现如下：

/**
    	 * 后序遍历
    	 * 
    	 * left->right->parent
    	 */
    	public void postOrder(TreeNode node) {
    		if (node == null) {
    			return;
    		}
    
    		postOrder(node.leftChild);
    		postOrder(node.rightChild);
    		System.out.print(node.data + "\t");
    	}

# Java实现二叉树 #

package structdemo;
    
    /**
     * 
     * 二叉树
     * 
     * @author zhangke
     */
    public class BinaryTree {
    
    	// 创建二叉树并调用遍历方法
    	public static void main(String[] args) {
    
    		BinaryTree binaryTree = new BinaryTree();
    		binaryTree.createBinaryTree();
    		System.out.println("height：" + binaryTree.getHeight());
    		System.out.println("size：" + binaryTree.getSize());
    
    		binaryTree.preOrder(binaryTree.root);
    		binaryTree.midOrder(binaryTree.root);
    		binaryTree.postOrder(binaryTree.root);
    
    	}
    
    	/**
    	 * 根节点
    	 */
    	private TreeNode root = null;
    
    	public BinaryTree() {
    		root = new TreeNode(1, "A");
    	}
    
    	/**
    	 * 构建二叉树 
    	 * 
    	 *       A 
    	 *       
    	 *   B      C 
    	 * 
    	 * D    E       F
    	 */
    	public void createBinaryTree() {
    		TreeNode nodeB = new TreeNode(2, "B");
    		TreeNode nodeC = new TreeNode(3, "C");
    		TreeNode nodeD = new TreeNode(4, "D");
    		TreeNode nodeE = new TreeNode(5, "E");
    		TreeNode nodeF = new TreeNode(6, "F");
    		root.leftChild = nodeB;
    		root.rightChild = nodeC;
    		nodeB.leftChild = nodeD;
    		nodeB.rightChild = nodeE;
    		nodeC.rightChild = nodeF;
    	}
    
    	/**
    	 * 获取树的深度
    	 * 
    	 * @return
    	 */
    	public int getHeight() {
    		return getHeight(root);
    	}
    
    	/**
    	 * 获取指定结点的深度
    	 */
    	private int getHeight(TreeNode node) {
    		if (node == null) {
    			return 0;
    		}
    
    		// 每当一个结点存在子结点时，Height就加一个
    		int i = getHeight(node.leftChild);
    		int j = getHeight(node.rightChild);
    		return (i > j) ? (i + 1) : (j + 1);
    	}
    
    	/**
    	 * 获取结点个数
    	 * 
    	 * @return
    	 */
    	public int getSize() {
    		return getSize(root);
    	}
    
    	private int getSize(TreeNode node) {
    		if (node == null) {
    			return 0;
    		}
    		return 1 + getSize(node.leftChild) + getSize(node.rightChild);
    	}
    
    	/**
    	 * 先序遍历
    	 * 
    	 * parent->left->right
    	 */
    	public void preOrder(TreeNode node) {
    		if (node == null) {
    			return;
    		}
    
    		System.out.print(node.data + "\t");
    		preOrder(node.leftChild);
    		preOrder(node.rightChild);
    	}
    
    	/**
    	 * 中序遍历
    	 * 
    	 * left->parent->right
    	 */
    	public void midOrder(TreeNode node) {
    		if (node == null) {
    			return;
    		}
    
    		midOrder(node.leftChild);
    		System.out.print(node.data + "\t");
    		midOrder(node.rightChild);
    	}
    
    	/**
    	 * 后序遍历
    	 * 
    	 * left->right->parent
    	 */
    	public void postOrder(TreeNode node) {
    		if (node == null) {
    			return;
    		}
    
    		postOrder(node.leftChild);
    		postOrder(node.rightChild);
    		System.out.print(node.data + "\t");
    	}
    
    	/**
    	 * 定义树的结点
    	 *
    	 * @author zhangke
    	 */
    	public class TreeNode {
    
    		/**
    		 * 下标
    		 */
    		private int index;
    		/**
    		 * 数据
    		 */
    		private String data;
    		/**
    		 * 左孩子
    		 */
    		private TreeNode leftChild;
    		/**
    		 * 右孩子
    		 */
    		private TreeNode rightChild;
    
    		public TreeNode(int index, String data) {
    			this.index = index;
    			this.data = data;
    		}
    	}
    
    }

# 常见面试题 #

已知，某树的先序遍历为：\{ 4, 2, 1 ,0, 3, 5, 9, 7, 6, 8 \}，中序遍历为: \{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 \}，请画出该树。

在解题之前我们可以明确一个概念：二叉树中序遍历加任意一种其他遍历方式都可以确定一棵树。  
解释：因为不论是先序遍历、后序遍历或者是层序遍历，都只能确定一颗树的根节点，在确定根节点后通过中序遍历就能区分树的左右子树，这样通过递归的思想就能确定一棵树了。

解题步骤如下：  
![这里写图片描述][0c9031a5379477c8f37d4d534c860a87.png]

[f993d8e4a5e9ada5b12cddb9ec107ac7.png]: /images/20220617/9506adce1b284c3c931bd74e5da2cad3.png
[ce5bda121087a4ae33e4cbd91e4d7028.png]: /images/20220617/c39ac853129941a3bf3e9dc4b1664207.png
[28f5a2e84f5d1c80daf601115b8aea56.png]: /images/20220617/fe7f433f07b8495ea94a02ca66947208.png
[423d1b0fea1b97e5ec0689d75413f926.png]: /images/20220617/c0d115b90638498da8a819bfe219bcb2.png
[508a492e3911c557018da7423de31084.png]: /images/20220617/5a965d817f1e4c829a4873cb228c77e4.png
[f3a2d569c2fc346585a56ca27c73cefc.png]: /images/20220617/4f338f621ddf45d480ac9bda6cfbe9d0.png
[51619904f128cd13525ab4581be06573.png]: /images/20220617/50fceb1011b5482195880bba37193e2e.png
[2282a4ab1f970a5180c0df82b6d72d85.png]: /images/20220617/47c8b300741e473b9c5e0d760caca84b.png
[619fcfe1364bf72cf0550a26b29b79ec.png]: /images/20220617/53d362c91d3b43f498d6edf09539378b.png
[fa48dbb6e769074236ab4e9049f6d8de.png]: /images/20220617/7258682f17a74bc396b14c1c657e6c82.png
[0c9031a5379477c8f37d4d534c860a87.png]: /images/20220617/8e0d68e992c94006bbfece6e773dfd49.png