数据结构总结.docx

本文格式为Word版，下载可任意编辑数据结构总结 完全二叉树的依次存储： A2B1C34DE56FG7HIJKL89101112 ABCDEFGHIJKL 0 1 2 3 4 5 6 7 8 9 10 11 12 一般二叉树的依次存储： 把一般的二叉树先补成完全二叉树，然后按照完全二叉树的依次存储方式举行存储，而新补上去的结点只占位置，不存放结点数据 ABCD(a) 右偏斜二叉树AABCD(b) 补全后的完全二叉树 DBC (c) 右偏斜二叉树的依次存储示意图 二叉树的链式存储布局： 二叉链表： 二叉树的遍历： 顺着某一条探寻路径巡访二叉树中的节点，使得每个节点均被访问一次，而且仅被访问一次 常见的遍历方式有： 递归遍历，层次遍历，非递归遍历 树的遍历常用方法： 先序遍历：先访问树的根节点，然后先序访问左子树，结果先序访问右子树 中序遍历：先中序遍历左子树，然后访问根节点，结果中序访问右子树 后序遍历：先后序遍历左子树，然后后序遍历右子树，结果访问根节点 按层次遍历：先访问第一次上的节点，然后依次遍历其次层。

先序遍历的递归算法： void PreOrder( BiTree bt) { if (bt!=NULL){ /* 假设bt为空，终止*/ visit (bt->data); /*访问根结点*/ PreOrder( bt->lchild); /*先序遍历左子树（递归调用）*/ PreOrder (bt->rchild); /*先序遍历右子树（递归调用）*/ } } 中序遍历的递归算法： void InOrder( BiTree bt) { if (bt!=NULL){ /* 假设bt为空，终止*/ InOrder( bt->lchild); /*中序遍历左子树（递归调用）*/ visit (bt->data); /*访问根结点*/ InOrder (bt->rchild); /* 中序遍历右子树（递归调用）*/ } } 后序遍历的递归算法： void PostOrder( BiTree bt) { if (bt!=NULL){ /* 假设bt为空，终止*/ PostOrder( bt->lchild); /*后序遍历左子树（递归调用）*/ PostOrder (bt->rchild); /* 后序遍历右子树（递归调用）*/ visit (bt->data); /*访问根结点*/ } } 中序遍历非递归算法： void NRInOrder(BiTree bt){ BiTree S[MAXNODE], p=bt; /*定义栈S*/ int top=-1; if (bt==NULL) return; /*空二叉树，遍历终止*/ while(!(p==NULL /*当前指针p进栈*/ Else { printf(“栈溢出\\n”); return; } p=p->lchild; /*指标指向p的左孩子结点*/ } if(top==-1) return; /*栈空时终止*/ else { p=S[--top]; /*弹出栈顶元素*/ visit(p->data); /*访问结点的数据域*/ p=p->rchild; /*指向p的右孩子结点*/ } } } 线索二叉树： 节点布局： 规定：若节点有左孩子，那么其lchild指示其左孩子，否那么，令lchild域指示其前驱；若节点有右孩子，那么其rchild指示其右孩子，否那么，令rchild域指示其后继。

布局： lchildLTagdataRTagrchild typedef struct BiThrNode{ Datatype data; struct BiThrNode *lchild, *rchild; byte LTag, RTag; }BiThrNode, *BiThrTree; ?0 lchild 域指示结点的左孩子LTag=??1 lchild域指示结点的前驱?0 rchild域指示结点的右孩子RTag=??1 rchild域指示结点的后继 以以下结点布局构成的二叉链表作为二叉树的存储布局，叫做线索链表，其中指向前驱和后继的指针，叫做线索（Thread）加上线索的二叉树叫做线索二叉树（Thread Binary Tree）对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化 二叉排序树： 二叉排序树的任意节点大于左孩子，小于右孩子 78543723456585828794 二叉平衡树： 二叉平衡树的每个节点的左右子树深度之差不超过1 哈夫曼树： 带权路径长度最短的树 树和森林： 树转化为二叉树： A对应BECFGD存储A∧∧BA∧∧BEC∧F∧D∧∧G∧解释C∧D∧∧E∧F∧G∧E∧F∧G∧解释存储BCEFGA∧∧BC∧D∧DA 二叉树转化为树： 加线：将结点和其左孩子结点的右孩子以及右孩子的右孩子加线相连 抹线：去掉结点和右孩子的连线 旋转：将加线、去线后的结果，举行旋转处理，就得到转换后的树 — 5 —。