北京正规网站建设公司,dreawever如何做本地网站,二级域名能查到一级域名吗,营销类网站建营销类网站建设文章目录 1. 二叉树的性质2. 链式结构二叉树3. 二叉树链式结构的4种遍历方式4. 二叉树节点个数5. 二叉树的叶子节点个数6. 二叉树第k层节点个数7. 二叉树的高度/深度8. 二叉树查找值为x的节点9. 二叉树的销毁10. 判断是否为完全二叉树11. 二叉树练习题11.1 单值二叉树11.2 相同… 文章目录 1. 二叉树的性质2. 链式结构二叉树3. 二叉树链式结构的4种遍历方式4. 二叉树节点个数5. 二叉树的叶子节点个数6. 二叉树第k层节点个数7. 二叉树的高度/深度8. 二叉树查找值为x的节点9. 二叉树的销毁10. 判断是否为完全二叉树11. 二叉树练习题11.1 单值二叉树11.2 相同的树11.3 另一棵树的子树11.4 二叉树的前序遍历11.5 二叉树遍历 1. 二叉树的性质 假设一个二叉树有a个度为2的节点b个度为1的节点c个度为0的节点那么该二叉树的边数是2ab abc-1二叉树的边数等于其节点数-1二叉树度为2的节点数等于度为0的节点数-1完全二叉树的高度h log2(n1) 2为底n1为对数n为二叉树节点数若完全二叉树的节点数为2n个那么它的叶子节点数为n若完全二叉树的节点数为2n-1个那么它的叶子节点数为n 2. 链式结构二叉树 链式二叉树的数据结构 3. 二叉树链式结构的4种遍历方式 前序遍历----根左右原则 //前序遍历
void PreOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}printf(%c , root-data);PreOrder(root-left);PreOrder(root-right);
}兄弟们感受一下函数递归的暴力美学吧 中序遍历----左根右原则 //中序遍历
void InOrder(BTNode* root)
{if (root NULL){printf(NULL );return ;}InOrder(root-left);printf(%c , root-data);InOrder(root-right);
}后序遍历----左右根原则 //后序遍历
void PostOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}PostOrder(root-left);PostOrder(root-right);printf(%c , root-data);
}层序遍历除了先序遍历、中序遍历、后序遍历外还可以对二叉树进行层序遍历。设二叉树的根结点所在层数为1层序遍历就是从所在二叉树的根结点出发首先访问第一层的树根结点然后从左到右访问第2层上的结点接着是第三层的结点以此类推自上而下自左至右逐层访问树的结点的过程就是层序遍历实现层序遍历需要额外借助数据结构队列 //层序遍历
void LevelOrder(BTNode* root)
{//队列Queue q;QueueInit(q);//初始化QueuePush(q, root);//根节点入队//队列不为空while (!QueueEmpty(q)){BTNode* top QueueFront(q);//取队头QueuePop(q);//销毁队头printf(%c , top-data);//打印队头//取出的队头的左子结点不为空入队if (top-left){QueuePush(q, top-left);}//取出的队头的右子结点不为空入队if (top-right){QueuePush(q, top-right);}}QueueDestroy(q);//销毁队列
}
4. 二叉树节点个数 //二叉树节点数个数
int BinaryTreeSize(BTNode* root)
{if (root NULL){return 0;}return 1 BinaryTreeSize(root-left) BinaryTreeSize(root-right);
}5. 二叉树的叶子节点个数 //二叉树的叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root NULL){return 0;}if (root-left NULL root-right NULL){return 1;}return BinaryTreeLeafSize(root-left) BinaryTreeLeafSize(root-right);
}6. 二叉树第k层节点个数 //二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root NULL){return 0;}if (k 1){return 1;}return BinaryTreeLevelKSize(root-left, k - 1) BinaryTreeLevelKSize(root-right, k - 1);
}7. 二叉树的高度/深度 //二叉树的高度/深度
int BinaryTreeDepth(BTNode* root)
{if (root NULL){return 0;}int leftDep BinaryTreeDepth(root-left);int rightDep BinaryTreeDepth(root-right);return 1 (leftDep rightDep ? leftDep : rightDep);
}8. 二叉树查找值为x的节点 //查找二叉树中值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root NULL){return NULL;}if (root-data x){return root;}BTNode* leftFind BinaryTreeFind(root-left, x);if (leftFind){return leftFind;}BTNode* rightFind BinaryTreeFind(root-right, x);if (rightFind){return rightFind;}//二叉树没有这个节点return NULL;
}9. 二叉树的销毁 //二叉树的销毁
void BinaryTreeDestory(BTNode** root)
{if (*root NULL){return;}BinaryTreeDestory(((*root)-left));BinaryTreeDestory(((*root)-right));free(*root);*root NULL;
}10. 判断是否为完全二叉树 //判断二叉树是否为完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(q);QueuePush(q, root);//根节点入队//第一次遍历非空队列找NULLwhile (!QueueEmpty(q)){BTNode* top QueueFront(q);//取队头QueuePop(q);//出队头if (top NULL){break;}QueuePush(q, top-left);//队头的左孩子入队QueuePush(q, top-right);//队头的右孩子入队}//第二次遍历找NULL后是否有非NULL节点while (!QueueEmpty(q)){BTNode* top QueueFront(q);//取队头QueuePop(q);//出队头if (top ! NULL){QueueDestroy(q);//销毁队列return false;}}//第二次循环中没有NULLQueueDestroy(q);return true;
}11. 二叉树练习题
11.1 单值二叉树 bool isUnivalTree(struct TreeNode* root)
{//如果根节点为NULL它也是单值二叉树if(root NULL){return true;}//如果根节点的左孩子节点存在且该节点的值不等于其左孩子节点的值if(root-left root-val ! root-left-val){return true;}//如果根节点的右孩子节点存在且该节点的值不等于其右孩子节点的值if(root-right root-val ! root-right-val){return true;}//说明当前节点和它的左孩子右孩子节点的值相等return isUnivalTree(root-left) isUnivalTree(root-right);
}11.2 相同的树 bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{//两个二叉树都为空if(p NULL q NULL){return true;}//一个二叉树为空另一个二叉树非空if(p NULL || q NULL){return false;}//两个二叉树都是非空if(p-val ! q-val){return false; //值不同返回}return isSameTree(p-left,q-left) isSameTree(p-right,q-right);
}11.3 另一棵树的子树 bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{//两个二叉树都为空if(p NULL q NULL){return true;}//一个二叉树为空另一个二叉树非空if(p NULL || q NULL){return false;}//两个二叉树都是非空if(p-val ! q-val){return false; //值不同返回}return isSameTree(p-left,q-left) isSameTree(p-right,q-right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{//如果传过来的节点为空if(root NULL){return false;}//如果root和subRoot两个二叉树相同if(isSameTree(root,subRoot)){return true;}//root和subRoot不是相同的树//分别判断subRoot是否是root的左子树和右子树return isSubtree(root-left,subRoot) || isSubtree(root-right,subRoot);
}11.4 二叉树的前序遍历 typedef struct TreeNode TreeNode;//求二叉树节点个数int TreeSize(TreeNode* root){if(root NULL){return 0;}return 1 TreeSize(root-left) TreeSize(root-right);}//前序遍历--根左右void PreOrder(TreeNode* root,int* arr,int* p){if(root NULL){return ;}arr[(*p)] root-val;PreOrder(root-left,arr,p);PreOrder(root-right,arr,p);}
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{//先求出二叉树节点的个数*returnSize TreeSize(root);//为数组arr申请节点空间int* arr (int*)malloc(sizeof(int)*(*(returnSize)));if(arr NULL){exit(1);}int i 0;PreOrder(root,arr,i);return arr;
}11.5 二叉树遍历 #include stdio.h
#include stdlib.h
typedef char BTDataType;
//创建二叉树的数据结构
typedef struct BinaryNode
{BTDataType data;struct BinaryNode* left;struct BinaryNode* right;
}BTNode;
//申请节点
BTNode* buyNode(char x)
{BTNode* node (BTNode*)malloc(sizeof(BTNode));node-data x;node-left node-right NULL;return node;
}//创建二叉树---根左右
BTNode* CreaterTreeNode(char* arr, int* p)
{if(arr[*p] #){(*p);return NULL;}//如果读取到的数组元素不是#BTNode* root buyNode(arr[*p]);(*p);root-left CreaterTreeNode(arr, p);root-right CreaterTreeNode(arr, p);return root;
}
//中序遍历
void InOrder(BTNode* root)
{if(root NULL){return;}//非空InOrder(root-left);printf(%c ,root-data);InOrder(root-right);
}
int main()
{//创建数组char arr[100];scanf(%s,arr);//读取字符串//创建二叉树int i 0;//数组下标BTNode* root CreaterTreeNode(arr,i);//中序遍历InOrder(root);return 0;
}
