二叉树：镜像树,子结构,二叉树转链表,二叉树的倒数K个数,对称，Z型打印

1.把一棵二叉树转换为它的镜像树。

void mirror_tree(TreeNode *root)
{if(root==NULL) return ;TreeNode *temp=root->right;root->right=root->left;root->left=temp;mirror_tree(root->right);mirror_tree(root->left);}

镜像树

2、输入两棵二叉树A，B，判断B是不是A的子结构（我们约定空树不是任意一个树的子结构）。

bool _is_zi(TreeNode *s1,TreeNode *s2)
{if(s1==NULL &&s2==NULL) return true;if(s1!=NULL&&s2==NULL) return false;if(s1==NULL&&s2!=NULL) return false;if(s1->date!=s2->data) return false;return _is_zi(s1->left,s2->left)&&_is_zi(s1->right,s2->right);}bool is_zi(TreeNode *root,TreeNode *node)
{if(root==NUll ) return false;if(root->data==node->data){bool a=_is_zi(root,node);if(bool) return true;}bool left=is_zi(root->left,node);bool right=is_zi(root->right,node);return right||left
}

3、将一棵有序二叉树转换成一个有序的双向链表。

void *add_tail_node(TreeNode **head,TreeNode *node)
{if(*head==NULL){*head=node;	}else{(*head)->left->right=node;node->left=(*head)->left;}(*head)->left=node;}
void *_tree_to_list(TreeNode *root ,TreeNode **head)
{if(root==NULL) return ;//中序遍历树_tree_to_list(root->let,node);//根结点添加到链表中add_tail_node(head,root)_tree_to_list(root->right,head);
}
//二插树链表
TreeNode *tree_to_list(TreeNode *root)
{//因为不带头结点用，二级指针TreeNode *head=NULL;_tree_to_list(root->left,&head);//最后一个元素的right需要重新指向head//而不能在add_tail中让right=head,这样会找不到右子树head->left->right=head;
}

4、计算出有序二叉树中倒数第K个大的数。

bool _access(TreeNode *root, int *k, int index, int *ptr) {  if (NULL == root) return false;  // 递归地访问右子树  bool rflag = _access(root->right, k, index, ptr);  if (rflag) return true; // 如果右子树中找到了结果，则直接返回  // 尝试在当前节点上找到结果  if ((*k)++ == index) {  *ptr = root->data;  return true;  }  // 递归地访问左子树  return _access(root->left, k, index, ptr);  
}

5、判断一个二叉树是否对称。

bool _is_sym(TreeNode *root1,TreeNode *root2)
{if(root1==NULL&&root2==NULL) return true;if(root1==NULL&&root2!==NULL) return false;if(root1==!NULL&&root2==NULL) return false;if(root1->data!=root2->data) return false;bool  lh=_is_sym(root1->left,root2->right);bool  rh=_is_sym(root2->right,root2->left);return lh&&rh
}
//5.对称
bool is_sym(TreeNode *root)
{_is_sym(root,root);	}

6、请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

//查找某节点
TreeNode *find_node(TreeNode *root, TREE_TYPE data)
{if (NULL == root){return NULL;}if (data == root->data){return root;}TreeNode *leftResult = find_node(root->left, data);if (leftResult != NULL){return leftResult;}TreeNode *rightResult = find_node(root->right, data);if (rightResult != NULL){return rightResult;}return NULL;
}//请实现一个函数按照之字形打印二叉树
void printf_zhi(TreeNode *root)
{if (NULL == root) return;ListStack *stack1 = create_Link_stack();ListStack *stack2 = create_Link_stack();push_Link_stack(stack1, root->data); // 将根节点入栈bool left_to_right = true; // 标记从左往右打印while (!empty_list_stack(stack1) || !empty_list_stack(stack2)){ListStack *current_stack = left_to_right ? stack1 : stack2;ListStack *next_stack = left_to_right ? stack2 : stack1;while (!empty_list_stack(current_stack)){TREE_TYPE data = top_list_stack(current_stack);printf("%c ", data);pop_List_stack(current_stack);TreeNode *current_node = find_node(root, data); // 找到当前节点if (current_node != NULL){if (left_to_right){if (current_node->left != NULL) push_Link_stack(next_stack, current_node->left->data);if (current_node->right != NULL) push_Link_stack(next_stack, current_node->right->data);}else{if (current_node->right != NULL) push_Link_stack(next_stack, current_node->right->data);if (current_node->left != NULL) push_Link_stack(next_stack, current_node->left->data);}}}left_to_right = !left_to_right; // 切换方向}
}