东莞做网站能赚钱吗,中国建设银行官网电脑版,建设网站的网站底压电工证,dedecms做网站注意事项目录
前言#xff1a;
二叉树的概念与结构
二叉树的链式存储 二叉树的创建
二叉树的销毁
二叉树结点个数计算
二叉树叶子结点个数计算
二叉树第k层节点个数的计算
二叉树高度的计算
二叉树查找值为x的结点 二叉树的遍历
二叉树的前序遍历
二叉树的中序遍历
二叉树…目录
前言
二叉树的概念与结构
二叉树的链式存储 二叉树的创建
二叉树的销毁
二叉树结点个数计算
二叉树叶子结点个数计算
二叉树第k层节点个数的计算
二叉树高度的计算
二叉树查找值为x的结点 二叉树的遍历
二叉树的前序遍历
二叉树的中序遍历
二叉树的后序遍历
二叉树的层序遍历
判断二叉树是否为完全二叉树 前言 二叉树的层序遍历需要使用队列实现队列的实现见数据结构之队列对于二叉树的代码需要不断画递归展开图进行结合理解递归展开图不展开描述 二叉树的概念与结构 一棵二叉树是n个有限结点的集合该集合或者为空或者由一个称为根(root)的结点或者由一个根结点加上两棵别称为左子树和右子树的二叉树组成 ; 二叉树的链式存储 二叉树的链式存储结构指的是用链表表示一棵二叉树即用链表指示元素的逻辑关系 通常的方法是链表中每个结点由三个域组成数据域与左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址; 二叉树的创建
扩展二叉树是指在二叉树中出现空子树的位置增加空树叶所形成的二叉树使得子树成为满二叉树的二叉树叫做扩展二叉树
先序遍历字符串 A B C # # # D # # 其中“#”表示的是空格空格字符代表空树则建立起来的二叉树如下图所示 //二叉树结点结构
typedef int BTDataType;
typedef struct BinaryTreeNode
{struct BinaryTreeNode* left;struct BinaryTreeNode* right;BTDataType val;
}BTNode;
//创建二叉树,返回根结点地址
//A B C # # # D # #
BTNode* CreateTree(char* str, int* pi)
{if (str[*pi] #){(*pi);return NULL;}BTNode* root (BTNode*)malloc(sizeof(BTNode));root-val str[*pi];(*pi);root-left CreateTree(str, pi);root-right CreateTree(str, pi);return root;}
int main()
{char arr[100] { A, B, C, #, #, #, D, #, # };int i 0;BTNode* root CreateTree(arr, i);return 0;
}
二叉树的销毁 按照先销毁其左子树再销毁右子树最后销毁根的顺序递归销毁二叉树 void DestroyTree(BTNode* root)
{if (root NULL)return;DestroyTree(root-left);DestroyTree(root-right);free(root);
}
二叉树结点个数计算 若根结点为空则二叉树结点个数0 若根节点不为空则二叉树结点个数左子树的结点个数右子树极点个数1 //二叉树结点个数
int TreeSize(BTNode* root)
{if (root NULL)return 0;return TreeSize(root-left) TreeSize(root-right) 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);
}
二叉树第k层节点个数的计算 规定二叉树的层数K以1为起点即第一层 k 1; 二叉树的第k层节点个数其左子树的第k-1层节点个数其右子树的第k-1层节点个数 int TreeKLevel(BTNode* root,int k)
{assert(k 0);if (root NULL)return 0;if (k 1)return 1;return TreeKLevel(root-left, k - 1) TreeKLevel(root-right, k - 1);
}
二叉树高度的计算 二叉树的高度左子树的高度与右子树的高度较大值1 //二叉树的高度
int TreeHeight(BTNode* root)
{if (root NULL)return 0;int LeftHeight TreeHeight(root-left);int RightHeight TreeHeight(root-right);return LeftHeight RightHeight ? LeftHeight 1 : RightHeight 1;
}
二叉树查找值为x的结点 如根节点非空先查找根如果根结点处的值即为查找的值直接返回根节点的地址如果根节点处未查找到先查找左子树找到了直接返回找不到继续查找右子树 //二叉树查找值为x的结点
BTNode* TreeFind(BTNode* root, BTDataType x)
{if (root NULL)return NULL;if (root-val x)return root;struct BinaryTreeNode* ret NULL;ret TreeFind(root-left, x);if (ret ! NULL)return ret;ret TreeFind(root-right, x);if (ret ! NULL)return ret;return NULL;
} 二叉树的遍历 前序遍历NLR依次遍历根结点—左子树—右子树中序遍历LNR依次遍历左子树—根结点—右子树后序遍历LRN依次遍历左子树—右子树—根结点 由于二叉树是递归定义的按照下图所示方法便可得到前序遍历的结点顺序 前序遍历结果A-B-D-E-C-F-G 中序遍历结果为D-B-E-A-F-C-G后序遍历结果D-E-B-F-G-C-A 二叉树的前序遍历
//二叉树的前序遍历
void PrevOrder(BTNode* root)
{if (root NULL)return;printf(%c , root-val);PrevOrder(root-left);PrevOrder(root-right);
}
二叉树的中序遍历
//二叉树的中序遍历
void InOrder(BTNode* root)
{if (root NULL)return;InOrder(root-left);printf(%c , root-val);InOrder(root-right);
}
二叉树的后序遍历
//二叉树的后序遍历
void PostOrder(BTNode* root)
{if (root NULL)return;PostOrder(root-left);PostOrder(root-right);printf(%c , root-val);
}
二叉树的层序遍历 二叉树的层序遍历是指将二叉树从上到下从左到右依次遍历如下图所示层序遍历结果为 A—B—D—C 层序遍历的思路如下 1. 判断根结点是否为空非空则入队列 2. 判断队列是否为空不为空则队头元素出队列再将队头元素的孩子入队列若队头元素的孩子为空则不入队列 3.判断队列是否为空将B出队列再将B的孩子入队列 4.判断队列是否为空将D出队列再将D的孩子入队列 5. 判断队列是否为空将C出队列再将C的孩子入队列队列为空时结束遍历 //二叉树的层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{Queue q;InitQueue(q);if (root ! NULL)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* front QueueFront(q);printf(%c , front-val);if (front-left ! NULL);QueuePush(q, front-left);if (front-right ! NULL)QueuePush(q, front-right);QueuePop(q);}DestroyQueue(q);
}判断二叉树是否为完全二叉树 满二叉树当二叉树深度为K二叉树结点个数为2^k-1,则为满二叉树 对满二叉树结点位置进行编号 编号的规则自上而下从左向右 每一节点位置都有元素 完全二叉树 深度为K具有n个结点的二叉树当且仅当其每一个节点都与深度为k的满二叉树中的编号为1~n的节点一 一对应时称为完全二叉树 判断二叉树是否是完全二叉树,是完全二叉树返回true,否则返回false; 利用二叉树层序遍历非空结点连续为完全二叉树非空结点不连续存在空节点,则为非完全二叉树; int BinaryTreeComplete(BTNode* root)
{Queue q;InitQueue(q);if (root ! NULL)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* front QueueFront(q);if (front NULL)break;QueuePush(q, front-left);QueuePush(q, front-right);QueuePop(q);}//若已经出现空结点队列后面结点存在非空结点则为非完全二叉树while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);if (front ! NULL){DestroyQueue(q);return false;}}DestroyQueue(q);return true;
}
