北京海淀区网站开发,海淀区手机网站制作服务,wordpress 移动社交主题,wordpress仿导航大全目录
1.二叉树的定义
2.创建二叉树
3.递归遍历二叉树
1#xff09;前序遍历
2#xff09;中序遍历
3#xff09;后序遍历
4.层序遍历
5.计算节点个数
6.计算叶子节点个数
7.计算第K层节点个数
8.计算树的最大深度
9.查找值为x的节点
10.二叉树的销毁 从二叉树…目录
1.二叉树的定义
2.创建二叉树
3.递归遍历二叉树
1前序遍历
2中序遍历
3后序遍历
4.层序遍历
5.计算节点个数
6.计算叶子节点个数
7.计算第K层节点个数
8.计算树的最大深度
9.查找值为x的节点
10.二叉树的销毁 从二叉树的概念中我们知道任何二叉树都难被分为根左子树右子树而左子树依然能被分为根左子树右子树。右子树也是所以我们这里可以采用递归的玩法来操作二叉树。
1.二叉树的定义
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;
2.创建二叉树
由于是初学为了便于观察我们这里手搓一个二叉树
BTNode* CreateTree()
{BTNode* n1 (BTNode*)malloc(sizeof(BTNode));assert(n1);BTNode* n2 (BTNode*)malloc(sizeof(BTNode));assert(n2);BTNode* n3 (BTNode*)malloc(sizeof(BTNode));assert(n3);BTNode* n4 (BTNode*)malloc(sizeof(BTNode));assert(n4);BTNode* n5 (BTNode*)malloc(sizeof(BTNode));assert(n5);BTNode* n6 (BTNode*)malloc(sizeof(BTNode));assert(n6);BTNode* n7 (BTNode*)malloc(sizeof(BTNode));assert(n7);n1-data 1;n2-data 2;n3-data 3;n4-data 4;n5-data 5;n6-data 6;n1-left n2;n1-right n4;n2-left n3;n2-right NULL;n3-left NULL;n3-right n7;n4-left n5;n4-right n6;n5-left NULL;n5-right NULL;n6-left NULL;n6-right NULL;n7-left NULL;n7-right NULL;n7-data 7;return n1;} 注意上述代码并不是创建二叉树的方式真正创建二叉树方式后序详解重点讲解。 3.递归遍历二叉树
根左子树右子树遍历顺序的不同导致访问的结果也不同先学习这三种遍历这里递归较为简单为我们后面做一些二叉树的oj题目打下基础。
按照规则二叉树的遍历有前序/中序/后序的递归结构遍历
1前序遍历
前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
// 二叉树前序遍历
void PreOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}printf(%d , root-data);PreOrder(root-left);PreOrder(root-right);
}
2中序遍历
中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中间。
// 二叉树中序遍历
void InOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}InOrder(root-left);printf(%d , root-data);InOrder(root-right);
}
3后序遍历
后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。
// 二叉树后序遍历
void PostOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}PostOrder(root-left);PostOrder(root-right);printf(%d , root-data);
}
4.层序遍历 层序遍历自上到下自左到右依次访问数的结点就是层序遍历。 思想借助一个队列 1、先将根节点入队然后开始从队头出数据 2、出队头的数据同时将队头左右子树的结点入队遇到NULL则不入队 3、重复第二步直到队列为空
//层序遍历
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-data);if (front-left)QueuePush(q, front-left);if (front-right)QueuePush(q, front-right);}printf(\n);
}
5.计算节点个数
求树的结点总数时可以将问题拆解成子问题 1.若为空则结点个数为0。 2.若不为空则结点个数 左子树结点个数 右子树结点个数 1自己
int TreeSize(BTNode* root)
{return root NULL ? 0 : TreeSize(root-left) TreeSize(root-right) 1;
}6.计算叶子节点个数 子问题拆解 1.若为空则叶子结点个数为0。 2.若结点的左指针和右指针均为空则叶子结点个数为1。 3.除上述两种情况外说明该树存在子树其叶子结点个数 左子树的叶子结点个数 右子树的叶子结点个数。
//叶子节点个数
int TreeLeaSize(BTNode* root)
{if (root NULL)return 0;return (root-left NULL root-right NULL) ? 1 : TreeLeaSize(root-left) TreeLeaSize(root-right);
}
7.计算第K层节点个数 这里我们要控制好递归的深度我们依然把他给转换为子问题思考。
思路
1、为空和非法时结点个数为0个 2、为第一层时结点个数为1个 3、不为空且合法时第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);
} 8.计算树的最大深度
我们如何找出最深的那一条途径这里是一个选择的问题。如果一条途径递归到倒数第二层左边有一个叶子节点右边无节点那么我们应该选择左边作为它的最深途径。
思路
1.若为空则深度为0。 2.若不为空则树的最大深度 左右子树中深度较大的值 1。
int TreeHeigh(BTNode* root)
{if (root NULL)return 0;return TreeHeigh(root-left) TreeHeigh(root-right) ? TreeHeigh(root-left) 1 :TreeHeigh(root-right) 1;
}
9.查找值为x的节点
思路 1.先判断根结点是否是目标结点。 2.再去左子树中寻找。 3.最后去右子树中寻找。
BTNode* TreeFind(BTNode* root, BTDataType x)
{if (root NULL){return NULL;}if (root-data x){return root;}//先去左树找BTNode* lret TreeFind(root-left, x);if (lret)return lret;//再去右树找BTNode* rret TreeFind(root-right, x);if (rret)return rret;return NULL;
}10.二叉树的销毁
void BinaryTressDestory(BTNode* root)
{if (root NULL)return;BinaryTressDestory(root-left);BinaryTressDestory(root-right);free(root);
}
