《数据结构》 (java版) 课件 6树、二叉树的性质和遍历

树和二叉树树的概念和常用术语递归、二叉树及其特性完全二叉树及其特性二叉树的存储二叉树的基本操作：遍历遍历的执行过程二叉树的其它操作树(Tree)离散数学有多种等价的定义，其中之一：

n个结点n-1条边的连通图。数据结构的定义同上，但选定一个结点作为“根(root)”，因此又叫做有根树。树用于表示有层次的数据，层次由数据之间的父子关系(一父多子)描述ACGBDEFHJACGBDEFHJ0层1层2层树是结点的有限集合，如果不为空集，其中，有一个特殊的结点叫做根，其他的结点划分为m个不相交的子集T1、T2、Tm，每个子集是一棵树，T1、T2、Tm叫做根的子树树中任何一个结点是整棵树的某棵子树的根结点树-目录基本术语DHIJM结点的度(degree):子树的个数终端/叶子结点(terminalnode/leaf):度为零的结点分支结点(branchnode):度大于零的结点ABCDEFGHIJMKL路径(path)：由从根到该结点所经边和结点构成：A-C-G路径长度(pathlength)：边的条数双亲结点孩子结点兄弟结点堂兄弟祖先结点子孙结点基本术语结点的层次(level):根结点0层、其孩子结点1层...(根到结点路径的长度)树的深度(depth):最大层次+1，或最长路径长度+1基本术语ABCDEFGHIJMKL0123有序树(orderedtree)：子树之间存在次序关系无序???树(orientedtree)：子树之间不存在次序关系基本术语PABCPBAC≠PABCPBAC=ArootBEFKLCGDHIJMF基本术语森林：是m（m≥0）棵互不相交的树的集合线性结构树型结构根结点无前驱第一个数据元素无前驱最后一个数据元素无后继叶子结点无后继其它结点一个前驱、多个后继其它数据元素一个前驱、一个后继树型结构和线性结构特点的对比一对一一对多递归定义：基础：空树是二叉树归纳：二叉树由根结点、左子树、右子树构成；并且左、右子树也是二叉树。二叉树(binarytree)RRLRRR1）空树2）

只含根结点4）左子树为空RRL3）

右子树为空RL5）左右子树都不为空二叉树从最基本的元素开始，重复使用简单的规则，就能构造出复杂的东西。复杂的东西有简单的构造原理。例如：算术表达式等递归(recursion)(a+b)/(c-d)+e+g*h/aaeab+cd-gh*//++ACGBDEFKLHJIMNOABCDEFGHKABCDEFGHK二叉树形态各异，但是，结构一样。二叉树扩展的二叉树(extendedbinarytree)ABECDABECD扩展的二叉树用方框表示空树，方框叫做外部结点性质1：二叉树的第i层上至多有2i个结点。(i≥0)二叉树具有以下五条重要性质：二叉树的特性层号ACGBDEFKLHJIMNO0123i=0时，只有一个根结点，满足2i=20=1；假设第i-1层上至多有2i-1个结点;二叉树上每个结点至多有两棵子树，则第i层的结点数=2i-1×2=2i。二叉树的特性用归纳法证明归纳基础：归纳假设：归纳：性质2：深度为k的二叉树上至多含2k-1个结点（k≥0）二叉树的特性证明：≤20+21+⋅⋅⋅⋅⋅⋅+2k-1=2k-1第0层:≤20第1层:≤21……第k-1层:≤2k-1深度为k，即有k-1层性质3：任何一棵二叉树，若它含有n0个叶子结点、n2个度为2的结点，则必存在关系式：n0=n2+1二叉树的特性ACGBDEFHJI设二叉树上边数为b，由树的性质：b=n-1又因为度为1的点引出一条边度为2的点引出2条边，所以：b=n1+2n2所以：n=n1+2n2+1公式(2)证明：设二叉树上结点总数n=n0+n1+n2公式(1)由式1和2得到：n0+n1+n2=n1+2n2+1整理后n0=n2+1给定n个(n≥0)结点，如何能得到深度最小的二叉树？先把第0层填满如果还有余下的结点，则把第1层填满如果还有余下的结点，则把第2层填满...，依次类推。填最后一层，按照从左往右的次序填，并且中间没有空隙完全二叉树(completebinarytree)ACGBDEFHJIACGBDEFHJI完全二叉树非完全二叉树扩展的完全二叉树(completebinarytree)ACGBDEFHJIACGBDEFHI取整函数的定义⎣x⎦=mifm≤x<m+1Math.floor(x)⎡x⎤=mifm-1<x≤mMath.ceil(x)设x是任意的实数，m是一个整数：⎣2.1⎦=2⎣-2.1⎦=-3⎡2.1⎤=3⎡-2.1⎤=-20123-1-2-3取整函数的性质⎣x⎦=⎡x⎤x是整数⎡x⎤=⎣x⎦+1x不是整数⎣-x⎦=-⎡x⎤x⎡x⎤⎣x⎦x+1x-1n是整数：⎣⎦+⎡⎤=n⎣⎦=⎡⎤证明：假设完全二叉树的深度为k。由定义：0-->k-2层构成的树一定是满二叉树由性质2：0-->k-2层结点数为：2k-1-1由性质2，0至k-1层结点数最多为：2k-1完全二叉树的特性性质4：具有n个结点的完全二叉树的深度为⎡log2(n+1)

