《数据结构复习笔记-树和二叉树》由会员分享，可在线阅读，更多相关《数据结构复习笔记-树和二叉树（12页珍藏版）》请在金锄头文库上搜索。
1、1 树和二叉树树和二叉树 一、一、基础知识和算法基础知识和算法 1. 1. 1. 1. 树及有关概念树及有关概念 树，根，子树；结点，结点的度，叶子（终端结点） ，分支结点（非终端结点） ，内部结点， 树的度；孩子，双亲，兄弟，祖先，子孙，堂兄弟；层次（根所在层为第 1 层） ，深度，高 度；有序树，无序树，二叉树是有序树；森林。 2. 2. 2. 2. 二叉树二叉树 二叉树（二叉树与度为 2 的树不同，二叉树的度可能是 0，1，2） ；左孩子，右孩子。 二叉树的五种基本形态。 3. 3. 3. 3. 二叉树的性质二叉树的性质 1.二叉树的第 i 层1上至多有 2i-1个结点。 2.深度为 k
2、 的二叉树至多有 2k-1 个结点。 满二叉树：深度为 k，有 2k-1 个结点。 完全二叉树：给满二叉树的结点编号，从上至下，从左至右，n 个结点的完全二叉树中结 点在对应满二叉树中的编号正好是从 1 到 n。 3.叶子结点 n0，度为 2 的结点为 n2，则 n0= n2+1。 考虑结点个数：n = n0+ n1+ n2 考虑分支个数：n-1 = 2n2+ n1 可得 n0= n2+1 例：1) 二叉树有 n 个叶子，没有度为 1 的结点，共有个结点。 2) 完全二叉树的第 3 层有 2 个叶子，则共有个结点。 分析：1) 度为 2 的结点有 n-1 个，所以共 2n-1 个结点。 2)
3、注意考虑到符合条件的二叉树 的深度可能是 3 或 4，所以有 5、10 或 11 个结点。 1 本书中约定根结点在第 1 层，也有约定根在第 0 层的，则计算公式会有所不同。 2 4.n 个结点的完全二叉树深度为 1log+n。 5.n 个结点的完全二叉树，结点按层次编号 有：i 的双亲是 2/n，如果 i = 1 时为根（无双亲） ； i 的左孩子是 2i，如果 2in，则无左孩子； i 的右孩子是 2i + 1，如果 2i + 1n 则无右孩子。 完全二叉树的特点： 深度为 k 的完全二叉树的叶子结点只可能在第 k 及第 k-1 层出现 任一结点，其右子树的深度为 L， 则其左子树的深度必
4、为 L 或 L+1 4. 4. 4. 4. 二叉树的存储结构二叉树的存储结构 1.顺序存储结构（无情的藐视掉） 用数组、编号 i 的结点存放在i-1处。适合于存储完全二叉树。 2.链式存储结构 二叉链表： /-/-/-/- - - - - - - - - - - - - - -二叉树的二叉链表存储表示二叉树的二叉链表存储表示- - - - - - - - - - - - - - - - - - typedeftypedeftypedeftypedefstructstructstructstructBiTNodeBiTNodeBiTNodeBiTNode TElemTypeTElemTypeTE
5、lemTypeTElemTypedata;data;data;data; structstructstructstruct BiTNodeBiTNodeBiTNodeBiTNode*lchild,*lchild,*lchild,*lchild, *rchild;*rchild;*rchild;*rchild;/左右孩子指针左右孩子指针 BiTNode,BiTNode,BiTNode,BiTNode, *BiTree;*BiTree;*BiTree;*BiTree; 三叉链表： （有条件的藐视掉） typedeftypedeftypedeftypedefstructstructstructstr
6、uct BiTNode DataType data; structstructstructstruct TNode *lchild, *rchild, *parent; BiTNode, *BiTree; data parentlchildrchilddatarchildlchild 例：用二叉链表存储 n 个结点的二叉树(n0)，共有(_a_)个空指针域；采用三叉链表存储， 共有(_b_)个空指针域。2 2 答案：(a) n+1 (b) n+2。提示：只有根结点没有双亲。 3 5. 5. 5. 5. 二叉树的五种基本形态二叉树的五种基本形态 空树：T=NULL左右子树均空：T-lchild=
7、NULL andandandandT-rchild=NULL 右子树为空：T-rchild=NULL左子树为空：T-lchild=NULL 左右子树均非空。 前两种常作为递归结束条件，后三者常需要递归。 6. 6. 6. 6. 遍历二叉树遍历二叉树 1.常见有四种遍历方式 按层次遍历，先序遍历，中序遍历，后序遍历。 按层次遍历： “从上至下，从左至右” ，利用队列。 先序遍历：DLR；中序遍历：LDR；后序遍历 LRD。 例：写出 a+b*(c-d)-e/f 的前缀、中缀和后缀表达式。 画出二叉树，分别进行前序、中序、后序遍历即可得到。 前缀表达式：- + a * b - c d / e f
8、中缀表达式：a + b * c - d - e / f 后缀表达式：a b c d - * + e f / - 2.先序遍历算法 voidvoidvoidvoid Preorder ( BiTree T ) if if if if ( T ) visit ( T-data ); Preorder ( T-lchild ); Preorder ( T-rchild ); 3.中序遍历算法 voidvoidvoidvoid Inorder ( BiTree T ) if if if if ( T ) Inorder ( T-lchild ); visit ( T-data ); Inorder (
9、 T-rchild ); - +/ a* b- cd ef 4 4.后序遍历 voidvoidvoidvoid Postorder ( BiTree T ) if if if if ( T ) Postorder ( T-lchild ); Postorder ( T-rchild ); visit ( T-data ); 分析： 1、三种算法的区别就是 if 里三个语句的顺序不同 2、根据应用简单的改变程序 方法：通过设置全局变量，把 visit 语句替换成相应的操作 3、考试时如果实在不会改，就把遍历程序写出来。 见后面的二叉树应用的例题 5.按层次遍历 思路：利用一个队列，首先将根（头指
10、针）入队列，以后若队列不空则取队头元素 p，如果 p 不空，则访问之，然后将其左右子树入队列，如此循环直到队列为空。 voidvoidvoidvoid LevelOrder ( BiTree T ) / 队列初始化为空 InitQueue ( Q ); / 根入队列 EnQueue ( Q, T ); / 队列不空则继续遍历 whilewhilewhilewhile ( ! QueueEmpty(Q) ) DeQueue ( Q, p ); if if if if ( p!=NULL ) visit ( p-data ); / 左、右子树入队列 EnQueue ( Q, p-lchild );
11、 EnQueue ( Q, p-rchild ); 若队列表示为“数组 q + 头尾 front, rear”有： voidvoidvoidvoid LevelOrder ( BiTree T ) constconstconstconstintintintintMAXSIZE = 1024; BiTree qMAXSIZE; 5 intintintintfront,rear; / 队列初始化为空 front = rear = 0; / 根入队列 qrear =T;rear = ( rear+1 ) % MAXSIZE; / 队列不空则循环 whilewhilewhilewhile ( fron
12、t != rear ) p = qfront;front = ( front+1 ) % MAXSIZE; if if if if ( p ) visit ( p-data ); / 左、右子树入队列 qrear = p-lchild;rear = ( rear+1 ) % MAXSIZE; qrear = p-rchild;rear = ( rear+1 ) % MAXSIZE; 6.非递归遍历二叉树 一般借助栈实现。设想一指针沿二叉树中序顺序移动，每当向上层移动时就要出栈。 中序非递归遍历最最重要，后面的两个用于提高。 (a) 中序非递归遍历 指针 p 从根开始，首先沿着左子树向下移动，同
13、时入栈保存；当到达空子树后需要退栈访问 结点，然后移动到右子树上去。 voidvoidvoidvoid InOrder ( BiTreeT,VisitFunc visit ) InitStack ( S ); p =T; whilewhilewhilewhile ( p | ! StackEmpty(S) ) if if if if ( p ) Push ( S, p ); p = p-lchild; elseelseelseelse Pop ( S, p ); visit ( p );/ 中序访问结点的位置 p = p-rchild; (b) 先序非递归遍历 按照中序遍历的顺序，将访问结点的
14、位置放在第一次指向该结点时。 voidvoidvoidvoid Preorder ( BiTreeT,VisitFunc visit ) InitStack ( S ); p =T; 6 whilewhilewhilewhile ( p | ! StackEmpty(S) ) if if if if ( p ) visit ( p );/ 先序访问结点的位置 Push ( S, p ); p = p-lchild; elseelseelseelse Pop ( S, p ); p = p-rchild; 或者，由于访问过的结点便可以弃之不用，只要能访问其左右子树即可，写出如下算法。 voidv
15、oidvoidvoid Preorder ( BiTreeT,VisitFunc visit ) InitStack ( S ); Push ( S, T ); whilewhilewhilewhile ( ! StackEmpty(S) ) Pop ( S, p ); if if if if ( p ) visit ( p ); Push ( S, p-rchild );/ 先进栈，后访问，所以 Push ( S, p-lchild );/这里先让右子树进栈 (c) 后序非递归遍历 后序遍历时， 分别从左子树和右子树共两次返回根结点， 只有从右子树返回时才访问根结点， 所以增加一个栈标记到达结点的次序。 voidvoidvoidvoid PostOrder ( BiTreeT,VisitFunc visit ) InitStack ( S ),InitStack ( tag ); p =T; whilewhilewhilewhile ( p | ! StackEmpty(S) ) if if if if ( p ) Push ( S, p ),Push ( tag, 1);/ 第一次入栈 p = p-lchild; elseelseelseelse Pop ( S, p ),Pop ( tag, f ); if if if if ( f=1 ) / 从左子树返回，二次入
