长沙手机网站首页设计公司,网页设计主要用什么软件,开个电商公司需要多少钱,高端网站建设一般多少钱树
树的很多题目中都包含递归的思想
递归
递归包括递归边界以及递归式
即#xff1a;往下递#xff0c;往上归
递归写法的特点#xff1a;写起来代码较短#xff0c;但是时间复杂度较高
01 利用递归求解 n 的阶乘。
int Func(int n) {if (n 0) {return 1;}else …树
树的很多题目中都包含递归的思想
递归
递归包括递归边界以及递归式
即往下递往上归
递归写法的特点写起来代码较短但是时间复杂度较高
01 利用递归求解 n 的阶乘。
int Func(int n) {if (n 0) {return 1;}else {return n * Func(n - 1);}
}02 斐波那契数列是满足 F(0)1F(1)1F(n)F(n-1)F(n-2)(n≥2)的数列数列的前几项为 1123581321…。写出求解斐波那契数列第 n 项的程序。
int Fbnq(int n) {if (n 0||n 1) {return 1;}else {return Fbnq(n - 1) Fbnq(n - 2);}
}树
二叉树的链式存储结构体定义。
typedef struct BiTNode {int data;struct BiTNode* lchild, * rchild;
}BiTNode,*BiTree;01 二叉树先序递归遍历算法
先序递归遍历根左右
void PreOrder(BiTree T) {if (T NULL) {//递归边界return;}else {printf(%d, T-data);//打印此结点数据域中的数据值PreOrder(T-lchild);//递归遍历左子树PreOrder(T-rchild);//递归遍历右子树}
}简便写法如下
//简便
void PreOrder(BiTree T) {if (T ! NULL) {printf(%d, T-data);PreOrder(T-lchild);PreOrder(T-rchild);}
}因此有些代码看着比较难懂是因为它们把递归边界隐藏了变得不容易轻易看懂。
02 二叉树中序递归遍历算法
中序递归遍历左根右
void InOrder(BiTree T) {if (T ! NULL) {//若所处理的结点不为空InOrder(T-lchild);//递归遍历左子树printf(%d, T-data);//打印此结点数据域中的数据值InOrder(T-rchild);//递归遍历右子树}
}03 二叉树后序递归遍历算法
后序递归遍历左右根
void PostOrder(BiTree T) {if (T ! NULL) {PostOrder(T-lchild);PostOrder(T-rchild);printf(%d, T-data);}
}04 在一棵以二叉链表为存储结构的二叉树中查找数据域值等于 key 的结点是否存在如果存在则将指针 q 指向该结点假设结点数据域为 int 型。二叉树中结点值都不相同
由于指针q可能会发生改变因此需要加从变量标识符开始从右往左看最靠近标识符的是变量的本质类型而再往左即为对变量类型的进一步修饰在C中星号代表指针而代表引用而*代表指针引用BiTNode* q标识符q左边紧邻的是说明q是一个引用变量再往左是 *所以q是一个指针变量的引用在往左是BiTNode可见q是一个指向BiTNode类型的指针的引用。这里改写先序递归遍历。
void Search(BiTree T, BiTNode* q, int key) {if(T!NULL){if (T-data key) {q T;//若为 key 则指针 q 指向该结点}else {Search(T-lchild, q, key);Search(T-rchild, q, key);}}
}05 假设二叉树采用二叉链表形式存储设计一个算法求先序遍历序列中第 k(1≤k≤二叉树中结点个数)个结点的值。
需要一个计数的变量由于是递归每次调用自己相当于重新开始调用函数因此该计数变量需要是全局变量这题改写前序递归遍历由于初始时n0因此进入if时先自加然后判断
int n 0;//定义全局变量 n 进行计数
int Search_k(BiTree T, int k) {if (T ! NULL) {//改写先序递归遍历n;//更新变量 n记录现在访问的是第几个结点if (n k) {//若 n 等于 k 则直接打印访问结点的数据值并结束此次递归printf(%d, T-data);return T-data;}else {Search_k(T-lchild, k);Search_k(T-rchild, k);}}
}06 利用递归计算二叉树中所有结点的个数。
法一
利用递归
int n 0;
void calc(BiTree T) {if (T NULL) {return;}else {n;calc(T-lchild);calc(T-rchild);}
}int n0;//定义全局变量 n 用来计数
void calc(BiTree T){if(T!NULL){//改写先序递归遍历n;//将先序遍历中访问结点代码改写为计数代码calc(T-lchild);//递归遍历左子树calc(T-rchild);//递归遍历右子树}
}法二
注意法二思想如果计算以某一结点为根的这颗树的所有结点个数可以先计算出该节点左结点为根的所有结点个数然后计算出该节点右结点为根的所有个数最后加上1该结点本身就得到了所有结点个数然后继续拆分问题。定义n1和n2变量用来接收左子树和右子树的结点个数该变量为局部变量记录此次递归函数左子树和右子树的结点个数。由于是递归到达叶子结点时继续往下递左子树为空返回0所以n10右子树为空返回0所以n20因此叶子结点往上归的时候是n1 n2 11。接着依次往上归得到了结点数。
int Count(BiTree T) {int n1, n2;//定义 n1 和 n2 分别用于接收左右子树结点个数if (T NULL) {return 0;}else {n1 Count(T-lchild);//递归求解左子树中结点个数结果 n1 接收n2 Count(T-rchild);return n1 n2 1;//再加根结点}
}法二的代码是求二叉树的高度、求叶子结点的个数、求单/双分支结点的个数的算法思想递归时尽量把叶子结点的左右空子树也画出来。
07 利用递归计算二叉树中所有叶子结点的个数。
法一
改写先序递归遍历
//法一
int n 0;
void Countleaves(BiTree T) {if (T ! NULL) {//所处理结点是否为叶子结点if (T-lchild NULL T-rchild NULL) {n;//若遍历结点是叶子结点则计数}Countleaves(T-lchild);//递归遍历左子树Countleaves(T-rchild);}
}法二
递归边界树为空说明没有叶子结点结点是叶子结点返回1最后返回的是n1n2
//法二
int Countl(BiTree T) {int n1, n2;//接受左右子树的叶子结点个数if (T NULL) {return 0;}else if (T-lchild NULL T-rchild NULL) {return 1;}else {n1 Countl(T-lchild);//递归求解左子树中叶子结点的个数结果 n1 接收n2 Countl(T-rchild);return n1 n2;}
}08 (题一)利用递归计算二叉树中所有双分支结点个数。
双分支结点的分类及其处理
①双分支 n1n21 看左子树的双分支右子树的双分支加上本身
②单分支 n1n2 看左子树的双分支右子树的双分支
③叶子结点 n1n2 看左子树的双分支右子树的双分支
④NULL 0递归边界
上面双分支的1操作是加上本次的所以需要1
由于是双分支还是单分支导致递归式的变化。
//(题一)利用递归计算二叉树中所有双分支结点个数。
int Count(BiTree T) {int n1, n2;if (T NULL) {//递归边界return 0;}else if (T-lchild ! NULL T-rchild ! NULL) {n1 Count(T-lchild);//递归求解左子树双分支结点个数结果用 n1 接收 n2 Count(T-rchild);return n1 n2 1;}else {若不为空树根结点也不为双分支结点也就是叶子结点和单分支结点的情况n1 Count(T-lchild);n2 Count(T-rchild);return n1 n2;}
}09 (题二)利用递归计算二叉树中所有单分支结点个数。
单分支结点的分类及其处理
①双分支 n1n2 看左子树的单分支右子树的单分支
②单分支有左孩子没有右孩子或者有右孩子没有左孩子 n1n21 看左子树的单分支右子树的单分支加上本身
③叶子结点 n1n2 看左子树的单分支右子树的单分支
④NULL 0
将上面的①和③合并到else中。
int Count_Simple_Node(BiTree T) {int n1, n2;if (T NULL) {return 0;}if ((T-lchild T-rchild NULL) || (T-lchild NULL T-rchild)) {n1 Count_Simple_Node(T-lchild);//递归求解左子树单分支结点个数结果用 n1 接收n2 Count_Simple_Node(T-rchild);return n1 n2 1;}else {n1 Count_Simple_Node(T-lchild);//递归求解左子树单分支结点个数结果用 n1 接收n2 Count_Simple_Node(T-rchild);return n1 n2;}
}
10 利用递归计算二叉树的深度。
定义两个变量用来接收左右子树的深度判断左右子树哪个更深若左子树更深则树总深度为左子树深度1(根也算一层) 若右子树更深则树总深度为右子树深度1(根也算一层) 两棵子树高相等既可以左子树1也可以右子树1这里的1就是根所在的一层所以1可以自己模拟一下。
int Depth(BiTree T) {int ldep;int rdep;if (T NULL) {return 0;}ldep Depth(T-lchild);//递归求解左子树深度结果用 ldep 接收rdep Depth(T-rchild);//判断左右子树哪个更高高的树加上根节点那一层if (ldep rdep) {return ldep 1;}else {return rdep 1;}
}11 设树 B 是一棵采用二叉链表形式存储的二叉树编写一个把树 B 中所有结点的左、右子树进行交换的函数。
采用递归改写先序递归遍历根左右每次将其左右孩子交换。
void Swap(BiTree B){if(B!NULL){BiTNode *tempB-lchild;//定义 temp 辅助指针辅助 B 左右子树交换交换指针域变换B-lchildB-rchild;B-rchildtemp;Swap(B-lchild);//递归处理左子树Swap(B-rchild);//递归处理右子树}
}12 假设二叉树采用二叉链表存储结构设计一个算法求二叉树 T 中值为 x 的结点的层次号。
查找结点要遍历这里用先序遍历这里多传了一个level参数代表这个根当前所在层数这题不太同常规。
void Search_x_level(BiTree T, int x, int level) {//level是当前根节点所在的层次if (T ! NULL) {if (T-data x) {printf(x所处的层数为%d, level);}Search_x_level(T-lchild, x, level 1);Search_x_level(T-lchild, x, level 1);}
}
void Func(BiTree T, int x) {Search_x_level(T, x, 1);//初始时根所在层次为 1
} 思路2先把结点分层如结点1在第一层结点2、3在第二层结点4、5、6、7在第三层然后查找值为x所在的层次。该思路感觉有点麻烦
13 请写出二叉树层次遍历算法。
由于层次遍历是按层来遍历会跳结点需要辅助**队列**先进先出
①先将根结点入队
②出队打印
③lchild入队
④rchild入队
②③④循环
void LevelOrder(BiTree T) {Queue Q;//定义一个队列 QInitQueue(Q);//初始化队列 QBiTNode* p T;//定义一个遍历指针 p初始时指向根结点EnQueue(Q, p);//将根结点入队while (!IsEmpty(Q)) {//队列不为空则继续循环DeQueue(Q, p);//出队并让 p 指向出队结点printf(%d, p-data);//打印出队结点数据域中的数据if (p-lchild ! NULL) {EnQueue(Q, p-lchild);//若出队结点有左孩子则让其左孩子入队}if (p-rchild ! NULL) {EnQueue(Q, p-rchild);//若出队结点有右孩子则让其右孩子入队}}
}14 试写出二叉树的自下而上、从右到左的层次遍历算法。
层序遍历是从上到下从左到右也就是反转层序遍历。—栈当然还是需要用到队列只是说先入栈等到最后依次出栈打印。打印对栈依次出栈打印笔者刚开始用for循环说明还是对栈与队列的基本操作不熟悉本题中层次遍历在队列中的排序是结点从上到下从左到右而题目要求相反因此猜测中间还做了一步额外的操作使得顺序颠倒而栈刚好输入和输出相反先进后出、后进先出因此可以将每次出队结点进行压栈到最后遍历栈即可。本题代码和上题类似只不过出队后打印而是将其压栈到最后队列为空处理完每层结点后对栈遍历打印。注意打印操作需要出队或者出栈后然后打印。
void ReverseLevelOrder(BiTree T) {Queue Q;//定义队列 QStack S;//定义栈 SInitQueue(Q);//初始化队列 QInitStack(S);//初始化栈 SBiTNode* p T;//定义遍历指针 p初始时指向根结点EnQueue(Q, p);//根结点入队while (!IsEmpty(Q)) {DeQueue(Q, p);Push(S, p);//将出队结点压入栈 S 中if (p-lchild) {EnQueue(Q, p-lchild);}if (p-rchild) {EnQueue(Q, p-rchild);}}//打印操作while (!IsEmpty(S)) {//栈不为空则继续循环Pop(S, p);//出栈并让 p 指向出栈结点printf(%d, p-data);}
}15 二叉树按二叉链表形式存储写一个判别给定二叉树是否是完全二叉树的算法。
⭐⭐⭐⭐⭐
首先要知道什么是完全二叉树完全二叉树它除了最后一层外其他层的节点都是满的并且最后一层的节点都尽可能地靠左排列。简单来说完全二叉树是一个结构紧凑且平衡的二叉树。该算法思想和层序遍历一样定义一个遍历指针指向根结点然后入队。若队列不为空出队有左孩子将左孩子入队有右孩子将右孩子入队重复判断完全二叉树时候将NULL也入队因为完全二叉树结点在队列中是连续的中间没有NULL的存在而不是完全二叉树的话在队列中NULL结点后面还会有带值的结点在导致结点在队列中不连续。通过这个可以判断是否为完全二叉树也就是当我们遍历到NULL结点时候我们可以将队列中的结点全部出队如果非空结点存在说明不是完全二叉树。大家可以画个树和队列模拟一下过程。
int IsComplete(BiTree T) {if (T NULL) {//空树是完全二叉树return 1;}Queue Q;//定义队列InitQueue(Q);BiTNode* p T;//定义遍历指针p初始时指向根结点EnQueue(Q, p);//让根结点入队while (!IsEmpty(Q)) {DeQueue(Q, p);//出队并让 p 指向出队结点if (p ! NULL) {//若 p 不为空EnQueue(Q, p-lchild);//让其左孩子入队左孩子为空则入队 NULLEnQueue(Q, p-rchild);//让其右孩子入队右孩子为空则入队 NULL}else {//p是空结点队列中其后面的所有结点均应该是空结点否则不符合完全二叉树while (!IsEmpty(Q)) {//队列不为空则需继续循环DeQueue(Q, p);//出队并让 p 指向出队结点if (p ! NULL) {return 0;//若后续还有结点则不是完全二叉树}}}}return 1;//若队列中剩余数据都为 NULL 则证明是完全二叉树
}16 二叉树采用二叉链表形式存储设计一个算法完成对于树中每个元素值为 x 的结点删去以它为根的子树并释放相应的空间。
①查找到元素为x的结点②如何删除以它为根的树从下往上删除结点因为如果从上往下把根节点删了无法定位其左右孩子结点的位置查找元素为x的结点后要将x与其父亲结点的链路断链这里采用层序遍历一层一层查找树为空、树的根节点的值就是x这两种情况算是特别情况需要单独写出来正常查找过程中先定义一个队列然后将树的根节点入队然后进行判断队列是否为空不为空则出队左孩子入队右孩子入队循环在左孩子入队和右孩子入队过程中如果其值为x直接调用DeleteTree函数最后将其指针域置空详见代码
从下往上删除以T为根节点的树
改写后序递归遍历 左右根也就是先去找左子树然后去找右子树最后处理根最后递归下来根节点是最后删除的。
//从下往上删除以T为根节点的树
void DeleteTree(BiTree T) {if (T ! NULL) {DeleteTree(T-lchild);DeleteTree(T-rchild);free(T);//释放结点空间}
}查找元素为x的结点
当树的根节点就是要查找的x时候直接调用DeleteTree()函数最后写个return表示可以结束运行了。普通的层序遍历是如果左右子树不为空将其左右子树入队而这里需要的是如果左右子树不为空判断其值是否等于x如果等于说明查找到了需要删除调用DeleteTree()函数且这时候需要将该节点的左右指针域置空如果不等于x没找到则和普通操作一样。
//查找元素为x的结点
void SearchX(BiTree T, int x) {if (T NULL) {return;}if (T-data x) {//删除整棵树也是这里的特殊情况因为不需要做任何遍历查找DeleteTree(T);return;//函数执行结束}Queue Q;InitQueue(Q);BiTNode* p T;EnQueue(Q, p);//入队while (!IsEmpty(Q)) {DeQueue(Q, p);//出队并让 p 指向出队结点if (p-lchild ! NULL) {//左孩子判断if (p-lchild-data x) {//如果p的左孩子的值x说明查找到了删除DeleteTree(p-lchild);p-lchild NULL;//指针域置空因为删除函数只是对结点的删除}else {EnQueue(Q, p-lchild);//如果p的左孩子的值不是x正常进行层次遍历}}if (p-rchild ! NULL) {//右孩子判断if (p-rchild-data x) {//如果p的左孩子的值x说明查找到了删除DeleteTree(p-rchild);p-rchild NULL;//指针域置空因为删除函数只是对结点的删除}else {EnQueue(Q, p-rchild);//如果p的左孩子的值不是x正常进行层次遍历}}}
}17 二叉树采用二叉链表存储结构设计一个非递归算法求二叉树的高度。 由于非递归求二叉树的高度因此需要层次遍历定义一个变量h每遍历一层h相应变化 如何判断某一层遍历完了定义last变量指向每一层最后一个结点假如每层最后一个结点处理完了这一层也就处理完了h可以变化了 之前的题目都是调用队列的基本操作这次不行了这次研究的更细一些需要进行更改之前初始化时候front和rear都是0。 但是在这里如果采用上面的方式会导致rear指向每次结点的后一个位置相当于错开了而求二叉树高度定义的last变量需要和rear一起使用因此这里我们初始化时将front和rear均指向-1入队时先rear1然后赋值入队此时rear和结点没有错开。 这里判断队列是否为空是frontrear判断是否为每层最后一个节点是front last这里初始时last0因为根节点先入队列其下标也为0且根节点也是第一层的最后一个元素这样就保证了第一次根节点入队后进入循环根节点出队此时front也是0last也是0使得h、更新last。
int Depth(BiTree T) {if (T NULL) {return 0;}int h 0;//变量 h 用来记录高度int last 0;//变量 last 用来记录每一层最右边结点位置 BiTNode* Q[MaxSize];//定义队列 Qint front -1, rear -1;//定义队头指针和队尾指针BiTNode* p T;//定义遍历指针p初始时指向根结点Q[rear] p;//根结点入队 while (front rear) {//队列不为空则继续循环 p Q[front];//出队p 指向出队结点 if (p-lchild) {//若此结点有左孩子则让其左孩子入队 Q[rear] p-lchild;}if (p-rchild){//若此结点有右孩子则让其右孩子入队 Q[rear] p-rchild;}if (front last) {//若二叉树其中一层的最右边结点出队 h;//让高度加一 last rear;//更新 last使其指向下一层最右边结点位置 }}return h;//返回二叉树的高度
}18 假设二叉树采用二叉链表存储结构设计一个算法求给定的二叉树的宽度。(宽度即树中具有结点数最多那一层的结点个数) 层次遍历二叉树 这里记录结点属于哪一层时定义一个新的数组专门用来记录每个结点所在层数 层次遍历完后得到的数组就是包含每个结点所在层数的记录只需要遍历这个数组找到哪一层的数最多这样也就找到宽度以及其对应的层数。 举个例子假设结点元素为 1 3 4 5 8 9 4 6 则数组中为1 2 2 3 3 3 3 4说明宽度是4因为第三层的结点个数是4。
int Width(BiTree T) {if (T NULL)//若为空树则宽度为 0 return 0;BiTNode* Q[MaxSize];//定义队列 Q int front 0, rear 0;//定义队头指针和队尾指针 int level[MaxSize];//定义存储结点层数的数组 BiTNode* p T;//定义遍历指针 p初始时指向根结点 int k 1;//定义变量 k 记录指针 p 指向结点所在的层数 初始时有结点说明有高度k从1开始Q[rear] p;//根结点入队 level[rear] k;//记录根结点所在层数为 1 rear;//尾指针后移 //遍历二叉树目的是得到结点所在层数的数组while (front rear) {//若队列不为空则需继续循环 p Q[front];//出队并让 p 指向出队结点 k level[front];//更新 k 为出队结点所在层数 p变了k也要变front;//头指针后移 if (p-lchild) {//若出队结点有左孩子 Q[rear] p-lchild;//将该结点左孩子入队level[rear] k 1;//新入队结点所在层数为 k1 rear;//尾指针后移 }if (p-rchild) {//若出队结点有右孩子 Q[rear] p-rchild;//将该结点右孩子入队 level[rear] k 1;//新入队结点所在层数为 k1 rear;//尾指针后移 }}//查找最大的宽度int max 0, i 0, n;//定义 max 记录宽度i 作为遍历索引n 记录每一层结点数 k 1;//k 用来表示所计数的是第几层初始时等于 1 表示计数第一层 while (i rear) {//遍历记录结点层数的数组 n 0;//对每一层结点计数时都需初始化变量 n while (i rear level[i] k) {//对第 k 层结点进行计数 n;i;}k;//本层计数结束更新变量 k准备对下一层结点计数 if (n max)//判断此层结点数是否为当前遍历过的最大宽度max n;}return max;//返回此树的宽度
}代码中首先将根节点对应的数组元素设为1相当于根节点在第一层
19 请写出先序非递归遍历二叉树的算法。
递归用递归工作栈非递归就自己定义栈先序根-左-右定义遍历指针 p初始时指向根结点打印将结点压入栈因为需要从左子树跳转到右子树不用栈实现不了从左子树回到根再到右子树处理左子树左子树处理完了才出栈去处理右子树具体的讲就是和代码一样若p指针不为空或者栈不为空一直循环如果栈为空p指针不为空最开始就是这种情况入栈遍历左子树遍历多次后来p指针为空说明左子树遍历完了就要通过出栈找到右子树进行遍历如果栈不为空但是p指针为空说明多次压栈到叶子结点的左右孩子结点处因此需要通过出栈找到上一层的右子树最后p为NULL栈为空说明遍历结束了。这类题目的循环条件注意刚开始的时候到叶子结点的时候及其左右空子树的时候。
void PreOrder(BiTree T) {Stack S;//定义一个栈 S InitStack(S);//初始化栈 S BiTNode* p T;//定义遍历指针 p初始时指向根结点 while (p || !IsEmpty(S)) {//若 p 指针不为空或栈 S 不为空则继续循环 if (p ! NULL) {//若 p 指针不为空 printf(%d, p-data);//打印此结点数据域中的数据值 Push(S, p);//将此结点压入栈 S 中 p p-lchild;//遍历指针 p 继续遍历此结点的左子树 }else {Pop(S, p);//若 p 为空则出栈并让 p 指向出栈结点 p p-rchild;//p 继续遍历此结点的右子树 }}
}20 请写出中序非递归遍历二叉树的算法。
中序左-根-右遍历左子树后回到根需要栈帮助由于先左子树然后根因此先将结点入栈等到左子树全部处理完也就是p为NULL时候需要出栈该元素就是根结点然后打印去到右子树那边去。先一直处理左子树当左子树结点为空时候此时栈不为空说明没有左子树了返回到根打印处理右结点到最后p为空、栈为空结束。p到达叶子结点的左结点时候p指向NULL此时需要出栈也就是中序中的左-根并让 p 指向出栈结点此时p指向的就是根节点。
void InOrder(BiTree T) {Stack S;InitStack(S);BiTNode* p T;while (p || !IsEmpty(S)) {if (p ! NULL) {Push(S, p);//将所处理结点压入栈中p p-lchild;//p 继续遍历此结点左子树}else {Pop(S, p);//若 p 指针为空则出栈并让 p 指向出栈结点printf(%d, p-data);p p-rchild;//遍历指针 p 继续遍历此结点的右子树}}
}21 请写出后序非递归遍历二叉树的算法。
⭐⭐⭐⭐⭐
后序左右根左子树处理完需要处理右子树这时候需要通过栈来实现但是这又出现一个问题左子树到右子树需要到根而右子树处理完也要到根这两个都可能需要到根结点处需要区分左子树处理完需要通过根结点遍历访问到右子树右子树处理完需要到根打印这两个的原因不同因此需要不同情况处理因此定义一个r指针负责记录上一个打印的结点位置else分支的意思是在p指向空的时候其根结点有没有右孩子以及根节点的这个右孩子有没有处理过分情况处理。此外else处的意思在p指向空时候需要出栈p指向出栈结点使得此时p就是根节点然后进行操作但是这是前序和中序非递归的思想对于后续非递归算法由于左右子树均有到根结点的情况需要分情况讨论如果只是左子树需要通过根跳转到右子树的情况我们就不用出栈而是需要到右子树等右子树处理完在打印根节点而如果是右子树跳转到根了说明需要打印此时出栈打印此时更新记录指针r表示该节点是最近一次遍历打印过了。由上面是否出栈的情况因此这里使用栈的GetTop()函数用来获取栈顶元素方便判断该节点是否存在右孩子且右孩子是否被遍历访问过。前序和中序非递归算法不用判断p-rchild是否为NULL因为它们都是每次循环的最后一步到下一次循环时候循环条件会判断p是否为NULL而后续非递归涉及到右子树是否被遍历过因此需要判断是否存在右子树。
void PostOrder(BiTree T) {Stack S;InitStack(S);BiTNode* p T;BiTNode* r NULL;while (p || !IsEmpty(S)) {if (p ! NULL) {Push(S, p);//先压栈然后去到左子树那里p p-lchild;}else {GetTop(S, p); if ((p-rchild ! NULL)(p-rchild!r)) {//有右孩子且右孩子没有被访问过左-右p p-rchild;}else {//若结点没有右子树或者右子树已被遍历过,右-根Pop(S, p);printf(%d, p-data);r p;//更新记录指针 }}}
} 模拟一下发现有问题左下角的叶子结点处理后会陷入死循环其原因是p到达左下角叶子结点时候p!NULL此时p去到叶子结点的左孩子那此时pNULL进入else中p回到叶子结点处且若没有右子树会出栈打印然后更新记录指针此时都没有变化p使得p!NULL从而陷入循环了下面代码在每次更新记录指针后将遍历指针p置空
void PostOrder(BiTree T) {Stack S;//定义栈 S InitStack(S);//初始化栈 S BiTNode* p T;//定义遍历指针 p初始时指向根结点 BiTNode* r NULL;//定义记录指针 r负责记录上一个打印的结点位置 while (p || !IsEmpty(S)) {//若 p 指针不为空或栈不为空则继续循环 if (p ! NULL) {//若 p 指针不为空 Push(S, p);//将所处理结点压入栈中 p p-lchild;//p 继续遍历此结点左子树 }else {GetTop(S, p);//若 p 指针为空则 p 指向栈顶结点 if (p-rchild p-rchild ! r)//判断此结点是否有右孩子以及是否遍历 p p-rchild;//若结点有右孩子且未被遍历则 p 继续遍历其右子树 else {//若结点没有右子树或者右子树已被遍历过 Pop(S, p);//出栈并让 p 指向其出栈结点 printf(%d, p-data);//打印此结点数据域中的数据 r p;//更新记录指针 p NULL;//将遍历指针置空 }}}
} 对于后续非递归遍历算法当你遍历打印某个结点时栈中的结点就是该结点的根也就是遍历某个结点时候栈中的元素都是其祖先后续打印某结点的祖先结点打印根节点到某结点的路径都是后续非递归遍历算法的改写。
22 在二叉树中查找值为 x 的结点试编写算法打印值为 x 的结点的所有祖先假设值为 x 的结点不多于一个。
后序非递归遍历栈里面的就是x及其所有祖先结点因此写这类求祖先结点实质就是写后序遍历的非递归版本只是将打印操作变成判断值是否为x相等则出栈打印其祖先结点。
void Search_x_father(BiTree T,int x) {Stack S;InitStack(S);BiTNode* p T;BiTNode* r NULL;while (p || !IsEmpty(S)) {if (p ! NULL) {Push(S, p);p p-lchild;}else {GetTop(S, p);//p 指向栈顶结点但不出栈if (p-rchild p-rchild ! r) {//若该结点有右子树且未被访问p p-rchild;}else {//若该结点无右子树或者右子树已经被访问Pop(S, p);//出栈并让 p 指向出栈结点if (p-data x) {//是我们要找的值while (!IsEmpty(S)) {//打印栈中的元素Pop(S, p);//出栈并让 p 指向出栈结点printf(%d, p-data);}}else {//不是我们要找的值r p;//更新记录指针位置p NULL;//将指针 p 置空进行下一次循环判断}}}}
}23 p 和 q 分别为指向一棵二叉树中任意两个结点的指针试编写算法找到p 和 q 最近公共结点并返回。
思路就是分别找两个结点的所有祖先节点然后比较这里采用后序非递归遍历每次遍历过程中栈中的元素就是该结点的所有祖先具体就是先找到p或者q谁先找到都没事找到后将栈中内容复制一份到新创建的栈1然后继续找还没找到的p/q然后找到后再复制一份内容到新创建的栈2因为涉及到栈的复制因此这里使用数组方便复制使用标准的栈需要出入栈比较复杂数组复制就使用一个for循环就好注意这里是查找公共结点并返回因此函数类型需要注意。后序非递归执行完后需要找最近公共结点从下往上从叶子结点到最祖先节点复制栈后别忘了更新栈顶指针。
BiTNode* FindAncestor(BiTree T, BiTNode* p, BiTNode* q) {BiTNode* bt T;BiTNode* r NULL;//定义三个栈,因为要复制BiTNode* S[MaxSize];BiTNode* S1[MaxSize],* S2[MaxSize];int top -1, top1 -1, top2 -1;int temp;//复制元素时使用while (bt || top!-1) {//栈不为空if (bt ! NULL) {S[top] bt;//入栈bt bt-lchild;}else {//若遍历指针为空bt S[top];//bt 指向栈顶结点但不出栈if (bt-rchild bt-rchild ! r) {//若该结点有右孩子且未被访问bt bt-rchild;//bt 遍历该结点右子树}else {//若该结点没有右孩子或者右孩子已经被访问bt S[top];top--;//出栈bt指向出栈结点if (bt p) {//如果该节点是p结点复制栈S到栈S1for (temp 0; temp top; temp) {S1[temp] S[temp];}top1 top;//更新 S1 栈顶指针}if (bt q) {for (temp 0; temp top; temp) {S2[temp] S[temp];}top2 top;}//更新r和btr bt;//更新记录指针bt NULL;//bt 指针置空}}}//查找最近公共结点for (int i top1; i 0; i--) {for (int j top2; j 0; j--) {if (S1[i] S2[j]) {return S1[i];//若找到即返回指向最近公共结点的指针变量 }}}return NULL;
}24 假设一棵二叉树以二叉链表存储方式存储请设计一个算法输出根结点到每个叶子结点的路径。
输出路径也使用后序非递归遍历定义辅助栈S这里判断一下每次的结点是不是叶子节点由于这里需要输出根节点到每个叶子结点的路径如果采用伪代码中调用栈的话每次打印路径需要出栈打印出栈打印比较麻烦此外由于是根-叶子结点在栈中是从下往上打印因此可以定义数组类型的栈方便遍历打印for循环从下标0处开始打印就是从下网上打印这里定义的栈存储的元素是结点类型有data域因此代码第23行为S[i]-data且需要打印叶子结点因为这个结点是先出栈然后打印的栈中只有其祖先结点这类题目首先看是后续非递归遍历的体型因此一般是19行开始最内部的else的代码的改写因为进入这个循环才要准备对结点进行相关操作了在此之前的都是为了让其进入对应的“路”。
void AllPath(BiTree T) {//改写后序非递归遍历BiTNode* p T;BiTNode* r NULL;//定义遍历指针 p记录指针 rBiTNode* S[MaxSize];//定义栈 Sint top -1;//定义栈顶指针while (p ! NULL || top ! -1) {if (p ! NULL) {S[top] p;//让 p 所指结点入栈 p p-lchild;}else {p S[top];//p 指向栈顶结点但不出栈 if (p-rchild p-rchild ! r) {//若 p 所指结点有右子树且未被访问 p p-rchild;}else {p S[top--];//出栈并让 p 指向其出栈结点if (p-lchild NULL p-rchild NULL) {for (int i 0; i top; i) {printf(%d, S[i]-data);//打印栈中所有结点数据}printf(%d, p-data);//打印此叶子结点数据}r p;//更新记录指针 r p NULL;//将 p 指针置空 }}}
}25 设计一个算法将二叉树的叶子结点按从左到右的顺序连成一个单链表表头指针为 head。二叉树按二叉链表方式存储链接时用叶子结点的右指针域来存放单链表指针。
从左到右链接头指针head指向最左边的叶子节点少不了遍历先序根左右中序左根右后序左右根不看根的位置这三种发现都是以左-右遍历的因此这三种遍历方式遍历叶子结点都可以这里通过改写中序遍历左根右由题意先定义一个表头指针head然后由于需要将叶子结点链接起来需要定义一个pre指针指向最近已经链接的叶子结点记录上一次遍历到的叶子结点若新找到叶子结点可以用pre-rchild新找到的叶子结点然后更新pre指针判断是否是第一个叶子结点可以判断pre是否为NULL。
BiTNode* head NULL, * pre NULL;//定义头指针 head 和记录指针 pre
void Link(BiTree T) {if (T ! NULL) {//改写中序递归遍历算法 Link(T-lchild);//递归遍历左子树//判断此结点为叶子结点 if (T-lchild NULL T-rchild NULL) {if (pre NULL) {//判断此结点是否为访问到的第一个叶子结点 head T;//若为第一个叶子结点则让头指针 head 指向它 pre T;//pre 负责记录上一次处理的叶子结点所以进行更新 }else {//若此结点不是第一个叶子结点 pre-rchild T;//直接让上一个访问的叶子结点指向此结点 pre T;//更新 pre 指针位置 }}Link(T-rchild);//递归遍历右子树 }
}26 表达式(a-(bc))*(d/e)存储在如下图所示的一棵以二叉链表为存储结构的二叉树中(二叉树结点的 data 域为字符型)编写程序求出该表达式的值。(表达式中的操作数都是一位的整数)
说明函数 int op(int A,int B,char C)返回的是以 C 为运算符以 A、B 为操作数的算式的数值例如若 C 为‘’则返回 AB 的值。 表达式中包括操作数和运算符叶子结点都是操作数双分支结点是操作符对于双分支结点采用递归方式求其左右子树的值对于叶子结点结点的data域是字符型如’0’‘1’‘2’不能直接参与计算计算机存的是ASCII码将字符型转化为整型可以采用将其对应的ASCII码减去’0’的ASCII码然后return就是对应的0-9的数字递归方式将其分为左右子树分别计算调用op函数
int Compute(BiTree T) {if (T NULL) {return 0;}int A, B;//定义两个变量分别接受左右子树计算的结果if (T-lchild ! NULL T-rchild ! NULL) {//若结点为双分支结点 A Compute(T-lchild);//递归计算左子树的值并用 A 接收 B Compute(T-rchild);//递归计算右子树的值并用 B 接收 return op(A, B, T-data);//计算左右子树运算结果并返回 }else {//若结点为叶子结点 return T-data - 0;//将字符型变量转换为数值ASCII 码return T-data是错的 }
}27 试设计判断两棵二叉树是否相似的算法。所谓二叉树 T1 和 T2 相似指的是 T1 和 T2 都是空的二叉树或都只有一个根结点或者 T1 的左子树和 T2 的左子树是相似的且 T1 的右子树和 T2 的右子树是相似的。
这题的相似指的是不管数据如何只管二叉树的结构是否相同使用递归分别判断左右子树是否相似递归边界这里给出两个两棵树都为空相似一棵树为空、另一棵树不为空说明不相似。
int Similar(BiTree T1, BiTree T2) {//结点结构一样即为相似 定义两个变量分别用于接收左右子树是否相似 int left, right;if (T1 NULL T2 NULL) {return 1;}else if (T1 NULL || T2 NULL) {return 0;}else {//递归式left Similar(T1-lchild, T2-lchild);//递归判断两棵树左子树是否相似 right Similar(T1-rchild, T2-rchild);//递归判断两棵树右子树是否相似 //return left right;//若左右子树都相似则两棵树相似返回 1 if (left 1 right 1) {return 1;//相似}else {return 0;}}
}28 在二叉树的二叉链表存储结构中增加一个指向双亲结点的 parent 指针设计一个算法给这个指针赋值并输出所有结点到根结点的路径。
修改原先树结点的结构体增加parent指针然后赋值最后输出所有结点到根结点的路径。赋值时采用先序遍历根左右先处理根然后在左右结点因此可以较好的从孩子结点-父亲结点定义一个q指针每次让结点的parent指针指向q就实现了赋值但是代码中需要注意的是根结点没有双亲结点需要将其置空且初始时应该为空因此调用Func()函数时候传入的参数应该为NULL输出所有结点到根结点的路径可以先写一个结点到根节点的路径的函数然后对所有结点遍历调用该函数。根节点的parent置空这是判断循环结束的条件遍历树的时候可以采用任何遍历方式因为只要遍历就行。
typedef struct BiTNode {int data;struct BiTNode* lchild;struct BiTNode* rchild;struct BiTNode* parent;
}BiTNode,*BiTree;
//对parent指针赋值
void Func(BiTree T, BiTNode* q) {//指针 q 用来记录T的双亲结点 if (T ! NULL) {//改写先序递归遍历 T-parent q;//遍历结点的 parent 指针指向双亲结点 q T;//更新指针 q 的位置 Func(T-lchild, q);//递归遍历左子树 Func(T-rchild, q);//递归遍历右子树 }
}
//打印单个结点到根结点的路径
void PrintPath(BiTNode* p) {while (p ! NULL) {//只要 p 不为空则继续循环 printf(%d, p-data);//打印结点数据域中数据 p p-parent;//p 顺着 parent 指针遍历 }
}
//打印所有结点到根结点的路径
void AllPath(BiTree T) {if (T ! NULL) {//只要 p 不为空则继续循环 PrintPath(T);//打印所处理结点到根结点路径 AllPath(T-lchild);//递归遍历左子树 AllPath(T-rchild);//递归遍历右子树 }
}29 有一棵二叉树以顺序存储的方式存在一维数组 A 中树中结点存储数据为字符型空指针域在数组中以字符’#表示请设计一个算法将其改为二叉链表的存储方式。(假设数组 A 中元素个数为 n从下标1处开始存储)
普通二叉树存在数组中需要将二叉树补成完全二叉树题目中给出NULL指针域用#表示二叉链表由左指针域数据域右指针域由于这里是下标为1开始数组下标和结点存在关系根结点下标为i左孩子结点位置为2i右孩子节点位置2i1函数类型BiTree每次创建完新的结点后返回新创建结点的位置为何会涉及到in呢比如当i是5时候进入下次递归去它左子树处此时i10n因此返回NULL。 BiTree Create(char A[], int i, int n) {//i 为索引n 为数组中元素个数 if(in||A[i]#){return NULL;//若 i≥n 则代表后续已无结点则返回 NULL }else{//只有 in 才有意义 BiTNode* p (BiTNode*)malloc(sizeof(BiTNode));//申请内存空间 p-data A[i];//给结点数据域赋值 p-lchild Create(A, 2*i, n);//递归处理左子树 p-rchild Create(A, 2*i1, n);//递归处理右子树 return p; //返回结点位置}
}30 设一棵二叉树中各结点的值互不相同其先序遍历序列和中序遍历序列分别存于两个一维数组 A[1…n]和 B[1…n]中试编写算法建立该二叉树的二叉链表。
先序ABCDE
中序BCAED
建立的二叉树如下
A
B D
NULL C E NULL 写代码时和我们自己手动确定二叉树结构类似拿到先序和中序序列时候先找到先序递归遍历的第一个结点该结点是整棵树的根结点此时确定好整棵树的根节点了可以创建该节点然后在中序遍历序列中找到这个根节点将序列分为左右两块也就是左子树和右子树 先序遍历序列根左右和中序遍历序列左根右可以确定唯一的二叉树且先序遍历序列的第一个结点是整棵树的根结点 需要在中序遍历序列中将结点分为左右两块 代码中low和high指的是数组中最左边和最右边是谁根节点确定好后B数组也需要到根结点处方便后续将树分为左子树和右子树因此有个for循环 由于题目中数组下标从1开始因此记录左右子树结点个数 llen i - low2;rlen high2 - i 递归创建左子树时候左半段对于A数组最开始的是根在递归时需要排出已经使用过了结束位置是low1 llen这里不是low11 llen可以自己动手试一试对于B数组最开始的就是最左边的结束位置是根节点前一个 p-lchild Create(A, low1 1, low1 llen, B, low2, low2 llen - 1);递归创建右子树时同样可以自己模拟一下哦
BiTree Create(char A[], int low1, int high1, char B[], int low2, int high2) {BiTNode* p (BiTNode*)malloc(sizeof(BiTNode));//给根结点分配内存空间p-data A[low1];//为根结点数据域赋值int i;//定义变量 i记录中序序列中根结点的位置for (i low2; B[i] ! p-data; i);//循环使变量 i 指向中序序列中根结点的位置int llen i - low2;//llen 记录左子树结点个数int rlen high2 - i;//rlen 记录右子树结点个数if (llen) {//若左子树有结点则递归创建左子树p-lchild Create(A, low1 1, low1 llen, B, low2, low2 llen - 1);}else {//若左子树已无结点则让其左指针域赋 NULLp-lchild NULL;}if (rlen) {//若右子树有结点则递归创建右子树p-rchild Create(A, high1 - rlen 1, high1, B, high2 - rlen 1, high2);}else {//若右子树已无结点则让其右指针域赋 NULLp-rchild NULL;}return p;//最后返回所创建树的根结点
}31 设有一棵满二叉树所有结点值均不同已知其先序序列为 pre设计一个算法求其后序序列 post。
先序序列的第一个结点就是根节点也是后序序列的最后一个结点满二叉树特点如果不看根节点其左右子树的结点数量是一样的可以将除根节点以外的结点一分为二然后分出来的两块左边的就是左子树右边的就是右子树然后递归。l1和h1是先序序列最左边的位置和最右边的位置所有h1l1时才有意义l2和h2是后序序列最左边的位置和最右边的位置所有h1l1时才有意义代码中给post数组赋值的根节点的操作。
void PreToPost(char pre[], int l1, int h1, char post[], int l2, int h2) {int half;//定义 half 变量记录左子树右子树结点个数if (h1 l1) {//h1≥l1 才有意义(先序遍历post[h2] pre[l1];//后序序列最后一个即为根结点也就是先序序列第一个half (h1 - l1) / 2;//因为是满二叉树所以左右子树结点个数相等PreToPost(pre, l1 1, l1 half, post, l2, l2 half - 1);//递归处理左子树PreToPost(pre, l1 1 half, h1, post, l2 half, h2 - 1);//递归处理右子树}
}/llen 记录左子树结点个数 int rlen high2 - i;//rlen 记录右子树结点个数 if (llen) {//若左子树有结点则递归创建左子树 p-lchild Create(A, low1 1, low1 llen, B, low2, low2 llen - 1); } else {//若左子树已无结点则让其左指针域赋 NULL p-lchild NULL; } if (rlen) {//若右子树有结点则递归创建右子树 p-rchild Create(A, high1 - rlen 1, high1, B, high2 - rlen 1, high2); } else {//若右子树已无结点则让其右指针域赋 NULL p-rchild NULL; } return p;//最后返回所创建树的根结点 }
##### 31 设有一棵满二叉树所有结点值均不同已知其先序序列为 pre设计一个算法求其后序序列 post。1. 先序序列的第一个结点就是根节点也是后序序列的最后一个结点
2. **满二叉树特点**如果不看根节点其左右子树的结点数量是一样的可以将除根节点以外的结点一分为二然后分出来的两块左边的就是左子树右边的就是右子树然后递归。
3. l1和h1是先序序列最左边的位置和最右边的位置所有h1l1时才有意义l2和h2是后序序列最左边的位置和最右边的位置所有h1l1时才有意义
4. 代码中给post数组赋值的根节点的操作。~~~cpp
void PreToPost(char pre[], int l1, int h1, char post[], int l2, int h2) {int half;//定义 half 变量记录左子树右子树结点个数if (h1 l1) {//h1≥l1 才有意义(先序遍历post[h2] pre[l1];//后序序列最后一个即为根结点也就是先序序列第一个half (h1 - l1) / 2;//因为是满二叉树所以左右子树结点个数相等PreToPost(pre, l1 1, l1 half, post, l2, l2 half - 1);//递归处理左子树PreToPost(pre, l1 1 half, h1, post, l2 half, h2 - 1);//递归处理右子树}
}
