做论坛网站的应用,网创,宁波正规优化seo公司,南宁网站推广二叉树 一.快速创建一颗二叉树二.二叉树的遍历1.前序、中序、后序遍历#xff08;深度优先遍历DFS#xff09;2.层序遍历#xff08;广度优先遍历BFS#xff09; 三.二叉树节点的个数四.二叉树叶子节点的个数五.二叉树的高度六.二叉树第k层节点个数七.二叉树查找值为x的节点… 二叉树 一.快速创建一颗二叉树二.二叉树的遍历1.前序、中序、后序遍历深度优先遍历DFS2.层序遍历广度优先遍历BFS 三.二叉树节点的个数四.二叉树叶子节点的个数五.二叉树的高度六.二叉树第k层节点个数七.二叉树查找值为x的节点八.判断二叉树是否是完全二叉树九.二叉树的递归创建十.二叉树的销毁十一.二叉树必做OJ题十二.了解高级树 一.快速创建一颗二叉树 回顾⼆叉树的概念⼆叉树分为空树和非空⼆叉树非空⼆叉树由根结点、根结点的左子树、根结点的右子树组成的 根结点的左子树和右子树分别又是由子树结点、子树结点的左子树、子树结点的右子树组成的因此⼆叉树定义是递归式的后序链式⼆叉树的操作中基本都是按照该概念实现的。
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;BTNode* BuyNode(BTDataType x)
{BTNode* node (BTNode*)malloc(sizeof(BTNode));if (node NULL){perror(malloc fail!);return;}node-data x;node-left node-right NULL;return node;
}BTNode* CreatBinaryTree()
{BTNode* node1 BuyNode(1);BTNode* node2 BuyNode(2);BTNode* node3 BuyNode(3);BTNode* node4 BuyNode(4);BTNode* node5 BuyNode(5);BTNode* node6 BuyNode(6);node1-left node2;node1-right node4;node2-left node3;node4-left node5;node4-right node6;return node1;
}int main()
{BTNode* root CreatBinaryTree();return 0;
}二.二叉树的遍历
1.前序、中序、后序遍历深度优先遍历DFS
按照规则⼆叉树的遍历有前序/中序/后序的递归结构遍历 前序遍历访问根结点的操作发生在遍历其左右子树之前访问顺序为根结点、左子树、右子树 中序遍历访问根结点的操作发生在遍历其左右子树中间访问顺序为左子树、根结点、右子树 后序遍历访问根结点的操作发生在遍历其左右子树之后访问顺序为左子树、右子树、根结点
参考如下 代码如下
//前序遍历
void PrevOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}printf(%d , root-data);PrevOrder(root-left);PrevOrder(root-right);
}//中序遍历
void InOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}InOrder(root-left);printf(%d , root-data);InOrder(root-right);
}//后序遍历
void PosOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}PosOrder(root-left);PosOrder(root-right);printf(%d , root-data);
}int main()
{BTNode* root CreatBinaryTree();PrevOrder(root);printf(\n);InOrder(root);printf(\n);PosOrder(root);printf(\n);return 0;
}前序遍历递归图解 注意已知二叉树的前序和中序后序和中序就可以推导出二叉树的形状但是只知道前序和后序则无法推导出二叉树的形状。 2.层序遍历广度优先遍历BFS 层序遍历除了先序遍历、中序遍历、后序遍历外还可以对二叉树进行层序遍历。设二叉树的根结点所在层数为1层序遍历就是从所在二叉树的根结点出发首先访问第一层的树根结点然后从左到右访问第2层上的结点接着是第三层的结点以此类推自上而下自左至右逐层访问树的结点的过程就是层序遍历。 实现层序遍历需要用到队列拷贝Queue.h与Queue.c文件到本地。
void TreeLevelOrder(BTNode* root)
{Queue q;QueueInit(q);if(root)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);printf(%d , front-val);// NULL无需入队列if(front-left)QueuePush(q, front-left);if (front-right)QueuePush(q, front-right);}QueueDestory(q);
}三.二叉树节点的个数
错误写法 改进方法 最好的方法分治法大问题化为多个小问题、小问题再化为多个小问题…直到不能再分为止
空0个非空左子树右子树1
int TreeSize(BTNode* root)
{if (root NULL)return 0;return TreeSize(root-left) TreeSize(root-right) 1;
}四.二叉树叶子节点的个数
空0个非空若左子树和右子树同时为空返回1否则左子树叶子节点右子树叶子节点
int TreeLeafSize(BTNode* root)
{if (root NULL)return 0;if (root-left NULL root-right NULL)return 1;return TreeLeafSize(root-left) TreeLeafSize(root-right);
}五.二叉树的高度
空0个非空MAX {左子树高度右子树高度} 1
//未记录高度导致重复大量的递归效率极低
//int TreeHeight1(BTNode* root)
//{
// if (root NULL)
// return 0;
//
// return TreeHeight(root-left) TreeHeight(root-right) ?
// TreeHeight(root-left) 1 : TreeHeight(root-right) 1;
//}int TreeHeight(BTNode* root)
{if (root NULL)return 0;int leftHeight TreeHeight(root-left);int rightHeight TreeHeight(root-left);return leftHeight rightHeight ?leftHeight 1 : rightHeight 1;
}六.二叉树第k层节点个数
空0个非空且k1返回1非空且k1左子树的k-1层节点个数右子树的k-1层节点个数
int TreeLevelKSize(BTNode* root, int k)
{if (root NULL)return 0;if (k 1)return 1;return TreeLevelKSize(root-left, k - 1) TreeLevelKSize(root-right, k - 1);
}七.二叉树查找值为x的节点
空返回NULL非空且datax返回root非空且data!x递归左子树递归右子树注意要保存递归的结果层层返回
BTNode* TreeFind(BTNode* root, BTDataType x)
{if (root NULL)return NULL;if (root-data x)return root;BTNode* ret1 TreeFind(root-left, x);if (ret1)return ret1;BTNode* ret2 TreeFind(root-right, x);if (ret2)return ret2;return NULL;
}八.判断二叉树是否是完全二叉树
注意满二叉树可以利用树的高度和节点的个数判断但是完全二叉树前k-1层是满二叉树最后一层不是满的该方法就不行了。
可以利用层序遍历解决方法如下 bool TreeComplete(BTNode* root)
{Queue q;QueueInit(q);if(root)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);//遇到第一个空开始判断if (front NULL)break;QueuePush(q, front-left);QueuePush(q, front-right);}while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);//队列中还有非空节点就不是完全二叉树if (front){QueueDestory(q);return false;} }//队列中没有非空节点就是完全二叉树QueueDestory(q);return true;
}九.二叉树的递归创建
题目已知前序遍历结果abc##de#g##f###其中#是NULL 输出中序遍历的结果不包含NULL #include stdio.h
#includestdlib.htypedef struct BinaryTreeNode
{char val;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;BTNode* CreateTree(char* a, int* pi)
{//遇到#返回NULLif(a[*pi] #){(*pi);return NULL;}//创建根节点BTNode* root (BTNode*)malloc(sizeof(BTNode));root-val a[(*pi)];//递归构建左子树root-left CreateTree(a, pi);//递归构建右子树root-right CreateTree(a, pi);//返回根节点return root;
}void InOrder(BTNode* root)
{if(root NULL)return;InOrder(root-left);printf(%c , root-val);InOrder(root-right);
}int main() {char a[100];scanf(%s, a);int i 0;BTNode* root CreateTree(a, i); //注意要传入地址InOrder(root);
}十.二叉树的销毁
空返回NULL非空后序遍历销毁节点
void TreeDestory(BTNode* root)
{if (root NULL)return;TreeDestory(root-left);TreeDestory(root-right);free(root);
}十一.二叉树必做OJ题
单值二叉树相同的树对称二叉树二叉树的前序遍历二叉树的中序遍历二叉树的后序遍历另一棵树的子树二叉树遍历
十二.了解高级树
