计算机组成与结构：DS and AL_Lecture6_Trees

《计算机组成与结构：DS and AL_Lecture6_Trees》由会员分享，可在线阅读，更多相关《计算机组成与结构：DS and AL_Lecture6_Trees（114页珍藏版）》请在金锄头文库上搜索。

1、DATASTRUCTURESANDALGORITHMSLectureNotes6buptsse2TREESTree Definitions and TerminologyBinary TreeBinary tree theoremBinary tree Implementation & examplesBinary tree traversalsTrees & Forest Tree Implementation & traversalsTree Converting to a binary treeHuffman TreeWhat is Huffman treeHuffman Code202

2、4/7/302024/7/303TREES DefinitionRecursive Definition : Tree is a collection of nodesA tree can be emptyA tree contains zero or more subtrees T1, T2, Tk connected to a root node by edges2024/7/304TREES: Terminology2024/7/305One natural way to define a tree is recursively. A tree is a collection of no

3、des. The collection can be empty; otherwise, a tree consists of a distinguished node r, called root, and zero or more nonempty (sub)trees T1, T2, Tk, each of whose roots are connected by a direct edge from r.TREES: Terminology2024/7/306Parent(双亲）Node A is the parent of node B, if B is the root of on

4、e subtree of A.Child（子节点）Node B is the child of node A, if A is the parent of B.Sibling（兄弟节点）Nodes with the same parent are siblingsLeaf（终端节点）A node is called a leaf if it has no childrenTREES: TerminologyABCDFGHIL2024/7/307Ancestor（祖先节点）Node A is an ancestor of node B, if A is either the parent of

5、B or is the parent of some ancestor of BDescendant（子孙节点）Node B is the descendant of node A, if A is an ancestor of node BTREES: Terminology2024/7/308Level of a Node（节点的层次）Level of the root of a tree is 1, and the level of any other nodes in the tree is one more than the level of its parentDepth of a

6、 Tree（深度或高度）The depth of a tree is the maximum level of any leaf in the tree (also called the height of the tree)Degree of a node（节点的度）The max-number of children Branch Node （分支节点 OR internal node） Any node of a tree that has child nodes( the number of child nodes is more than 0).TREES: Terminology2

7、024/7/309ADT TreeADT Tree Data objects :D = ai | aiElemset, (i=1,2,n, n0) Relationships of Data Elements: Recursive Definition of a tree Basic Operations: INITTREE（T）；）； DESTROYTREE（T）；）； ADT TreeTREES: Terminology2024/7/3010Basic Operations on a tree(1): INITTREE（T）；）； DESTROYTREE（T）；）； CREATETREE（

8、T，DEFINITION）；）； CLEARTREE（T）；）； ADT TreeADT Tree2024/7/3011Basic Operations on a tree(2): test a tree TREEEMPTY（T）;TREEDEPTH（T）; ROOT（T）; ADT TreeADT Tree2024/7/3012Basic Operations on a tree(3): Get the value of a node ASSIGN（T，CUR_E，VALUE）;PARENT（T，CURE）;LEFTCHILD（T，CURE）;RIGHTSIBLING（T，CURE）. AD

9、T TreeADT Tree2024/7/3013Basic Operations on a tree(4) INSERTCHILD（T，P，I，C）；DELETECHILD（T，P，I）； TRAVERSETREE（T，VISIT（）； (3) ADT TreeADT Tree2024/7/3014Binary TreesA binary tree is a tree in which no node can have more than two children. (a)Empty binary tree; (b) Binary tree with only one node；(c) Bi

10、nary without any right tree；(d) Binary with left and right trees； (e) Binary tree with no left tree。(a)A(b)A(c)A(d)A(e)2024/7/3015A full binary tree (满二叉树） of depth k is a binary tree of depth k having 2k -1 nodes. here k=0.Each node is either a leaf or internal node with exactly two non-empty child

11、ren.Binary Trees123456(a)7123456(b)12345(c)61234(d)5Abinarytreewithnnodesanddepthkiscomplete(完全二叉树）完全二叉树）iff itsnodescorrespondtothenodesnumberedfrom1toninthefullbinarytreeofdepthk.2024/7/3016Binary Trees Two special kinds of binary trees: (a) skewed tree, (b) complete binary treeThe all leaf nodes

12、of these trees are on two adjacent levels2024/7/3017Binary Trees Properties of binary treesMaximum number of nodes1.The maximum number of nodes on level i of a binary tree is 2i-1, i 1.2.The maximum number of nodes in a binary tree of depth k is 2k-1, k1.Relation between number of leaf nodes and deg

13、ree-2 nodes:For any nonempty binary tree, T, if n0 is the number of leaf nodes and n2 is the number of nodes of degree 2, then n0 = n2 + 1.2024/7/3018Binary Trees The height of a complete binary tree with n nodes is log2n +1 , X is the large integer less then X.2 k-1 -1 n = 2k - 1 Or 2k-1 = n 2k The

14、n：k - 1 log2n k k log2n 1。2024/7/3019Binary Trees Binary tree representations (using array)If a complete binary tree with n nodes is represented sequentially, then for any node with index i, 1 i n, we have1. parent(i) is at i /2 if i 1. If i = 1, i is at the root and has no parent.2. LeftChild(i) is

15、 at 2i if 2i n. If 2i n, then i has no left child.3. RightChild(i) is at 2i+1 if 2i+1 n. If 2i +1 n, then i has no right child2024/7/3020ABCDEF A B D - C - E - - - - - - F 0 1 2 3 4 5 6 7 8 9 10 11 12 131401326Binary tree representations (using array)2024/7/3021#define MAX_TREE_SIZE 100 / maximum nu

16、mber of nodestypedef TElemType BiTreeMAX_ TREE_SIZE; / Root NodeBiTree bt;Binary tree representations (using array)2024/7/3022Binary Trees Disadvantages of Binary tree representations (using array)Waste spaces: in the worst case, a skewed tree of depth k requires 2k-1 spaces. Of these, only k spaces

17、 will be occupiedInsertion or deletion of nodes from the middle of a tree requires the movement of potentially many nodes to reflect the change in the level of these nodes2024/7/3023Binary Trees representations (using array) voidCreateBiTree(SqBiTreeT)/*按按层层序次序序次序输输入二叉入二叉树树中中结结点的点的值值(字符型或整型字符型或整型),构

18、造构造顺顺序存序存储储的二叉的二叉树树T*/inti=0;InitBiTree(T);/*构造空二叉树构造空二叉树T*/printf(请按层序输入结点的值请按层序输入结点的值(整型整型)，0表示空结点，输表示空结点，输999结束。结点数结束。结点数%d:n,MAX_TREE_SIZE);while(1)scanf(%d,&Ti);if(Ti=999)Ti=Nil;break;i+;for(i=1;idata = ch ; CreateBiTree(T-lchild); CreateBiTree(T-rchild); return OK;/CreateBiTree2024/7/3028ADEBC

19、F root Triple Linked Listparent lchild data rchildNode2024/7/3029 typedef struct TriTNode / Node TElemType data; struct TriTNode *lchild, *rchild; / Left & Right Children struct TriTNode *parent; /Parent TriTNode, *TriTree;parent lchild data rchildNode:Node Structure2024/7/303030BinaryTreeLinkedBiTr

20、eeLinkedTripleTree2024/7/3031 Expression tree for (a+b*c) +(d*e+f)*g)Application of Binary Trees: Expression Trees2024/7/3032Algorithm to convert postfix expression into expression treee.g. input: ab+cde+*Application of Binary Trees: Expression Trees2024/7/3033 ab+cde+*Application of Binary Trees: E

21、xpression Trees2024/7/3034 Expression tree for (a+b*c) +(d*e+f)*g)Application of Binary Trees: Expression Trees2024/7/30353 methods of traversal preorder traversal strategy postorder traversal strategyinorder traversal strategyPreliminaries: Traversal Strategy2024/7/3036Preorder traversal (depth-fir

22、st order)A. If the tree is empty, do nothing，Otherwise do B:B. Do followings:1.Visit the root node2.Traverse the left subtrees in PreOrder3. Traverse the right subtrees in PreOrder A B C D F E GABCDGEFPreorder traversal (depth-first order)2024/7/3037Preorder Traverse Algorithm Status PreOrderTravers

23、e(BiTree T, Status(* Visit)(TElemType e) if (T) if (Visit(T-data) if (PreOrderTraverse(T-lchild,Visit) if (PreOrderTraverse(T-rchild,Visit) return OK; return ERROR; else return OK;/PreOrderTraverse2024/7/3038Postorder traversalA. If the tree is empty, do nothing，Otherwise do B:B. Do followings:1.Tra

24、verse the left subtrees in postorder2.Traverse the right subtrees in postorder2. Visit the root nodeABCDGEFC F D B G E APostorder Traverse Algorithm 2024/7/3039Status PostOrderTraverse(BiTree T, Status(* Visit)(TElemType e) if (T) if (PostOrderTraverse(T-lchild,Visit) if (PostOrderTraverse(T-rchild,

25、Visit) if (Visit(T-data) return OK; return ERROR; else return OK;/PostOrderTraversePostorder Traverse Algorithm 2024/7/3040Inorder traversal (symmetric order)A. If the tree is empty, do nothing，Otherwise do B:B. Do followings:1. Traverse the left subtree in inorder2. Visit the root node3. Traverse t

26、he right subtree in inorderABCDGEFCBDFAGEInorder Traverse Algorithm 2024/7/3041Inorder Traverse Algorithm (Recursive)Status InOrderTraverse(BiTree T, Status(* Visit)(TElemType e) if (T) if (InOrderTraverse(T-lchild,Visit) if (Visit(T-data) if (InOrderTraverse(T-rchild,Visit) return OK; return ERROR;

27、 else return OK;/InOrderTraverse2024/7/3042TRight NullReturnReturnReturnReturniod(T R);Mainiod( T )iod(T R);ACBDTBprintf(B);TAprintf(A);TDprintf(D);iod(T L);TCprintf(C);iod(T L);iod(T L);ReturnTLeft is Null, returniod(T R);TLeft NullTLeft NullTRight Nulliod(T R);Inorder Seq：B D A C42Traverse(Inorder

28、) Recursive：void iod(BiTree T) if (T!=NULL) iod(T-lchild); printf(T-data); iod(T-rchild); iod(T L);2024/7/3043void inorder(BiTree T) InitStack(S); p=T; while(p|!SatckEmpty(S) if (p) Push(p); p=p-lchild; else Pop(p); printf(p-data);p=p-rchild); Non_recursive：432024/7/3044ABCDEFGpiP-A(1)ABCDEFGpiP-AP-

29、B(2)ABCDEFGpiP-AP-BP-C(3)p=NULLABCDEFGiP-AP-BVisit：C(4)442024/7/3045pABCDEFGiP-AVisited：C B(5)ABCDEFGiP-AP-DVisited：C Bp(6)ABCDEFGiP-AP-DP-EVisited：C Bp(7)ABCDEFGiP-AP-DVisited：C B Ep(8)452024/7/3046ABCDEFGiP-AP-DP-GVisited：C B EP=NULL (9)ABCDEFGiP-AVisited：C B E G Dp(11)ABCDEFGiP-AP-Fvisited：C B E

30、G Dp(12)ABCDEFGiP-AP-DVisited：C B E Gp(10)462024/7/3047ABCDEFGiP-AVisited：C B E G D Fp=NULL(13)ABCDEFGiVisited：C B E G D F Ap(14)ABCDEFGiVisited：C B E G D F Ap=NULL(15)472024/7/3048Examples1、Count down the number of leaf node (preorder) 2、Get the depth of binary Tree (Postorder)2024/7/3049Count the

31、leaf node numberIdea about Algorithm:Idea about Algorithm: 1) Preorder(inorder or postorder) Traverse binary tree, look for leaf node in the traverse process and count the number of leaf node. 2) Setup one parameter to count the leaf node. 3) In visit function, if it is leaf, the count number +.Exam

32、ples2024/7/3050void CountLeaf (BiTree T, int& count) if ( T ) if (!T-lchild)& (!T-rchild) count+; / Count down leaf node CountLeaf( T-lchild, count); CountLeaf( T-rchild, count); / if / CountLeafExamples2024/7/3051Get the depth of binary tree (Postorder) Idea about algorithm Idea about algorithm1)Ge

33、t the depth of left subtree and right tree ;2) Get maximum value of depth 3) max_depth +; The depth of tree is the maximum of depth of left subtree and right subtreeExamples2024/7/3052intdepth(BiTreet)intdep1,dep2;if(t=NULL)return(0);elsedep1=depth(t-lchild);dep2=depth(t-rchild);if(dep1dep2)return(d

34、ep1+1);elsereturn(dep2+1);2024/7/3053+-H/*+*E-ABCDFGPreorder: +-/+AB*CD*E-FGHInorder : A+B/C*D-E*F-G+HPostorder: AB+CD*/EFG-*-H+Examples2024/7/3054The nodes of binary tree such as followings, display binary tree Preorder sequence：A B C D E F GInorder sequence：C B E D A F GACBEDFGABCDEFGABCFDEGExampl

35、e2024/7/3055The node sequence of binary tree such as followings, Preorder sequence：A B Postorder sequence：B AThanking In followingsPleaseDisplaytheTree?ABAB2024/7/3056Threaded Binary Trees ThreadsDo you find any drawback of the above tree?Too many null pointers in current representation of binary tr

36、eesn: number of nodesnumber of non-null links: n-1total links: 2nnull links: 2n-(n-1) = n+1Solution: replace these null pointers with some useful “threads”2024/7/3057Threaded Binary Trees Rules for constructing the threadsIf ptr-left_child is null, replace it with a pointer to the node that would be

37、 visited before ptr in an inorder traversalIf ptr-right_child is null, replace it with a pointer to the node that would be visited after ptr in an inorder traversal2024/7/3058Threaded Binary Trees A Threaded Binary TreeACGIDHFdanglingdanglingH D I B E A F C Ginorder traversal:EttBfft: true threadf:

38、false childroot2024/7/3059Threaded Binary Trees Two additional fields of the node structure, left-thread and right-threadIf ptr-left-thread=TRUE, then ptr-left-child contains a thread; Otherwise it contains a pointer to the left child.Similarly for the right-thread2024/7/3060Threaded Binary Trees If

39、 we dont want the left pointer of H and the right pointer of G to be dangling pointers, we may create root node and assign them pointing to the root node2024/7/3061Inorder Threaded Binary Trees -+a*e/-fbdcNILNILb*11 + /f00 e 2024/7/3062Look for predecessor and successor in Inorder Threaded Binary Tr

40、ees62pR1R2Rk最左下结点BiThrNode *nextnode(BiThrNode *p) if(p-Rtag) return(p-rchild); next=p-rchild; / 查找右子树的最左结点 while(!next-Ltag) next=next-lchild; return(next);2024/7/3063pL1L2Lk最右下结点BiThrNode *priornode(BiThrNode *p) if(p-Ltag) return(p-lchild); pre=p-lchild; / 查找左子树的最右结点 while(!pre-Rtag) pre=pre-rchi

41、ld; return(pre);632024/7/3064Inorder threaded binary tree/ implimentation of threaded binary treetypedef enum Link,Thread / PointerTag; Link=0: Pointer,Thread=1:Threadtypedef struct BiThrNode TElemType data; struct BiThrNode *lchild,*rchild; /The pointers of left and right children PointerTag LTag,

42、RTag; /signsBiThrNode, *BiThrTree;2024/7/3065Inorder threaded binary treevoidCreateBiThrTree(BiThrTree*T)/*按先序输入线索二叉树中结点的值，构造线索二叉树按先序输入线索二叉树中结点的值，构造线索二叉树T。(整型整型)/空格空格(字符字符型型)表示空结点表示空结点*/TElemTypech;scanf(form,&ch);if(ch=Nil)*T=NULL;else*T=(BiThrTree)malloc(sizeof(BiThrNode);/*生成根结点生成根结点(先序先序)*/if(!*

43、T)exit(OVERFLOW);(*T)-data=ch;/*给根结点赋植给根结点赋植*/CreateBiThrTree(&(*T)-lchild);/*递归构造左子树递归构造左子树*/if(*T)printf(%c,(*T)-data);if(*T)-lchild)/*有左孩子有左孩子*/(*T)-LTag=Link;/*给左标志赋值给左标志赋值(指针指针)*/CreateBiThrTree(&(*T)-rchild);/*递归构造右子树递归构造右子树*/if(*T)-rchild)/*有右孩子有右孩子*/(*T)-RTag=Link;/*给右标志赋值给右标志赋值(指针指针)*/ABCDE

44、Thrt 0 1prepStatus InOrderThreading(BiThrTree &Thrt, BiThrTree T) / Thrt point to node, use pre and p /as global variables to /record the thread if (!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode) exit (OVERFLOW); Thrt-LTag=Link; Thrt-RTag=Thread; /head node/右指针回指右指针回指 Thrt-rchild=Thrt; /若二叉树空，则左指针回指若二叉树

45、空，则左指针回指if (!T)Thrt-lchild=Thrt; elseThrt-lchild=T; pre=Thrt; /中序遍历进行中序线索化中序遍历进行中序线索化 InThreading(T); pre-rchild=Thrt; /最后一个结点线索化最后一个结点线索化 pre-RTag=Thread; Thrt-rchild=pre; return OK;/InOrderThreading A B D C ET000000000066Inorder threaded binary treeABCDE A B D C ETThrt 0 1prepvoid InThreading(BiTh

46、rTree p) / 一个全程指针一个全程指针pre if (p) /左子树线索化左子树线索化 InThreading(p-lchild); if (!p-lchild) /前驱线索前驱线索 p-LTag=Thread; p-lchild=pre; if (!pre-rchild) /后继线索后继线索 pre-RTag=Thread; pre-rchild=p; /保持保持pre指向指向p的前驱的前驱 pre=p; /右子树线索化右子树线索化 InThreading(p-rchild); /InThreading000000000067ABCDE A B D C ETThrt 0 1prep=

47、NULL000000000068void InThreading(BiThrTree p) / 一个全程指针一个全程指针pre if (p) /左子树线索化左子树线索化 InThreading(p-lchild); if (!p-lchild) /前驱线索前驱线索 p-LTag=Thread; p-lchild=pre; if (!pre-rchild) /后继线索后继线索 pre-RTag=Thread; pre-rchild=p; /保持保持pre指向指向p的前驱的前驱 pre=p; /右子树线索化右子树线索化 InThreading(p-rchild); /InThreadingABCD

48、E A B D C ETThrt 0 1prep0000000000169void InThreading(BiThrTree p) / 一个全程指针一个全程指针pre if (p) /左子树线索化左子树线索化 InThreading(p-lchild); if (!p-lchild) /前驱线索前驱线索 p-LTag=Thread; p-lchild=pre; if (!pre-rchild) /后继线索后继线索 pre-RTag=Thread; pre-rchild=p; /保持保持pre指向指向p的前驱的前驱 pre=p; /右子树线索化右子树线索化 InThreading(p-rchi

49、ld); /InThreadingABCDE A B D C ETThrt 0 1prep000010000070void InThreading(BiThrTree p) / 一个全程指针一个全程指针pre if (p) /左子树线索化左子树线索化 InThreading(p-lchild); if (!p-lchild) /前驱线索前驱线索 p-LTag=Thread; p-lchild=pre; if (!pre-rchild) /后继线索后继线索 pre-RTag=Thread; pre-rchild=p; /保持保持pre指向指向p的前驱的前驱 pre=p; /右子树线索化右子树线索

50、化 InThreading(p-rchild); /InThreadingABCDE A B D C ETThrt 0 1prep=NULL000010000071void InThreading(BiThrTree p) / 一个全程指针一个全程指针pre if (p) /左子树线索化左子树线索化 InThreading(p-lchild); InThreading(p-lchild); if (!p-lchild) /前驱线索前驱线索 p-LTag=Thread; p-lchild=pre; if (!pre-rchild) /后继线索后继线索 pre-RTag=Thread; pre-r

51、child=p; /保持保持pre指向指向p的前驱的前驱 pre=p; /右子树线索化右子树线索化 InThreading(p-rchild); /InThreadingABCDE A B D C ETThrt 0 1prep0000100000172void InThreading(BiThrTree p) / 一个全程指针一个全程指针pre if (p) /左子树线索化左子树线索化 InThreading(p-lchild); if (!p-lchild) /前驱线索前驱线索 p-LTag=Thread; p-lchild=pre; if (!pre-rchild) /后继线索后继线索 p

52、re-RTag=Thread; pre-rchild=p; /保持保持pre指向指向p的前驱的前驱 pre=p; /右子树线索化右子树线索化 InThreading(p-rchild); /InThreadingABCDE A B D C ETThrt 0 1prep=NULL000010101073void InThreading(BiThrTree p) / 一个全程指针一个全程指针pre if (p) /左子树线索化左子树线索化 InThreading(p-lchild); if (!p-lchild) /前驱线索前驱线索 p-LTag=Thread; p-lchild=pre; if

53、(!pre-rchild) /后继线索后继线索 pre-RTag=Thread; pre-rchild=p; /保持保持pre指向指向p的前驱的前驱 pre=p; /右子树线索化右子树线索化 InThreading(p-rchild); /InThreadingABCDE A B D C ETThrt 0 1prep0000100010174void InThreading(BiThrTree p) / 一个全程指针一个全程指针pre if (p) /左子树线索化左子树线索化 InThreading(p-lchild); if (!p-lchild) /前驱线索前驱线索 p-LTag=Thre

54、ad; p-lchild=pre; if (!pre-rchild) /后继线索后继线索 pre-RTag=Thread; pre-rchild=p; /保持保持pre指向指向p的前驱的前驱 pre=p; /右子树线索化右子树线索化 InThreading(p-rchild); /InThreadingABCDE A B D C ETThrt 0 1ppre000010101075void InThreading(BiThrTree p) / 一个全程指针一个全程指针pre if (p) /左子树线索化左子树线索化 InThreading(p-lchild); if (!p-lchild) /

55、前驱线索前驱线索 p-LTag=Thread; p-lchild=pre; if (!pre-rchild) /后继线索后继线索 pre-RTag=Thread; pre-rchild=p; /保持保持pre指向指向p的前驱的前驱 pre=p; /右子树线索化右子树线索化 InThreading(p-rchild); /InThreadingABCDE A B D C ETThrt 0 1ppre000010101076void InThreading(BiThrTree p) / 一个全程指针一个全程指针pre if (p) /左子树线索化左子树线索化 InThreading(p-lchil

56、d); if (!p-lchild) /前驱线索前驱线索 p-LTag=Thread; p-lchild=pre; if (!pre-rchild) /后继线索后继线索 pre-RTag=Thread; pre-rchild=p; /保持保持pre指向指向p的前驱的前驱 pre=p; /右子树线索化右子树线索化 InThreading(p-rchild); /InThreadingABCDE A B D C ETThrt 0 1p=NULLpre000010101077void InThreading(BiThrTree p) / 一个全程指针一个全程指针pre if (p) /左子树线索化左

57、子树线索化 InThreading(p-lchild); if (!p-lchild) /前驱线索前驱线索 p-LTag=Thread; p-lchild=pre; if (!pre-rchild) /后继线索后继线索 pre-RTag=Thread; pre-rchild=p; /保持保持pre指向指向p的前驱的前驱 pre=p; /右子树线索化右子树线索化 InThreading(p-rchild); /InThreadingABCDE A B D C ETThrt 0 1ppre0000101010 178void InThreading(BiThrTree p) / 一个全程指针一个全

58、程指针pre if (p) /左子树线索化左子树线索化 InThreading(p-lchild); if (!p-lchild) /前驱线索前驱线索 p-LTag=Thread; p-lchild=pre; if (!pre-rchild) /后继线索后继线索 pre-RTag=Thread; pre-rchild=p; /保持保持pre指向指向p的前驱的前驱 pre=p; /右子树线索化右子树线索化 InThreading(p-rchild); /InThreadingABCDE A B D C ETThrt 0 1p=NULLpre000010101179void InThreading

59、(BiThrTree p) / 一个全程指针一个全程指针pre if (p) /左子树线索化左子树线索化 InThreading(p-lchild); if (!p-lchild) /前驱线索前驱线索 p-LTag=Thread; p-lchild=pre; if (!pre-rchild) /后继线索后继线索 pre-RTag=Thread; pre-rchild=p; /保持保持pre指向指向p的前驱的前驱 pre=p; /右子树线索化右子树线索化 InThreading(p-rchild); /InThreadingABCDE A B D C ETThrt 0 1ppre00001010

60、11180void InThreading(BiThrTree p) / 一个全程指针一个全程指针pre if (p) /左子树线索化左子树线索化 InThreading(p-lchild); if (!p-lchild) /前驱线索前驱线索 p-LTag=Thread; p-lchild=pre; if (!pre-rchild) /后继线索后继线索 pre-RTag=Thread; pre-rchild=p; /保持保持pre指向指向p的前驱的前驱 pre=p; /右子树线索化右子树线索化 InThreading(p-rchild); /InThreadingABCDE A B D C E

61、TThrt 0 1p=NULLipre0000101111181Status InOrderThreading(BiThrTree &Thrt, BiThrTree T) / Thrt point to node, use pre and p /as global variables to /record the thread if (!(Thrt=(BiThrTree) malloc(sizeof(BiThrNode) exit (OVERFLOW); Thrt-LTag=Link; Thrt-RTag=Thread; /head node/右指针回指右指针回指 Thrt-rchild=Th

62、rt; /若二叉树空，则左指针回指若二叉树空，则左指针回指if (!T)Thrt-lchild=Thrt; elseThrt-lchild=T; pre=Thrt; /中序遍历进行中序线索化中序遍历进行中序线索化 InThreading(T); pre-rchild=Thrt; /最后一个结点线索化最后一个结点线索化 pre-RTag=Thread; Thrt-rchild=pre; return OK;/InOrderThreading2024/7/3082Modify Binary list into inorder threaded list 1 2 3 4 5 6 7 8 9 10 1

63、1 12 13 142024/7/3083The tree of the exampleThrt10 1234567891011121314ABDEFCHIGKJMNL2024/7/3084Tree & ForestA forest is a set of n = 0 disjoint treesAEGBCDFHIGHIABCDFEForest2024/7/3085Trees Implementation1) Parent Pointer ImplementationAdvantage:lookupparenteasilyAdvantage:lookupparenteasily2024/7/3

64、086Form1:Form1:Form2:Form2: data child1child2child3childd data child2childdechild1degreeProblem:nodesstructureisinconsistentProblem:nodesstructureisinconsistent2) Lists of ChildrenProblem:NullpointerswastespaceProblem:NullpointerswastespaceSolution:ListsofChildrenSolution:ListsofChildren2024/7/3087E

65、xample：abcdefhgi6012345789acdefghibdatafc 2 3 4 5 9 7 8 6How to lookup parent2024/7/3088Lists of children with parent612345789acdefghibdatafc 2 3 4 5 9 7 8 6012235551parentabcdefhgi2024/7/3089 datafirstChildnextSibling3) Leftmost Child/Right Sibling Each node contains three parts: a data field and t

66、wo pointer to its leftmost child and right sibling.abcdefhgi a b c d e f g h i2024/7/3090Implementation of Leftmost Child/Right Sibling typedef struct TreeNode * PtrToNode;struct TreeNodeElementType element;PtrToNode FirstChild;PtrToNode NextSibling;FirstChild pointer: arrow that points downwardNext

67、Sibling pointer: arrow that goes left to right2024/7/3091 Implementation of Leftmost Child/Right Sibling 2024/7/3092Unix File System Implementation of a Tree2024/7/3093Unix File SystemStatic void ListDir(DirectoryOrFile D, int Depth)if (D is a legitimate entry)PrintName(D, Depth);if (D is a director

68、y)for each child, C, of DListDir(C, Depth +1); void ListDirectory(DirectoryOrFile D) ListDir(D, 0); Implementation of a Tree2024/7/3094Unix File SystemStatic int SizeDirectory(DirectoryOrFile D) int TotalSize = 0;if (D is a legitimate entry) TotalSize = FileSize(D); if (D is a directory) for each ch

69、ild, C, of D TotalSize += SizeDirectory(C); return TotalSize; Implementation of a Tree2024/7/3095 Converting to a Binary TreeACBEDTreeABCDEBinary tree A B C D E A B C D E A B C D E Any tree can be transformed into binary treeAny tree can be transformed into binary treecorrespondingstoragestoragestor

70、agestorage2024/7/30961)Transform a tree into a binary treeABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI2024/7/30972)Transform a forest into a binary treeABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ2024/7/30981) Keep current root node and its left sub tree as one of the tree of the forest, the right sub

71、tree as the other trees.2) Repeat step 1) until the right subtree in the node is empty. JIHGFEBCDAT1BCDAFET2T3JIHG3)Transform a binary tree into forest 2024/7/30994)Transform a binary tree into tree ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI2024/7/30100 General Tree Traversal(1)1) Tree traversalP

