数据结构Java8二叉树与树

二叉树与树P137-179

目的、内容：掌握二叉树和树的性质和应用。主要有：最近公共祖先、哈夫曼树等。

重点：树的建立、遍历。 难点：二叉树和树的应用。 学法：基本按书上的要求 教学过程： 一、二叉树

1.基本术语：二叉树递归定义书P139

二叉树（binary tree）是n个结点的有限集合： ? 空二叉树；

? 由一个根结点、两棵互不相交的左子树和右子树组成。

2.二叉树性质书P140

1) Problem 1259 二叉树的性质

给你一棵有n个结点的完全二叉树，请你编程计算它的叶结点的个数、深度。 ? 叶结点的个数： 叶结点个数计算推导：

性质3 设一棵二叉树的叶子结点树为n0，2度结点数为n2，则n0=n2+1。① 1度结点数为n1，

则n为完全二叉树的结点总数，n=n0+n1+n2。② 公式①和公式②消去n2得n=2n0+n1-1。

由于完全二叉树中度为1的结点数只有两种可能0或1，因此n0=(n+1)/2或n0=n/2。 ? 完全二叉树的深度:

性质4：一棵具有n个结点的完全二叉树，其高度为

2) 外Problem 最近公共祖先 h?logn?1?2?SMP Problem 1046 村民相会

SMP Problem 1062 牛郎织女的命运

性质5：一棵具有n个结点的完全二叉树，对序号为i（0≤i＜n）的结点，有： 若i=0，则i为根结点，无父母结点； 若i>0，则i的父母结点序号为

(i?1)/2若2i+1＜n，则i的左孩子结点在2i+1；否则i无左孩子。

若2i+2＜n，则i的右孩子结点在2i+2；否则i无右孩子。

??3.完全二叉树的存储

4.二叉树顺序存储结构，见P143图6.8

二叉树的性质50137ACE45F260123G456n-1（a）一棵完全二叉树 ABCDEFGH2*i+1

二叉树的遍历 B1261、B1262、B1263

先序遍历：先访问根结点，然后分别先序遍历左子树、右子树（DLR）

中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树（LDR） 后序遍历：先后序遍历左、右子树，然后访问根结点（LRD） 如图：

图6.8 完全二叉树及其顺序存储结构

ABCD.EF.G....H

先根遍历序列：A B D G C E F H 中根遍历序列：D G B A E C H F 后根遍历序列：G D B E H F C A

按层次遍历：从上到下、从左到右访问各结点

1) 用递归完成先序遍历

如果树非空（树不空），输出根；递归左子树；递归右子树

public class Main { public static void main(String[] args) { String str = \ preorder(str,0); System.out.println(); } public static void preorder(String str,int i){ if(i

先根递归:先输出根,递归左子树,递归右子树. 后根递归:递归左子树,递归右子树,输出根. 中根递归:递归左子树, 输出根,递归右子树.

2) 用栈完成先序遍历

(1)根结点入栈。

(2)出栈，访问栈顶结点，右结点入栈，左结点入栈。

(3)重复(2)直到栈空。

public static void preorder(String str) { Stack s = new Stack(); s.push(0); int len = str.length(); while (!s.empty()) { int c = s.pop(); if (str.charAt(c) != '.') { System.out.printf(\ if (2 * c + 2 < len && str.charAt(2 * c + 2) != '.') s.push(2 * c + 2); if (2 * c + 1 < len && str.charAt(2 * c + 1) != '.') s.push(2 * c + 1); } } }

5.二叉树链式存储结构，见P143图6.9

左孩子数据右孩子leftABDGEHCF∧D根指针 rootdatarightAB∧∧E∧CF∧∧G∧（b）二叉链表∧H∧（a）一棵二叉树

图6.9 二叉树的二叉链表存储结构

1) 二叉链表结点类

class BinaryNode //二叉树的二叉链表结点类，T指定结点的元素类型 {

public T data; //数据域，存储数据元素 public BinaryNode left, right; //链域，分别指向左、右孩子结点 //构造结点，data指定元素，left、right分别指向左孩子和右孩子结点 public BinaryNode(T data, BinaryNode left, BinaryNode right) {

this.data = data;