二叉树(0001)_原创文档.pdf

二叉树

第六章树

第一部分：知识点

知识脉络：

重点：二叉树的性质、：I树的各种遍历方法及它g1所确定的序列问的关

系、二又树上的基本运算算法

的实现、二又树的线索化方法，构造赂夫曼树的方法。

难点：二叉树上各种算法，特别是遍历的非递归算法的设计。

一、二叉树的遍历的非递归算法

1.先序遍历

先将根结点入栈，然后只要栈不空，先出栈，然后沿着左子针依次访问沿途经

过的子树根结点，同时将右指针进栈（以便递归访问左子树后访问右子树），如

此重复，直至栈为空。

voidPreOrderBiTree(BitTreeT)

{SqStackS;

BitTreep;

InitStack(S);/*初始化一个空栈*/

Push(S,T);/*根结点指针进栈*/

while(!EmptyStack(S))/*栈为空时算法结束*/

{Pop(S，p);/*弹栈，p指向(子树)根结点*/

while(p)

/*访问根结点*/

if(p-rchild)Push(S,p-rchild);/*非空的右指针进栈*/

p=p-lchild;/*沿着左指针访问，直到左指针为空*/

}

elsep=q-rchild;

}

}

二、线索二叉树

1、已知树T如下，画出它的三种线索二叉树

先序线索二叉树

（1）写出先序序列：ABDCEFG

（2）为度不是2结点添加指针。

若没有左孩子，添加左孩子指针并

指向直接前驱。

若没有右孩子，添加右孩子指针

并指向直接后继。

中序线索二叉树后序线索二叉树

中序序列：DBAFEGC写出后序序列：DBFGECA

2、中序线索二叉树的存储结构

带头结点的中序线索化树

以中序线索链表为存储结构的中序遍历

inorderthread1(BiThrTreeThrt)

{

BiThrTreep=Thrt-lchild;

while(p!=Thrt)

{while(p-ltag==0)p=p-lchild;

while(p-rtag==1p-rchild!=Thrt)

p=p-rchild;

}

}

第二部分：习题

一、选择题

1．已知一算术表达式的中缀形式为A+B*C-D/E，

后缀形式为ABC*+DE/-，其前缀形式为()

A．-A+B*C/DEB.-A+B*CD/E

C．-+*ABC/DED.-+A*BC/DE

2.设有一表示算术表达式的二叉树（见右图），

/

它所表示的算术表达式是（+）。*+

*C-

DEF