⎤所以：2k-1-1<n≤2k-12k-1<n＋1≤2k

于是：k-1<log2(n+1)≤kk=⎡log2(n+1)

⎤所以：2k-1-1<n≤2k-12k-1≤n<2k

于是：k-1≤log2(n)<kk-1=⎣log2(n)⎦k=⎣log2(n)⎦+1按照从上往下，从左往右，从0开始连续对完全二叉树的结点编号：0123456789完全二叉树ACGBDEFHJI若i=0，则该结点是二叉树的根，无双亲。否则，编号为⎣⎦的结点为其双亲结点。性质5：结点的编号之间具有关系：完全二叉树的特性0123456789(2)若2i+1≥n，则编号为i的结点无左孩子,否则，编号为2i+1的结点为其左孩子结点。若2i+2≥n，则编号为i的结点无右孩子结点，否则，编号为2i+2的结点为其右孩子结点。完全二叉树的特性01234567891.具有1025个结点的二叉树的深度为____A.11B.10C.11至1025之间D.10至1024之间课堂练习2、有n个结点的满二叉树的叶子结点有多少？3、完全二叉树的度为1的结点有多少？5、有n个结点的二叉树最大深度是多少？最少深度是多少？4、一棵完全二叉树上有1001个结点，其中叶子结点的个数是____A.250B.500C.254D.505E.以上答案都不对ACGBDEFHJI0123456789

0123456789ABCEFDGHIJ完全二叉树的顺序存储二叉树的链式存储：二叉链AF∧∧E∧C∧D∧∧B∧rootABDCEF思考n个结点的链式表示中有多少个引用变量的值为null?由性质3:n0=n2+1设总的结点数为n，n=n0+n1+n2=n0+n1+n0-12n0+n1=n+1

从上往下看(top-down):叶子结点(n0)有2个null，度为1的结点(n1)有1个null，度为2的结点(n2)有0个null，2n0+n1?AF∧∧E∧C∧D∧∧B∧root思考n个结点的二叉链中有多少个引用变量的值为null?从下往上看(bottom-up):每个结点有2个引用变量，n个结点共2n个引用变量结点的孩子占用1个引用变量，每个结点(除根结点)都是某个结点的孩子，共有n-1个孩子结点，占用了n-1个引用变量所以null的个数为2n-(n-1)=n+1AF∧∧E∧C∧D∧∧B∧root∧链式存储：三叉链表二叉树的多数应用一般从root入手，采用top-down处理方式；有些应用需要采用bottom-up处理方式，为了方便找到父结点，也可以采用三叉链表像平衡树需要结合top-down和bottom-up2种方式，使用二叉链+栈AF∧∧E∧C∧D∧∧B∧root二叉树的操作二叉树是一种很重要的数据结构，但不如栈、队列和线性表那样基础，有公认的基本操作(接口)。二叉树作为数据的集合，其最基本的操作就是遍历。即枚举二叉树中的结点，从根结点开始，一个不多，一个不少的给出所有的结点。

线性结构的遍历：因为每个结点均只有一个后继，

所以只有一条搜索路径。二叉树的遍历：二叉树是非线性结构，每个结点有两个后继，则存在如何遍历，即按什么样的搜索路径进行遍历的问题。二叉树的遍历二叉树存在下述三条搜索路径：1．先上后下的按层次遍历；2．先左（子树）后右（子树）的遍历；DLR，LDR，LRD3．先右（子树）后左（子树）的遍历。DRL，RDL，RLD二叉树的遍历左子树右子树根根左子树右子树若二叉树为空树，则空操作；否则：（1）访问根结点（2）先序遍历左子树（3）先序遍历右子树先序遍历ABCDEFGHKABCDEFGHKABCDEFGHK先序遍历ABDCEFABC先序遍历练习左子树右子树根根左子树右子树若二叉树为空树，则空操作；否则：（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树中序遍历ABCDEFGHKABCDEFGHKABDCEHGKF中序遍历ABDCEFABC中序遍历练习后序遍历左子树右子树根根左子树右子树若二叉树为空树，则空操作；否则：（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。ABCDEFGHKABCDEFGHKADCBHKGFE后序遍历ABECD后序遍历练习层次遍历ACGBDEFKLHJIMNO0123层号从0层开始，逐层遍历，同一层，从左往右遍历遍历练习ABCDEFGHK写出下列二叉树的前序、中序、后序和层次遍历的结果。二叉树的结点

