数据结构之二叉树

2019-11-08 02:27:16

字体：大中小

来源：转载

供稿：网友

数据结构之二叉树

标签（空格分隔）：学习笔记

一、二叉树综述

树形结构是一类重要的非线性数据结构，其中以树和二叉树最为常用。二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2的 i -1次方个结点；深度为k的二叉树至多有2k−1 $2^{k} -1$ 个结点；对任何一棵二叉树T，如果其终端结点数(即叶子结点数)为n0，度为2的结点数为n2，则n0 = n2 + 1。二叉树的链式存储结构是一类重要的数据结构，其形式定义如下：

struct TreeNode{ int val; TreeNode *left, *right;};

二、二叉树的建立

采用递归的方法前序（根左右）建立二叉树，以#符号表示此当前数值为空。

TreeNode* CreateBiTree(){ char ch; TreeNode* T; scanf_s("%c", &ch); if (ch == '#') { T = NULL; } else { T = (TreeNode*)malloc(sizeof(TreeNode)); T->val = ch; T->left = CreateBiTree(); T->right = CreateBiTree(); } return T;//返回根节点}

测试图像：微信截图_20160822110832.png-33.3kB 测试结果：微信截图_20160822111005.png-16.3kB

三、二叉树的遍历

序是根据树根的遍历位置来说的，前序就是先遍历根，后遍历左右子节点比如这样的树 A / / B C 根是A，前序遍历就是ABC，中序就是BAC，后序就是BCA，根据A的位置决定

3.1 前序遍历

void PReOrderTraverse(TreeNode* T){ if (T) { printf("%c", T->val); PreOrderTraverse(T->left); PreOrderTraverse(T->right); }}

3.2 中序遍历

//中序遍历二叉树void MidOrderTraverse(TreeNode* T){ if (T) { MidOrderTraverse(T->left); printf("%c->", T->val); MidOrderTraverse(T->right); }}

3.3 后序遍历

//后序遍历二叉树void BackOrderTraverse(TreeNode* T){ if (T) { BackOrderTraverse(T->left); BackOrderTraverse(T->right); printf("%c->", T->val); }}

3.4二叉树的层次遍历

采用层次遍历的方式递归遍历二叉树的所有元素；

void levelTraverse(TreeNode* T) { vector<TreeNode*> vec; vec.push_back(T); int cur = 0; int end = 1; while (cur < vec.size()) { end = vec.size(); while (cur < end) { cout << vec[cur]->data << " "; if (vec[cur]->lchild) vec.push_back(vec[cur]->lchild); if (vec[cur]->rchild) vec.push_back(vec[cur]->rchild); cur++; } cout << endl; } }

运行结果如下图所示：微信截图_20160822114201.png-5.1kB

四、二叉树的最大深度

给定一个二叉树，其最大深度指的是根节点到所有叶子节点中的最大距离。同样采用递归的方式遍历二叉树，没遍历一次，计数器+1；

int maxDepth(TreeNode *root) { // write your code here if(root == NULL) { return 0; } int max_left=1; int max_right=1; if(root->left != NULL) { max_left = maxDepth(root->left) + 1; } if(root->right != NULL) { max_right = maxDepth(root->right) + 1; } return max_left>max_right?max_left:max_right; }

上一篇：算法导论之图算法

下一篇：VS2013生成dll及动态调用