js实现网站浮动窗口,桂林生活网论坛论坛,湖南网站建设 要上磐石网络,遵义市网站建设1.前置说明 我们手动构建一棵二叉树#xff1a; 注意#xff1a;上述代码并不是创建二叉树的方式 从概念中可以看出#xff0c;二叉树定义是递归式的#xff0c;因此后序基本操作中基本都是按照该概念实现的
2.二叉树的遍历
2.1前序、中序以及后序遍历
学习二叉树结构 注意上述代码并不是创建二叉树的方式 从概念中可以看出二叉树定义是递归式的因此后序基本操作中基本都是按照该概念实现的
2.二叉树的遍历
2.1前序、中序以及后序遍历
学习二叉树结构最简单的方式就是遍历
所谓二叉树遍历(Traversal)是按照某种特定的规则依次对二叉树中的节点进行相应的操作并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题
遍历是二叉树上最重要的运算之一也是二叉树上进行其它运算的基础 其实可以这样理解 前序遍历根-左子树-右子树中序遍历左子树-根-右子树后序遍历左子树-右子树-根 以下面这个二叉树为例 前序遍历1-2-3-4-5-6中序遍历3-2-1-5-4-6后序遍历3-2-5-6-4-1
由于被访问的结点必是某子树的根所以N(Node、L(Left subtree和R(Right subtree又可解释为根、根的左子树和根的右子树
NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历
遍历的实现需要用到递归
2.2前序遍历 代码实现是这样的 2.3中序遍历 2.4后序遍历 2.5层序遍历 层序遍历除了先序遍历、中序遍历、后序遍历外还可以对二叉树进行层序遍历。 设二叉树的根节点所在层数为1层序遍历就是从所在二叉树的根节点出发首先访问第一层的树根节点然后从左到右访问第2层上的节点接着是第三层的节点以此类推自上而下自左至右逐层访问树的结点的过程就是层序遍历 我们可以利用队列先进先出的特点来实现 定义一个q队列如果root不为空则将root入队列用front来保存队头数据将队头数据pop打印队头数据然后遍历下一层如果左孩子不为空左孩子入队列右孩子不为空右孩子入队列当队列不为空则继续遍历下一层直到队列为空退出循环 关于这块的指针问题我们画图解释一下 我们修改val也为BTNode*类型 分层打印 我们可以定义一个levelsize保存每一层的数据个数控制一层一层打印 队列的size就是下一层的数据个数 效果是这样的 3.节点个数
3.1二叉树的节点个数 3.1叶子节点个数 4.求树的高度
如果为空 返回0不为空 左子树和右子树高度更高的那个1 5.求第k层的节点个数
如果为空 返回0如果不为空 且k1 返回1如果不为空 且k1 返回左子树的k-1层右子树的k-1层 5.查找值为x的节点 6.构建一棵链式二叉树
假设给一个前序遍历的数组将其构建成一棵二叉树 7.判断完全二叉树
完全二叉树的节点都是连续的所以不可能出现一个NULL节点的后面存在非空节点的情况我们用层序遍历的思路入队列的时候不管是不是NULL节点都入队列出队列的时候如果遇到NULL节点则停止出队列判断后面是否还有非空节点我们用while循环来控制如果队列不为空则出队列如果队头数据有不为空的情况则返回false 8.销毁二叉树
销毁我们为了防止形成野指针从下往上从左往右即后序遍历依次销毁 代码示例
Queue
Queue.h
#pragma once
#include stdio.h
#include stdlib.h
#include stdbool.h
#include assert.h
//创建
typedef struct BTNode* QDataType;
typedef struct QueueNode
{QDataType val;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;
//把队列的头尾封装在一个结构体中//初始化
void QInit(Queue* pq);
//销毁
void QDestroy(Queue* pq);//入队列
void QPush(Queue* pq, QDataType x);
//出队列
void QPop(Queue* pq);
//取队头数据
QDataType QFront(Queue* pq);
//取队尾数据
QDataType QBack(Queue* pq);
//判空
bool QEmpty(Queue* pq);
//返回队列有效元素个数
int QSize(Queue* pq);Queue.c
#define _CRT_SECURE_NO_WARNINGS 1
#includeQueue.h
//初始化
void QInit(Queue* pq)
{assert(pq);pq-phead pq-ptail NULL;pq-size 0;
}
//销毁
void QDestroy(Queue* pq)
{assert(pq);QNode* cur pq-phead;while (cur){QNode* next cur-next;free(cur);cur next;}pq-phead pq-ptail NULL;pq-size 0;
}
//入队列
void QPush(Queue* pq, QDataType x)
{assert(pq);//创建newnodeQNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);return;}newnode-val x;newnode-next NULL;if (pq-ptail NULL){pq-phead pq-ptail newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}
//出队列
void QPop(Queue* pq)
{assert(pq);assert(pq-phead);QNode* del pq-phead;pq-phead pq-phead-next;free(del);del NULL;if (pq-phead NULL){pq-ptail NULL;//防止ptail成为野指针}pq-size--;
}
//取队头数据
QDataType QFront(Queue* pq)
{assert(pq);assert(pq-phead);return pq-phead-val;
}
//取队尾数据
QDataType QBack(Queue* pq)
{assert(pq);assert(pq-ptail);return pq-ptail-val;
}
//判空
bool QEmpty(Queue* pq)
{assert(pq);return pq-phead NULL;
}
//返回队列有效元素个数
int QSize(Queue* pq)
{assert(pq);return pq-size;
}
TreeNode
TreeNode.c
#define _CRT_SECURE_NO_WARNINGS 1
#include stdio.h
#include stdlib.h
#include assert.h
#include stdbool.h
#include Queue.h
//创建
typedef char BTDataType;
typedef struct BTNode
{BTDataType data;struct BTNode* left;struct BTNode* right;
}BTNode;//BTNode* BuyNode(BTDataType x)
//{
// BTNode* node (BTNode*)malloc(sizeof(BTNode));
// node-data x;
// node-left NULL;
// node-right NULL;
// return node;
//}
//构建二叉树
BTNode* BTCreate(BTDataType*a,int*pi)
{if (a[*pi] #){(*pi);return NULL;}BTNode* root (BTNode*)malloc(sizeof(BTNode));if (root NULL){perror(malloc fail);exit(-1);}root-data a[(*pi)];root-left BTCreate(a,pi);root-right BTCreate(a,pi);return root;
}
//先序遍历
void BTPrevOrder(BTNode* root)
{if (root NULL){printf(# );return;}printf(%c , root-data);BTPrevOrder(root-left);BTPrevOrder(root-right);
}
//中序遍历
void BTInOrder(BTNode* root)
{if (root NULL){printf(# );return;}BTInOrder(root-left);printf(%c , root-data);BTInOrder(root-right);
}
//后序遍历
void BTPostOrder(BTNode* root)
{if (root NULL){printf(# );return;}BTPostOrder(root-left);BTPostOrder(root-right);printf(%c , root-data);
}
// 层序遍历
void BTLevelOrder(BTNode* root)
{Queue q;QInit(q);if (root)QPush(q, root);int levelsize 1;while (!QEmpty(q)){while (levelsize--){BTNode* front QFront(q);QPop(q);printf(%c , front-data);if (front-left)QPush(q, front-left);if (front-right)QPush(q, front-right);}printf(\n);levelsize QSize(q);}printf(\n);QDestroy(q);
}
//判断完全二叉树
bool BTComplete(BTNode* root)
{Queue q;QInit(q);if (root)QPush(q, root);int levelsize 1;while (!QEmpty(q)){BTNode* front QFront(q);QPop(q);if (front NULL)break;QPush(q, front-left);QPush(q, front-right);}while (!QEmpty(q)){BTNode* front QFront(q);QPop(q);if (front){QDestroy(q);return false;}}QDestroy(q);return true;
}
//销毁
void BTDestroy(BTNode* root)
{if (root NULL)return;BTDestroy(root-left);BTDestroy(root-right);free(root);
}
//二叉树结点个数
//static int size 0;
int BTSize(BTNode* root)
{/*if (root NULL){return;}size;BTSize(root-left);BTSize(root-right);return size;*/return root NULL ? 0 : BTSize(root-left) BTSize(root-right)1;
}
//叶子节点个数
int BTLSize(BTNode* root)
{/*if (root NULL){return 0;}return root-left NULL root-right NULL ? 1:BTLSize(root-left) BTLSize(root-right);*/return (root NULL ? 0 : (root-left NULL root-right NULL ? 1 :BTLSize(root-left) BTLSize(root-right)));
}
//求树的高度
int BTHeight(BTNode* root)
{if (root NULL)return 0;int leftHeight BTHeight(root-left);int rightHeight BTHeight(root-right);return leftHeight rightHeight ? leftHeight 1 : rightHeight 1;
}
//求第k层的节点个数
int BTLKSize(BTNode* root, int k)
{assert(k 0);if (root NULL)return 0;if (k 1)return 1;return BTLKSize(root-left, k - 1) BTLKSize(root-right, k - 1);
}
//查找值为x的节点
BTNode* BTFind(BTNode* root, BTDataType x)
{if (root NULL)return NULL;if (root-data x)return root;BTNode* leftnode BTFind(root-left, x);if (leftnode)return leftnode;BTNode* rightnode BTFind(root-right, x);if (rightnode)return rightnode;return NULL;
}
int main()
{//char a[] ABD##E#H##CF##G##;char a[] ABC##D##EF##G##;int i 0;BTNode* root BTCreate(a,i);BTPrevOrder(root);printf(\n);BTInOrder(root);printf(\n);BTPostOrder(root);printf(\n);int size1 BTSize(root);printf(%d\n, size1);int size2 BTSize(root);printf(%d\n, size2);int size3 BTLSize(root);printf(%d\n, size3);int h BTHeight(root);printf(%d\n, h);int s BTLKSize(root, 3);printf(%d\n, s);BTLevelOrder(root);printf(%d\n, BTComplete(root));BTDestroy(root);root NULL;return 0;
}