private

static

classNode<T>{ Tdata; Node<T>left; Node<T>right; Node(Tdata,Node<T>left,Node<T>right){

this.data=data;

this.left=left;

this.right=right; } }e二叉树public

classBiTree<T>{

privateNode<T>root;AF∧∧E∧C∧D∧∧B∧由两棵二叉树构造新的二叉树rootABCDEABCEFNrootABCDErootABCEF二叉树的构造器

publicBiTree(){//建立空树

}

publicBiTree(Tdata,BiTree<T>leftBiTree,BiTree<T>rightBiTree){

root=newNode<>(data,leftBiTree.root,rightBiTree.root);

leftBiTree.root=rightBiTree.root=null; } BiTree<String>btnull=newBiTree<>(); BiTree<String>btl=newBiTree<>("D",btnull,btnull);

btl=newBiTree<>("B",btl,btnull);

BiTree<String>btr=newBiTree<>("E",btnull,btnull);

btr=newBiTree<>("C",btr,btnull);

btl=newBiTree<>("A",btl,btr);二叉树的构造器

//使用前序和中序遍历的结果，构造一颗数据为Character的二叉树，用于构造测试用的二叉树

@SuppressWarnings("unchecked")

publicBiTree(StringpreString,StringinString){

if(preString.length()==0){//如果不特殊处理，makeBitree将崩溃

root=null; }else{

root=(Node<T>)makeBitree(preString,inString); } } BiTree<Character>btString=newBiTree<>("ABCDEFGHK","BDCAEHGKF");前序遍历

public

voidpreRootTraversal(){ preRootTraversal(root); }

private

voidpreRootTraversal(Node<T>t){

if(t==null)

return;

//对结点的数据进行处理，例如：输出结点t的数据 System.out.println(t.data); preRootTraversal(t.left); preRootTraversal(t.right); }∧AF∧∧E∧C∧D∧∧B注意：不是必须要println!!!中序遍历

public

voidinRootTraversal(){ inRootTraversal(root); }

private

voidinRootTraversal(Node<T>t){

if(t==null)

return; inRootTraversal(t.left);

//对结点的数据进行处理，例如：输出结点t的数据 System.out.println(t.data); inRootTraversal(t.right); }后序遍历

public

voidpostRootTraversal(){ postRootTraversal(root); }

private

voidpostRootTraversal(Node<T>t){

if(t==null)

return; postRootTraversal(t.left); postRootTraversal(t.right);

//对结点的数据进行处理，例如：输出结点t的数据 System.out.println(t.data); }层次遍历

public

voidlevelTraverse(){

if(root==null)

return; Deque<Node<T>>queue=newLinkedList<>();

queue.offer(root);

while(!queue.isEmpty()){ Node<T>t=queue.poll();

//对结点的数据进行处理，例如：输出结点t的数据 System.out.println(t.data);

if(t.left!=null)

queue.offer(t.left);

if(t.right!=null)

queue.offer(t.right); } }ABECD阶乘-递归定义1ifn=02!=2×1!1!=1×0!0!=1n!=n!=n*(n-1)!ifn≥1阶乘-递归的执行过程public

classFactorial{

public

static

longfact(int

n){

if(n==0)

return1;

return

n*fact(n-1); }

public

static

voidmain(String[]args){

long

result=fact(2); System.out.println(result); }}fact(2)fact(1)fact0)递归的执行过程：同一个方法，多次执行，但每次执行传入的参数不同前序遍历－执行过程

private

voidpreRootTraversal(A){

if(t==null)

return; System.out.println(t.data); preRootTraversal(t.left); preRootTraversal(t.right); }

private

voidpreRootTraversal(B){

if(t==null)

return; System.out.println(t.data); preRootTraversal(t.left); preRootTraversal(t.right); }

private

voidpreRootTraversal(null){

if(t==null)

return; System.out.println(t.data); preRootTraversal(t.left); preRootTraversal(t.right); }

private

voidpreRootTraversal(C){

if(t==null)

return; System.out.println(t.data); preRootTraversal(t.left); preRootTraversal(t.right); }ABDC部分执行过程示例：前序遍历－执行过程ABDCpre(A)pre(B)处理Apre(D)pre(null)处理Bpre(C)pre(null)处理Cpre(null)pre(null)处理Dpre(null)pre:preRootTraversal图中省略了if(t==null)前序遍历－执行过程ABDCt:At:Bt:0t:Ct:0t:0t:Dt:0t:0ABCD可以使用Debug功能观察函数的调用过程

public

voidpreRootTraversal(){ preRootTraversal(root); }

private

voidpreRootTraversal(Node<T>t){

if(t==null)

return;

//对结点的数据进行处理，例如：输出结点t的数据 System.out.println(t.data); preRootTraversal(t.left); preRootTraversal(t.right); }java的函数接口高阶函数：函数的参数或返回值是函数的函数。即函数也是数据。为了能将函数像数据那样传递，javase8提出了函数接口的概念：

只有1个抽象函数的接口1、javase8在包java.util.function定义了一系列的函数接口2、如果方法的参数的类型是函数接口，实参可以是函数引用或Lambda表达式或对象(引用)(这个对象所属的类实现了函数接口)。java的函数接口@FunctionalInterfacepublic

interfaceConsumer<T>{

voidaccept(Tt);

defaultConsumer<T>andThen(Consumer<?superT>after){Objects.requireNonNull(after);

return(Tt)->{accept(t);after.accept(t);};}}、前序遍历

public

voidpreRootTraversal(Consumer<T>fun){ preRootTraversal(root,fun); }

private

voidpreRootTraversal(Node<T>t,Consumer<T>fun){

if(t==null)

return;

//处理结点t

fun.accept(t.data); preRootTraversal(t.left,fun); preRootTraversal(t.right,fun); }传入函数btl.preRootTraversal(System.out::println);//函数引用 btl.preRootTraversal(x->System.out.println(x));//Lambda表达式btl.preRootTraversal(newTest());//对象publicclassTestimplementsConsumer<Test>{...}遍历小结1、时间复杂度为O(n)：因为访问每个结点用的时间是常数2、空间复杂度O(logn)：因为递归要用到系统栈，非递归的算法也要用到栈，极端情况会达到O(n)3、1979年，JosephMorris发明了空间复杂度为O(1)的遍历算法，利用了二叉链中大量的null引用变量非递归的遍历

public

voidinOrderNonRecursively(){

if(root==null)

return; Deque<Node<T>>stackNode=newLinkedList<>(); Node<T>p=root;

for(;;){//对变量p代表的每棵二叉树做相同的操作

while(p!=null){//向左不断的分解二叉树，将以后要访问的各子二叉树逐次入栈

stackNode.push(p);

p=p.left; }

//到此，p代表的二叉树分解到空二叉树，处理完毕

if(stackNode.isEmpty())

return;

p=stackNode.pop();//从栈中取出下1棵待处理的二叉树 System.out.println(p.data);//做处理，例如，输出根结点的值

p=p.right;//继续处理它的右子树 } }中序遍历如下，其它的见工程结点个数左子树右子树根根左子树右子树ABCDEFGHK

public

intcountNode(){

returncountNode(root); }

private

intcountNode(Node<T>t){

if(t==null)

return0;

returncountNode(t.left)+countNode(t.right)+1; }叶子结点个数ABCDEFGHK

public

intcountLeafNode(){

returncountLeafNode(root); }

private

intcountLeafNode(Node<T>t){

if(t==null)

return0;

if(t.left==null&&t.right==null)

return1;

returncountLeafNode(t.left)+countLeafNode(t.right); }左子树右子树根根左子树右子树ABCDEFGHK求树的深度

public

intdepth(){

returndepth(root); }

private

intdepth(Node<T>t){

if(t==null)

return0;

int

left=depth(t.left);

int

right=depth(t.right);

return

left>right?left+1:right+1; }左子树右子树根根左子树右子树查找二叉树中的某个结点在树中查找数据元素的值等于x的结点，如果找到，则返回这个结点，否则，返回null。ABECDrootX="C"查找二叉树中的某个结点

publicNode<T>search(Tx){

returnsearch(root,x); }

privateNode<T>search(Node<T>t,Tx){

if(t==null)

return

null;

if(t.data.equals(x))

return

t; Node<T>result=search(t.left,x);

if(result!=null)

return

result;

returnsearch(t.right,x); }判断二棵二叉树相等

public

booleanisEqual(BiTree<T>rhd){

if(this==rhd)return

true;

returnisEqual(this.root,rhd.root); }

private

booleanisEqual(Node<T>t1,Node<T>t2){

if(t1==null&&t2==null)return

true;

if(t1==null&&t2!=null||t1!=null&&t2==null)

return

false;

if(!t1.data.equals(t2.data))

return

false;

returnisEqual(t1.left,t2.left)&&isEqual(t1.right,t2.right); }左子树右子树根根左子树右子树左子树右子树根根左子树右子树二叉树转换为数组

//将先序遍历的结果存入数组

publicObject[]toArray(){

int

n=countNode();//因为没有size变量，只能笨办法 Object[]elements=newObject[n]; toArray(root,elements,0);

return

elements; }二叉树转换为数组

//pos：将以t为根的二叉树的第1个结点放入数组array的位置

//方法的返回值：以t为根的树的结点数,//或者说将t为根的二叉树向数组中放入了几个数据

private

inttoArray(Node<T>t,Object[]array,int

pos){

if(t==null)

return0;

array[pos++]=t.data;

int

countLeft=toArray(t.left,array,pos);

int

countRight=toArray(t.right,array,pos+countLeft);

return

countLeft+countRight+1; }poscountLeft右子树的第1个位置=？根左子树pos+1二叉树转换为数组

private

inttoArray0(Object[]array){

classState{

int

pos;

voidpreOrder(Node<T>s){

if(s==null)

return;

array[pos++]=s.data; preOrder(s.left); preOrder(s.right); } } States=newState();

s.preOrder(root);

return

s.pos; }使用局部类记录下一个存放位置

//这里传入数组a的主要目的：因为java的语法要求：不能写newT[]

//所以，传入a是为了获取数组元素的类型

//通过Java的反射机制，Array.newInstance//在运行时，new一个任意类型(不包括基本数据类型)的数组

publicT[]toArrayIn(T[]a){//将前序遍历结果存入指定的数组a中

int

size=countNode();

if(a.length<size)

a=(T[])Array.newInstance(a.getClass().getComponentType(),size);

int

n=toArrayIn(root,a,0);

assert(n==size);

if(a.length>size)//因为a的数组元素个数多余结点的个数，为了识别存储了多少个结点

a[size]=null;

return

a; }二叉树转换为数组copyAF∧∧E∧C∧D∧∧B∧tAF∧∧E∧C∧D∧∧B∧p先复制t的左子树，再复制t的右子树，然后生成新的根结点。根元素t右子树根元素p左子树右子树左子树copycopy

privateNode<T>copy(Node<T>t){//返回复制得到的二叉树的根结点

if(t==null)

return

null; Node<T>left=copy(t.left); Node<T>right=copy(t.right);

return

newNode<>(t.data,left,right);}复制以t为根的二叉树clone

publicObjectclone(){

try{ BiTree<T>v=(BiTree<T>)super.clone();

v.root=copy(root);//clone后二者的root引用了相同的node，不行

return

v;}catch(CloneNotSupportedExceptione){

//thisshouldn'thappen,sinceweareCloneable

throw

newInternalError(e);}}输出根结点到所有叶子结点的路径ABCDEFGHKABCDABCIAEFGHAEFGKAEFJIJ使用先序遍历，将先序遍历的结果保存于栈遇到叶子结点，从栈底到栈顶输出栈中的数据以结点x为根的子树完成了先序遍历，将结点x出栈输出根结点到所有叶子结点的路径

public

voidpath(){

if(root==null)

return; Deque<Node<T>>stack=newArrayDeque<>(); path(root,stack); }

private

voidpath(Node<T>t,Deque<Node<T>>stack){

if(t==null)

return;

if(t.left==null&&t.right==null){

for(Node<T>p:stack) System.out.print(p.data+""); System.out.println(t.data);

return; }

stack.offerLast(t); path(t.left,stack); path(t.right,stack);

stack.pollLast(); }根据先序和中序遍历结果构造二叉树ABCDEFGHK中序序列：先序序列：BDCAEHGKFABCDEFGHK

BDC

BCD左子树的中序和先序序列右子树的中序和先序序列EHGKFEFGHK根据先序和中序遍历结果构造二叉树

publicBiTree(StringpreString,StringinString){

root=(Node<T>)makeBitree(preString,inString); }根据先序和中序遍历结果构造二叉树

publicNode<String>makeBitree(StringpreString,StringinString){ Node<String>left=null,right=null;

if(preString.length()!=1){

//假设各个结点的值不一样，使用indexOf代替了书上的循环查找，

int

rootPos=inString.indexOf(preString.charAt(0));

if(roo