接单类型网站建设费用,网站建设开发ppt模板,淘宝 wordpress,建盏公司哪几家二叉树的销毁
void BTreeDestroy(BTNode* root)
{if (root NULL)return;BTreeDestroy(root-left);BTreeDestroy(root-right);free(root);
}递归展示图 使用后序销毁#xff0c;如果用前序销毁的话#xff0c;就会找不到根对应的子树的地址.下面就不能被销毁了…二叉树的销毁
void BTreeDestroy(BTNode* root)
{if (root NULL)return;BTreeDestroy(root-left);BTreeDestroy(root-right);free(root);
}递归展示图 使用后序销毁如果用前序销毁的话就会找不到根对应的子树的地址.下面就不能被销毁了所以从子树开始销毁自下而上的销毁方式采用后序.
二叉树的遍历
二叉树的遍历 题目描述 代码实现 #include stdio.h
#include stdlib.h
typedef struct BinaryTreeNode {char data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
} BTNode;
BTNode* BinaryTreeCreate(char*a,int*pi)
{if(a[*pi]#){(*pi);return NULL;}BTNode* root(BTNode*)malloc(sizeof(BTNode));if(rootNULL){perror(malloc fail);}root-dataa[(*pi)];root-leftBinaryTreeCreate(a,pi);root-rightBinaryTreeCreate(a,pi);return root;
}
void InOrder(BTNode* root)
{if(rootNULL)
return ;
InOrder(root-left);
printf(%c ,root-data);
InOrder(root-right);}
int main() {char a[100];scanf(%s,a);int i 0;BTNode*bkBinaryTreeCreate(a, i);InOrder(bk);}思路分析 我们可以根据给定的字符串进行还原二叉树按照先序遍历所以还原出来为下图的样子 因为要输入一段字符串从字符串中读取到二叉树中对应的操作为 char a[100];scanf(%s,a);由于要构建二叉树先构建一个二叉树节点的结构体
typedef struct BinaryTreeNode {char data;//节点数据struct BinaryTreeNode* left;//左子树结点地址struct BinaryTreeNode* right;//右子树结点地址
} BTNode;定义一个创建二叉树的函数
BTNode* BinaryTreeCreate(char*a,int*pi)函数的返回值为树节点的地址参数分别为要构建二叉树的字符串第二个参数是传递构建字符串数组的下标为了防止栈销毁时参数被销毁所以传下标的地址过去下标从0开始. 如果a字符串的第一个元素开始构建二叉树当遇到‘#’相当与构建二叉树的NULLreturn NULL即可并且a数组下标加到下一个元素当遇到一个非‘#’时malloc一个树的结点地址保存在root里面root-dataa[(*pi)];将数据写进该节点*pi表示赋值后,下标指向下一个元素递归调用左子树和右子树同理创建子树然后返回创建好根的地址然后通过中序遍历打印即可.
相同的树
相同的树 题目描述 代码展示
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
if(pNULLqNULL)
return true;
if(pNULL||qNULL)
return false;
if(p-val!q-val)
return false;return isSameTree(p-left,q-left)isSameTree(p-right,q-right);
}代码分析当两个树为空树时两个为相同的树返回true,当程序经过这个判断条件并且没有结束说明两颗树不同时为空 如果一个树为空另一个树不为空则两颗树不相等返回false; 如果程序还没有结束则说明两个树的该节点都不为空判断两个节点存在后如果两个节点不相等则返回false,如果程序还没有结束则说明两颗树的根节点相等接下来递归判断左子树和右子树因为要判断的是两颗树是否相同则必须保证制左子树相同且右子树相同二者是的关系。
翻转二叉树
翻转二叉树 题目描述 代码展示
struct TreeNode* invertTree(struct TreeNode* root) {
if(rootNULL)
return NULL ;
struct TreeNode* leftinvertTree(root-left);
struct TreeNode* rightinvertTree(root-right);
root-leftright;
root-rightleft;
return root;}递归遍历图 根据递归图我们可以看到先发生交换的是两个空节点然后进行1,3的交换然后是6和9的交换. 交换后如上图所示. 然后就是2,7的交换 注意本质上是根节点的左右子树地址的交换.
二叉树的层序遍历
层序遍历除了先序遍历、中序遍历、后序遍历外还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1层序遍历就是从所在二叉树的根节点出发首先访问第一层的树根节点然后从左到右访问第2层上的节点接着是第三层的节点以此类推自上而下自左至右逐层访问树的结点的过程就是层序遍历.
层序遍历的接口
// 层序遍历
void LevelOrder(BTNode* root);实现方法使用队列这种结构当队列中没有数据时我们可以先入队列一个堆顶数据这里着重强调入队的元素为树节点的地址然后队列不为空.先保存队列中元素的地址然后出队列并且打印这个出队列的元素由于已经保存好堆顶节点的地址所以我们可以找到对应的子树当出一个根节点时如果根节点的左右子树不为空地话就将左右子树节点的地址入队列总结是先入队列一个当这个元素出队列时依次入队列他的左子树和右子树的地址在出这个左子树时同理将他的左右子树依次入队列. 图片演示 代码展示 首先是队列的功能函数
typedef struct QListNode
{struct QListNode* next;//保存结点的下一个结点的地址int data;//该节点的数据
}QNode;
typedef struct Queue
{QNode* front;QNode* tail;
}Queue;//定义一个队列结构体指向队列的前结点和尾结点
// 初始化队列
void QueueInit(Queue* q)
{assert(q);q-front q-tail NULL;//头节点尾结点置为NULL}
// 队尾入队列
void QueuePush(Queue* q, int data)
{assert(q);QNode* newnode (QNode*)malloc(sizeof(QNode));//新结点申请空间assert(newnode);//防止申请失败newnode-next NULL;//新节点的下一个结点的地址为空不保存newnode-data data;//新结点的数据if (q-front NULL)//没有一个结点{q-front q-tail newnode;//就让指向头节点和指向尾结点的指针指向新结点}else//有结点{q-tail-next newnode;//新结点尾插到后面q-tail newnode;//移动指向尾结点的指针到队列末尾结点也就是新结点}}// 检测队列是否为空如果为空返回非零结果如果非空返回0
int QueueEmpty(Queue* q)
{return q-front NULL;//如果没有结点,则q-frontNULL,表达式成立返回1表明队列为空}// 队头出队列
void QueuePop(Queue* q)
{assert(q);assert(!QueueEmpty(q));//防止队列为空在出数据if (q-front-next NULL)//如果只有一个结点{q-front q-tail NULL;//那就把这个结点置空指向头结点指针和指向尾结点的指针指向空}else{QNode* next q-front-next;//保存下一个结点的地址free(q-front);//从头结点开始释放一个结点也就是头删q-front next;//指向头结点的指针移动到下一个位置}}
// 获取队列头部元素
int QueueFront(Queue* q)
{assert(q);assert(q-front);//防止头节点为空return q-front-data;//头结点数据}
// 获取队列队尾元素
int QueueBack(Queue* q)
{assert(q);assert(q-tail);//防止尾节点为空return q-tail-data;//尾节点数据}
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{int size 0;//记录元素个数变量assert(q);QNode* cur q-front;//遍历队列的指针先指向头while (cur){size;//遍历记数cur cur-next;}return size;//返回有效数据个数
}
// 销毁队列
void QueueDestroy(Queue* q)
{assert(q);QNode* cur q-front;//遍历队列的指针while (cur){QNode* next cur-next;//保存下一个节点的地址free(cur);//释放掉当前cur指针指向当前位置的空间cur next;//指向下一个位置}q-front q-tail NULL;//防止野指针}层序遍历实现
void LevelOrder(BTNode* root)
{Queue sk;QueueInit(sk);if (root ! NULL){QueuePush(sk,root);}while (!QueueEmpty(sk)){BTNode* frontQueueFront(sk);QueuePop(sk);printf(%d , front-data);if (front-left ! NULL){QueuePush(sk, front-left);}if (front-right ! NULL){QueuePush(sk, front-right);}}QueueDestroy(sk);}包含的头文件
#include stdio.h
#include stdlib.h
#include assert.h
#include stdbool.h判断二叉树是否为完全二叉树 方法层序遍历二叉树会出现数据都是连续的. 如果是这样的则他不是完全二叉树。 如何实现用到了层序遍历我们当队列没数据时先入一个堆顶节点进去和层序遍历一样不同的是如果队前元素为空地话会退出判断队列为空的循环此时检查队列种如果有非空元素则说明该树不是完全二叉树 图示说明 比如说这个例子 如果修改一下
代码展示
bool BTreeComplete(BTNode* root)
{Queue sk;QueueInit(sk);if (root ! NULL){QueuePush(sk, root);}while (!QueueEmpty(sk)){BTNode* front QueueFront(sk);QueuePop(sk);if (front NULL){break;}QueuePush(sk, front-left);QueuePush(sk, front-right);}while (!QueueEmpty(sk)){BTNode* front QueueFront(sk);QueuePop(sk);if (front ! NULL){QueueDestroy(sk);return false;}}QueueDestroy(sk);return true;}注意这里入队列的还是二叉树节点的地址为了方便展示上图演示我用的是元素。
