11_1 韩顺平数据结构与算法树结构基础部分_二叉树 _递归

3）二叉树 1. 二叉树的概念
树有很多种，每个节点最多只有两个子节点的形式就是二叉树
二叉树的子节点分为左节点和右节点
如果该二叉树的所有叶子节点都在最后一层并且结点总数=2^n-1（n为层数）我们称为满二叉树
如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称之为完全二叉树
PS：连续是横向连续不是纵向连续（比如81->91左连续;71->61->15右连续）
2. 二叉树遍历说明
前序遍历：先输出父节点，再遍历左子树和右子树
中序遍历：先遍历左子树，再输出父节点，再遍历右子树
后续遍历：先遍历左子树，再遍历右子树，最后输出父节点
小结：看输出父节点的顺序，就确定是前序，中序还是后序

文章插图
思路分析：
【11_1韩顺平数据结构与算法树结构基础部分_二叉树】创建一颗二叉树前序遍历先输出当前节点（初始的时候是root节点）；如果左子节点不为空，则递归前序遍历；如果右子节点不为空，则递归前序遍历中序遍历如果当前节点的左子节点不为空，则递归中序遍历；输出当前节点如果当前节点的右子节点不为空，则递归中序遍历后序遍历如果当前节点的左子节点不为空，则递归后序遍历如果当前节点的右子节点不为空，则递归后序遍历输出当前节点
代码实现（遍历部分）

MainBinaryTree binaryTree = new BinaryTree();//创先需要的节点HeroNode root = new HeroNode(1, "宋江");HeroNode node2 = new HeroNode(2, "吴用");HeroNode node3 = new HeroNode(3, "卢俊义");HeroNode node4 = new HeroNode(4, "林冲");HeroNode node5 = new HeroNode(5, "关胜");//说明：我们先手动创建二叉树，后面使用递归创建二叉树root.setLeft(node2);root.setRight(node3);node3.setRight(node4);node3.setLeft(node5);binaryTree.setRoot(root);BinaryTree>Search//前序遍历public void preOrder() {if (this.root != null) {this.root.preOrder();} else {System.out.println("二叉树为空，无法遍历");}}//中序遍历public void infixOrder() {if (this.root != null) {this.root.infixOrder();} else {System.out.println("二叉树为空，无法遍历");}}//后序遍历public void postOrder() {if (this.root != null) {this.root.postOrder();} else {System.out.println("二叉树为空，无法遍历");}}HeroNode>Search// 1. 前序遍历public void preOrder() {//先输出父节点System.out.println(this);//向左子树前序遍历递归if (this.left != null) {this.left.preOrder();}//向右子树前序遍历递归if (this.right != null) {this.right.preOrder();}}// 2. 中序遍历public void infixOrder() {//向左子树中序遍历递归if (this.left != null) {this.left.infixOrder();}System.out.println(this);//向右子树中序遍历递归if (this.right != null) {this.right.infixOrder();}}// 3. 后序遍历public void postOrder() {//向左子树后序遍历递归iif (this.left != null) {this.left.postOrder();}if (this.right != null) {this.right.postOrder();}System.out.println(this);}

3. 二叉树的检索（查询）
要求：
请编写前中后序查找方法分别用三种方法查找hero.no==5的节点分析三种查找方法，进行比较
思路：
前序查找
先判断当前节点的no是否等于要查找的相等：则返回当前节点不等，则判断左子节点是否为空，若不空则递归前序查找，一旦找到就返回；左边前序递归完未找到，再判断右节点是否为空，不为空就前序递归右边，一旦找到就返回；
中序查找
判断当前节点的左子节点是否为空，不为空则前序递归查找如果找到就返回，否则就和当前节点比较，如果是就返回当前节点，否则继续进行右递归的中序查找如果右递归中序查找找到就返回，否则返回null

11_1 韩顺平 数据结构与算法 树结构基础部分_二叉树

11_1 韩顺平数据结构与算法树结构基础部分_二叉树