思路 : 1.设置两个队列l,r,先将root的左节点入l,右节点入r。 2.分别出队,若出队元素相同 Queuepush(&l, front->left); Queuepush(&l, front->right); Queuepush(&r, behind->right); Queuepush(&r, behind->left); 若不同则返回false 3.直至两队列都为空,返回true
typedef struct TreeNode* datatype;
typedef struct Queuenode
{
datatype data;
struct Queuenode * next;
}Qnode;
typedef struct QT
{
Qnode* head;
Qnode* tail;
int size;
}QT;
void QueueInit(QT* sl)
{
assert(sl);
sl->head = NULL;
sl->tail = NULL;
sl->size = 0;
}
bool Queueempty(QT* sl)
{
assert(sl);
return sl->head ==NULL;
}
void Queuepush(QT* sl, datatype x)
{
assert(sl);
Qnode* newnode = (Qnode*)malloc(sizeof(Qnode));
newnode->next = NULL;
newnode->data = x;
if (Queueempty(sl))
{
sl->head = newnode;
sl->tail = newnode;
}
else
{
sl->tail->next = newnode;
sl->tail = newnode;
}
sl->size++;
}
void Queuepop(QT* sl)
{
assert(sl);
assert(!Queueempty(sl));
Qnode* next = sl->head->next;
free(sl->head);
sl->head = next;
sl->size--;
}
datatype Queuetop(QT* sl)
{
assert(sl);
assert(!Queueempty(sl));
return sl->head->data;
}
void Queuedestroy(QT* sl)
{
assert(sl);
while (!Queueempty(sl))
Queuepop(sl);
sl->head = sl->tail = NULL;
sl->size = 0;
}
bool isSymmetric(struct TreeNode* root) {
if(root==NULL)
return true;
QT l;
QT r;
QueueInit(&l);
QueueInit(&r);
Queuepush(&l,root->left);
Queuepush(&r,root->right);
while (!Queueempty(&r)&&!Queueempty(&l))
{
struct TreeNode* front = Queuetop(&r);
struct TreeNode* behind = Queuetop(&l);
if((front!=NULL&&behind!=NULL)&&front->val==behind->val)
{ Queuepop(&r);
Queuepop(&l);
if(front)
{
Queuepush(&l, front->left);
Queuepush(&l, front->right);
Queuepush(&r, behind->right);
Queuepush(&r, behind->left);
}
}
else if(front==NULL&&behind==NULL)
{
Queuepop(&r);
Queuepop(&l);
}
else if((front!=NULL&&behind==NULL)||(front==NULL&&behind!=NULL))
return false;
else
return false;
}
if(Queueempty(&r)&&Queueempty(&l))
return true;
else
return false;
}
判断「平衡二叉树」的 2 个条件: 1. 是「二叉排序树」 2. 任何一个节点的左子树或者右子树都是「平衡二叉树」(左右高度差小于等于 1)
思路: 1.分别找出根节点的左子树高和右子树高(递归),若相差大于1; 则一定不是AVL树;
int BTreeheight(struct TreeNode* root,int* i)
{
int flag;
if (root == NULL)
{
return 0;
}
int leftHeight = BTreeheight(root->left,i);
int rightHeight= BTreeheight(root->right,i);
if(leftHeight>=rightHeight)
flag=leftHeight-rightHeight;
else
flag=rightHeight-leftHeight;
if(flag>1)
{*i=flag;}
return fmax(leftHeight , rightHeight ) + 1;
}
bool isBalanced(struct TreeNode* root) {
if(root==NULL)
return true;
int i=0;
int height=BTreeheight(root,&i);
if(i>1)
return false;
else
return true;
}
思路: 1.左右节点交换,然后递归左节点与右节点
void change(struct TreeNode* root)
{
if(root)
{
struct TreeNode* flag=root->left;
root->left=root->right;
root->right=flag;
change(root->left);
change(root->right);
}
}
思路: 1.需要先写判断两颗树是否相等的函数 bool isSameTree(struct TreeNode* p, struct TreeNode* q) 2. (1)如果root==NULL;返回false (2)如果isSameTree(root, subroot) 返回true (3)递归 isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot); (必须是||,只要左子树或右子树有一个和subroot相同即可)
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
int i=0;
if(p==NULL&&q==NULL)
return true;
if((p==NULL&&q!=NULL)||(p!=NULL&&q==NULL))
return false;
if(p->val!=q->val)
return false;
else
return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}
bool isSubtree(struct TreeNode * root, struct TreeNode * subRoot) {
if(root==NULL)
return false;
if(isSameTree(root, subRoot))
return true;
return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}
思路: 1.用arr存储字符串,并初始化二叉树BTnode* node 2.建立函数 void newbuynode(BTnode*& L, char* arr, int* i) (这里使用了c++的引用,如果没有引用就得传二级指针,而且不方便) 3.if (L == NULL && arr[*i] != '#') //开辟空间并存储数据 4. else if (arr[*i] != '#') L->data = arr[*i]; (*i)++; //当前数据存储完后要跳向下一位 5. if (L) { newbuynode(L->left, arr, i); newbuynode(L->right, arr, i); } //反义就是如果该节点为空,而且也不需要存储数据,那么就不用递归了
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include <iostream>
using namespace std;
typedef struct BinaryTree {
char data;
struct BinaryTree* left;
struct BinaryTree* right;
} BTnode;
void newbuynode(BTnode*& L, char* arr, int* i) {
if (arr[*i] != '\0') {
if (L == NULL && arr[*i] != '#') {
BTnode* node = (BTnode*)malloc(sizeof(BTnode));
node->data = arr[*i];
node->left = NULL;
node->right = NULL;
L = node;
} else if (arr[*i] != '#')
L->data = arr[*i];
(*i)++;
if (L) {
newbuynode(L->left, arr, i);
newbuynode(L->right, arr, i);
}
}
}
void midorder(BTnode*
root) { //前序排列(根,左子树,右子树)递归思想
if (root == NULL) {
return ;
} else {
midorder(root->left);
printf("%c ",root->data); // 根
midorder(root->right); //右子树
}
}
int main() {
BTnode* node = (BTnode*)malloc(sizeof(BTnode));
node->data = 0;
node->left = NULL;
node->right = NULL;
char arr[100];
int i = 0;
cin.get(arr, 100);
newbuynode(node, arr, &i);
midorder(node);
return 0;
}