2023年6月22日发(作者：)

⼆叉树的常见笔试⾯试题在⼆叉树的基本操作⾥已经说明如何⽤递归的⽅法进⾏⼆叉树的遍历，那么如何⽤⾮递归的⽅法来进⾏⼆叉树的遍历呢，请看下⽂1.使⽤⾮递归⽅式进⾏⼆叉树的先序遍历思想：先将根节点⼊栈然后出栈，继续将右⼦树先⼊栈，然后将左⼦树⼊栈，因为栈是先进后出的原则，所以左⼦树后进是先出来的实现代码：void TreePreOrderByLoop(TreeNode* root){ if(root == NULL) { return; } //先把根结点⼊栈 SeqStack stack; SeqStackInit(&stack); SeqStackPush(&stack,root); //循环开始，栈为空时循环结束 TreeNode* cur = NULL; while(SeqStackTop(&stack,&cur)) { //取栈顶元素为当前元素。出栈 SeqStackPop(&stack); //打印当前元素 printf("%c ",cur->data); //把当前元素的左⼦树⼊栈 if(cur->rchild != NULL) { SeqStackPush(&stack,cur->rchild); } //把当前的右⼦树⼊栈 if(cur->lchild != NULL) { SeqStackPush(&stack,cur->lchild); } } printf("n"); return;}测试代码：void TestPreOrderByLoop(){ TEST_HEADER; TreeNodeType data[] = "abd##eg###c#f##"; TreeNode* root = TreeCreate(data,sizeof(data)/sizeof(data[0])-1,'#'); TreePreOrderByLoop(root);}运⾏结果：2.使⽤⾮递归⽅式进⾏⼆叉树的中序遍历实现代码：void TreeInOrderByLoop(TreeNode* root){ if(root == NULL) { return; } SeqStack stack; SeqStackInit(&stack); //定义cur指向根节点 TreeNode* cur = root; while(1) { //循环的判定cur是否为空，如果不为空，就将cur⼊栈 //并将cur指向cur->lchild while(cur != NULL) { SeqStackPush(&stack,cur); cur = cur->lchild; } //如果cur为空，取栈顶元素，访问出栈 TreeNode* top; int ret = SeqStackTop(&stack,&top); if(ret == 0) { //说明栈中已经没有元素了 return; } printf("%c ",top->data); SeqStackPop(&stack); //让cur指向栈顶元素的右⼦树，重复刚才循环判空的过程 cur = top->rchild; } printf("n"); return;}测试代码：void TestInOrderByLoop(){ TEST_HEADER; TreeNodeType data[] = "abd##eg###c#f##"; TreeNode* root = TreeCreate(data,sizeof(data)/sizeof(data[0])-1,'#'); TreeInOrderByLoop(root);}运⾏结果：3.使⽤⾮递归⽅式进⾏⼆叉树的后序遍历实现代码：void TreePostOrderByLoop(TreeNode* root){ if(root == NULL) { return; } SeqStack stack; SeqStackInit(&stack); //定义⼀个cur指向root TreeNode* cur = root; //pre保存上⼀个访问过的元素 TreeNode* pre = NULL; while(1) { //循环判断cur是否为空，如果不为空就将cur⼊栈 //并且将cur指向cur->lchild while(cur != NULL) { SeqStackPush(&stack,cur); cur = cur->lchild; } TreeNode* top; int ret = SeqStackTop(&stack,&top); if(ret == 0) { printf("n"); return; } //如果cur为空，循环取栈顶元素 //对栈顶元素进⾏判定 //a）如果栈顶元素的右⼦树和访问的上⼀个元素是同⼀个元素 //b）栈顶元素的右⼦树为空 // 此时才能够访问栈顶元素，同时进⾏出栈 //如果不满⾜刚才的条件，就让cur指向栈顶元素的右⼦树，重复循环 if(top->rchild == NULL || top->rchild == pre) { printf("%c ",top->data); SeqStackPop(&stack); pre = top; } else { cur = top->rchild; } } return;}测试代码：void TestPostOrderByLoop(){ TEST_HEADER; TreeNodeType data[] = "abd##eg###c#f##"; TreeNode* root = TreeCreate(data,sizeof(data)/sizeof(data[0])-1,'#'); TreePostOrderByLoop(root);}运⾏结果：4.⼆叉树的镜像（就像⼈照镜⼦⼀样，原来的左⼦树变为右⼦树，原来的右⼦树变为左⼦树）（1）递归⽅法实现代码：void Swap(TreeNode** a,TreeNode** b){ TreeNode* tmp = *a; *a = *b; *b = tmp; return;}void TreeMirror(TreeNode* root){ if(root == NULL) { return; } Swap(&root->lchild,&root->rchild); TreeMirror(root->lchild); TreeMirror(root->rchild);}测试代码：void TestMirror(){ TEST_HEADER; TreeNodeType data[] = "abd##eg###c#f##"; TreeNode* root = TreeCreate(data,sizeof(data)/sizeof(data[0])-1,'#'); TreeMirror(root); printf("n先序遍历："); TreePreOrder(root); printf("n中序遍历："); TreeInOrder(root); printf("n后序遍历："); TreePostOrder(root); printf("n层序遍历："); TreeLevelOrder(root);}运⾏结果：（2）⾮递归⽅法：实现代码：void TreeMirrorByLoop(TreeNode* root){ if(root == NULL) { return; } SeqQueue queue; SeqQueueInit(&queue); SeqQueuePush(&queue,root); TreeNode* cur = NULL; while(SeqQueueFront(&queue,&cur)) { //此处的访问相当于交换左右⼦树 Swap(&cur->lchild,&cur->rchild); SeqQueuePop(&queue); if(cur->lchild != NULL) { SeqQueuePush(&queue,cur->lchild); } if(cur->rchild != NULL) { SeqQueuePush(&queue,cur->rchild); } } return;}测试代码：void TestMirrorByLoop(){ TEST_HEADER; TreeNodeType data[] = "abd##eg###c#f##"; TreeNode* root = TreeCreate(data,sizeof(data)/sizeof(data[0])-1,'#'); TreeMirrorByLoop(root); printf("n先序遍历："); TreePreOrder(root); printf("n中序遍历："); TreeInOrder(root); printf("n后序遍历："); TreePostOrder(root); printf("n层序遍历："); TreeLevelOrder(root);}运⾏结果：5.判断⼀个数是不是完全⼆叉树⾸先介绍⼀下什么是完全⼆叉树完全⼆叉树是由满⼆叉树⽽引出来的。对于深度为K的，有n个节点的⼆叉树，当且仅当其每个节点都与深度为K的满⼆叉树中的编号从1⾄n的节点⼀⼀对应时称之为完全⼆叉树。完全⼆叉树具有以下的特点：1）只允许最后⼀层有空缺节点且空缺在右边，即叶⼦节点只能在层次最⼤的两层上出现；2）对任⼀节点，如果其右⼦树的深度为j，则其左⼦树的深度必为j或j+1，即度为1的点只有1个或0个实现代码：int IsCompleteTree(TreeNode* root){ if(root == NULL) { return 0; } SeqQueue queue; SeqQueueInit(&queue); SeqQueuePush(&queue,root); //是否要进⼊第⼆阶段 int is_step_tow_flag = 0; TreeNode* cur = NULL; while(SeqQueueFront(&queue,&cur)) { SeqQueuePop(&queue); //阶段⼀⾛这个分⽀ if(is_step_tow_flag == 0) { if(cur->lchild != NULL && cur->rchild != NULL) { //同时具备左右⼦树 SeqQueuePush(&queue,cur->lchild); SeqQueuePush(&queue,cur->rchild); } else if(cur->rchild != NULL && cur->lchild == NULL) { //只有右⼦树，没有左⼦树，⼀定不是完全⼆叉树 return 0; } else if(cur->rchild == NULL && cur->lchild != NULL) { //只有左⼦树没有右⼦树，需要进⼊第⼆阶段 is_step_tow_flag = 1; SeqQueuePush(&queue,cur->lchild); } else { //没有左右⼦树 is_step_tow_flag = 1; } } else { //阶段⼆分⽀ if(cur->lchild == NULL && cur->rchild == NULL) { break; } else { return 0; } }//结束阶段⼀和阶段⼆的判定 }//循环结束 //所有节点都遍历完了，此时是完全⼆叉树 return 1;}测试代码：void TestIsComplete(){ TEST_HEADER; TreeNodeType data[] = "abd##eg###c#f##"; TreeNode* root = TreeCreate(data,sizeof(data)/sizeof(data[0])-1,'#'); int ret = IsCompleteTree(root); printf("ret expected : 0,actual %dn",ret); TreeNodeType data1[] = "ab##c##"; TreeNode* root1 = TreeCreate(data1,sizeof(data1)/sizeof(data1[0])-1,'#'); int ret1 = IsCompleteTree(root1); printf("ret1 expected : 1,actual %dn",ret1);}运⾏结果：6.知道⼆叉树的先序和中序的遍历结果创建⼀个树实现代码：size_t Find(TreeNodeType array[],size_t left,size_t right,TreeNodeType to_find){ size_t i = left; for(;i < right ;++i) { if(array[i] == to_find) { return i; } } return 0;}TreeNode* _TreeRebuild(TreeNodeType pre_order[],size_t pre_order_size,size_t* pre_order_index, TreeNodeType in_order[],size_t in_order_left,size_t in_order_right){ if(in_order_right >= in_order_left) { //⽆效区间内，当前⼦树的中序遍历结果就是空的，此时说明这棵⼦树就是空树 return NULL; } if(pre_order_index == NULL ) { //⾮法输⼊ return NULL; } if(*pre_order_index >= pre_order_size) { //遍历完了 return NULL; } //根据先序遍历结果取出当前值，基于这个值构建⼀个节点 //new_node相当于前⼦树的根节点 TreeNode* new_node = CreateTreeNode(pre_order[*pre_order_index]); //查找⼀下当前节点在中序序列的位置 size_t cur_root_in_order_index = Find(in_order,in_order_left,in_order_right,new_node->data); assert(cur_root_in_order_index != (size_t)-1); ++(*pre_order_index); //左⼦树区间[in_order_left,cur_root_in_order_index) new_node->lchild = _TreeRebuild(pre_order,pre_order_size,pre_order_index, in_order,in_order_left,cur_root_in_order_index); //右⼦树区间[cur_root_in_order_index+1，in_order_right) new_node->rchild = _TreeRebuild(pre_order,pre_order_size,pre_order_index, in_order,cur_root_in_order_index+1,in_order_right); return new_node;}TreeNode* TreeRebuild(TreeNodeType pre_order[],TreeNodeType in_order[],size_t size){ size_t pre_order_index = 0; //[in_order_left,in_order_right) size_t in_order_left = 0; size_t in_order_right = size; return _TreeRebuild(pre_order,size,&pre_order_index,in_order,in_order_left,in_order_right);}测试代码：void TestRebuild(){ TEST_HEADER; TreeNodeType pre_order[] = "acfbegd"; TreeNodeType in_order[] = "fcaegbd"; TreeNode* root = TreeRebuild(pre_order,in_order,sizeof(pre_order)/sizeof(pre_order[0])-1); printf("n先序遍历："); TreePreOrder(root); printf("n中序遍历："); TreeInOrder(root); printf("n后序遍历："); TreePostOrder(root); printf("n层序遍历："); TreeLevelOrder(root); printf("n");}运⾏结果：