72、reorder: If the tree is not empty, visit the root and traverse the subtrees in preorder.Postorder: If the tree is not empty, traverse all subtrees of the root in postorder, then visit the root of the tree.ABCDEFGHIJExample：PreorderPreorder：ABEFCGDHIJABEFCGDHIJPostorderPostorder：EFBGCHIJDAEFBGCHIJDA2

73、024/7/30101Tree traverse in preorder Corresponding binary tree traverse in preorder.Tree traverse in postorder Corresponding binary tree traverse in Inorder.ABCDEFGHIJABCDEFGHIJTree Preorder(Binary tree Preorder): ABEFCGDHIJ ABEFCGDHIJ Tree Postorder(Tree Postorder(Binary tree Inorder ):EFBGCHIJDAEF

74、BGCHIJDA General Tree Traversal(2)2024/7/301022）ForestTraversals Preorder If F is empty, then return Visit the root of the first tree of F Traverse the subtrees of the first tree in tree preorder Traverse the remaining trees of F in preordern Inorder (similar PostOrder in Tree) If F is empty, then r

75、eturn Traverse the subtrees of the first tree in tree inorder (PostOrder in Tree). Visit the root of the first tree Traverse the remaining trees of F is indorer(PostOrder in Tree).2024/7/30103Forest traverse in preorder Corresponding binary tree traverse in preorder.Forest traverse in Inorder Corres

76、ponding binary tree traverse in Inorder.PreorderPreorder：ABCDEFGHIKJABCDEFGHIKJInorderInorder： BCEDAGFKIJHBCEDAGFKIJH2024/7/30104Huffman TreeVery often used for text compressionDo you know how gzip or winzip works? Compression methodsASCII code uses codes of equal length for all letters how many cod

77、es?Todays alternative to ASCII?Idea behind Huffman code: use shorter length codes for letters that are more frequent2024/7/30105Huffman Tree(Optional Binary Tree) 1) What is a Huffman tree? Path Length: Path Length: The The lengthlength of path is the number of path is the number of edges on the pat

