《[工学]数据结构第6章》由会员分享，可在线阅读，更多相关《[工学]数据结构第6章（84页珍藏版）》请在金锄头文库上搜索。
1、YOUR LOGO HERE第第 6 6 章章树和二叉树树和二叉树YOUR LOGO HERE树与图树与图 属于非线性结构属于非线性结构YOUR LOGO HERE6.1 6.1 树的定义和基本术语树的定义和基本术语YOUR LOGO HERE树的结构定义树的结构定义树树( (Tree)Tree)是是n(n=0)n(n=0)个结点的有限集个结点的有限集合。在任意一棵非空树中：合。在任意一棵非空树中：（1 1）有且仅有一个特定的结点，称）有且仅有一个特定的结点，称为树根为树根( (root)root)（2 2）当当n1n1时，其余结点被划分成时，其余结点被划分成mm个个互不相交互不相交的的子集子
2、集，每个子集又，每个子集又是一棵树，被称为子树是一棵树，被称为子树( (subtreesubtree) )。YOUR LOGO HERE树的表示方法树的表示方法abcdghijfemlkYOUR LOGO HERE树的表示方法树的表示方法abcde kl fgh m ijYOUR LOGO HERE树的表示方法树的表示方法abeklfcgdhmijYOUR LOGO HERE树的表示方法树的表示方法(a(b(e(k,l),f),c(g),d(h(m),i,j)YOUR LOGO HERE基本术语基本术语s s结点结点s s结点的度，树的度结点的度，树的度s s叶子叶子( (终端结点终端结点)
3、)s s非终端结点非终端结点s s结点的层次结点的层次s s树的深度树的深度s s有序树，无序树有序树，无序树s s森林森林abcdghijfemlkYOUR LOGO HERE基本术语基本术语rr 孩子孩子rr 双亲双亲rr 兄弟兄弟rr 祖先祖先rr 子孙子孙rr 堂兄弟堂兄弟abcdghijfemlkYOUR LOGO HERE树的抽象数据类型定义树的抽象数据类型定义ADT TreeADT Tree数据对象数据对象DD：DD是具有相同特性的数据元是具有相同特性的数据元素集合；素集合；数据关系数据关系R R：若若DD为空集，则称为为空集，则称为空树空树； 若若DD仅含一个数据元素，则仅含一
4、个数据元素，则R R为空集，否为空集，否 则则R=HR=H，HH是如下二元关系：是如下二元关系：(1) (1) 在在DD中存在唯一的称为中存在唯一的称为根根的数据元素的数据元素 rootroot，它在关系它在关系HH下无前驱；下无前驱；YOUR LOGO HERE(2) (2) D-rootD-root，则存在则存在D-root D-root 的一个的一个 划分划分 DD1 1,D,D2 2, . ,D, . ,Dmm (m0)(m0)，对任意对任意 j j k(1k(1 j,kj,k m)m)有有DDj jDDk k= =，且对任意的且对任意的 i(1 i(1 i i m) m) 唯一唯一存
5、在数据元素存在数据元素 x xi i DDi i，有有 H;H;(3) (3) 对应于对应于D-rootD-root的划分，的划分，H-,.,.,有唯一的一个划分有唯一的一个划分HH1 1, , HH2 2,.,.,HHmm(m0)(m0)，对任意对任意 j j k(1k(1 j, kj, k m)m)有有 HHj jHHk k= =，且对任意的且对任意的i(1 i(1 i i m)m)，HHi i是是 DDi i上的二元关系，上的二元关系，( (DDi i,H,Hi i) ) 是一棵符合本是一棵符合本 定义的树，称为根定义的树，称为根rootroot的子树。的子树。YOUR LOGO HER
6、E基本操作基本操作基本操作：基本操作： InitTreeInitTree( return OK;return ERROR; return ERROR; else return OK; else return OK; YOUR LOGO HERE中序遍历递归算法中序遍历递归算法 status status InOrderTraverseInOrderTraverse( (BiTree BiTree T,T,Status(*Visit)( Status(*Visit)(TElemTypeTElemType e) e) if (T) if (T) if ( if (InOrderTraverseIn
7、OrderTraverse(T-(T-lchildlchild,Visit),Visit) )if (Visit(T-data) ) if (Visit(T-data) )if ( if ( InOrderTraverseInOrderTraverse(T-(T-rchildrchild,Visit),Visit) ) ) return OK; return OK;return ERROR; return ERROR; else return OK; else return OK; YOUR LOGO HERE后序遍历递归算法后序遍历递归算法 status status PostOrderTr
8、aversePostOrderTraverse( (BiTree BiTree T,T,Status(*Visit)( Status(*Visit)(TElemTypeTElemType e) e) if (T) if (T) if ( if ( PostOrderTraversePostOrderTraverse(T-(T-lchildlchild,Visit),Visit) ) )if ( if ( PostOrderTraversePostOrderTraverse(T-(T-rchildrchild,Visit),Visit) ) )if (Visit(T-data) if (Visi
9、t(T-data)return OK; return OK;return ERROR; return ERROR; else return OK; else return OK; YOUR LOGO HERE二叉树遍历算法应用二叉树遍历算法应用表达式表达式- -+ +a a/ /f fe e* *b b- -d dc ca+b*(c-d)-e/fa+b*(c-d)-e/fYOUR LOGO HERE原表达式：原表达式：a+b*(c-d)-e/fa+b*(c-d)-e/fqq先序序列：先序序列：( (波兰式波兰式) )-+ -+a*b-a*b-cdcd/ /efefqq中序序列：中序序列：a+b
10、*c-d-e/fa+b*c-d-e/fqq后序序列：后序序列：( (逆波兰式逆波兰式) )abcdabcd-*+-*+efef/- /-YOUR LOGO HERE二叉树遍历算法应用二叉树遍历算法应用利用先序思想构造二叉树利用先序思想构造二叉树要求：空指针位置补空格要求：空指针位置补空格YOUR LOGO HERE先序序列：先序序列：ABC_ _ DE_ G_ _F _ _ _ABC_ _ DE_ G_ _F _ _ _AGFEDCBYOUR LOGO HERE利用先序序列创建二叉树利用先序序列创建二叉树Status Status CreateBiTreeCreateBiTree( (BiTr
11、ee BiTree ;if ( if (chch= ) T=NULL;= ) T=NULL;else else if (!(T=new if (!(T=new BiTNode BiTNode) exit(OVERFLOW);) exit(OVERFLOW);T-data= T-data=chch; ;CreateBiTree CreateBiTree(T-(T-lchildlchild); );CreateBiTree CreateBiTree(T-(T-rchildrchild); ); return OK; return OK; YOUR LOGO HERE先序遍历的非递归算法先序遍历的非
12、递归算法Status Status PreOrderTraversePreOrderTraverse( (BiTree BiTree T,T,Status(*Visit)( Status(*Visit)(TElemType TElemType e) e) InitStack InitStack(S); p=T;(S); p=T;do do while (p) while (p) if (! Visit(p-data) return ERROR;if (! Visit(p-data) return ERROR;Push(S,p); p=p- Push(S,p); p=p-lchildlchild
13、; ; if (! if (!StackEmptyStackEmpty(S) Pop(S,p); p=p-(S) Pop(S,p); p=p-rchildrchild; ; while (p|! while (p|!StackEmptyStackEmpty(S);(S);return OK; return OK; YOUR LOGO HEREStatus Status InOrderTraverseInOrderTraverse( (BiTreeBiTree T, T,Status(*Visit)( Status(*Visit)(TElemTypeTElemType e) e) InitSta
14、ck InitStack(S); p=T;(S); p=T;do do while (p) Push(S,p); p=p- while (p) Push(S,p); p=p-lchildlchild; ; if (! if (!StackEmptyStackEmpty(S) (S) Pop(S,p); Pop(S,p);if (! Visit(p-data) return ERROR;if (! Visit(p-data) return ERROR; p=p- p=p-rchildrchild; ; while (p|! while (p|!StackEmptyStackEmpty(S);(S
15、);return OK; return OK; 中序遍历的非递归算法中序遍历的非递归算法YOUR LOGO HEREStatus Status PostOrderTraversePostOrderTraverse( (BiTreeBiTree T, T,Status(*Visit)( Status(*Visit)(TElemTypeTElemType e) e) InitStack InitStack(S); p=T;(S); p=T;do do while (p) Push(S,p,L); p=p- while (p) Push(S,p,L); p=p-lchildlchild; ; while (! while (!StackEmptyStackEmpty(S) Pop(S,p,tag); if (!Visit(p-data) return ERROR;if (!Visit(p-data) return ERROR; if (! if (!StackEm