78、h.of edges on the path.2024/7/30106 Weighted Path Length, WPL Weighted Path Length, WPL 2dcab475WPL=7*3+5*3+2*1+4*2=46n n w wi i is the weight of the i-th leaf; is the weight of the i-th leaf;n n l li i is the path length from root to is the path length from root to the i-th leafthe i-th leaf Huffma

79、n Tree: Huffman Tree: the binary tree the binary tree with the with the minimumminimum weighted path weighted path length.length.2024/7/30107Fixed Length CodesRepresent data as a sequence of 0s and 1sSequence: BACADAEAFABBAAAGAH (18 characters)A 000 B 001 C 010 D 011E 100 F 101 G 110 H 1110010000100

80、00011000100000101000001001000000000110000111The Encoding is 18x3=54 bits long. Can we make the encoding shorter?A fixed length code:Encoding of sequence:2024/7/30108Variable Length CodeA 0 B 100 C 1010 D 1011E 1100 F 1101 G 1110 H 1111Example: BACADAEAFABBAAAGAH10001010010110110001101010010000011100

81、1111Make use of frequencies. Frequency of A=8, B=3, others 1. But how do we decode? 42 bits (20% shorter)2024/7/30109Prefix code Binary treeA 0 B 100 C 1010 D 1011E 1100 F 1101 G 1110 H 1111Prefix code: No codeword is a prefix of any other codewordABCDEFGH011110000001112024/7/30110Decoding Example10

82、001010ABCDEFGH0111100000011110001010 B10001010 BA10001010 BAC2024/7/30111Huffman Tree = Optimal Length CodeOptimal: no code has better weighted average lengthABCDEFGH0111100000011183111111ADBCEFGH01111000000111831111112024/7/30112Huffmans AlgorithmBuild tree bottom-up, so that lowest weight leaves a

83、re farthest from the root. Repeatedly: Find two trees of lowest weight. merge them to form a new tree whose weight is the sum of their weights.2024/7/30113Construction of Huffman treeABCDEFGH83111111222459172024/7/30114PointsLevelPercentage059 6069 7079 8089 90100 E D C B A0.05 0.15 0.40 0.30 0.10 a60 a70 a80 a90EDCBAYNNNNYYY70 a80CBEADYNYYN80 a9060 a70 a60 a80 a70 a90 a60EDCABNNNNNNYYYYDeterminantTree：WPL=(0.05*1+0.15*2+0.4*3+0.3*4+0.1*4)=3.15WPL=0.4*1+0.3*2+0.05*4+0.1*4+0.15*3=2.05WPL=2.2114