怎么利用网站做产品推广,网站开发pc和手机端,只做正品的网站,178软文网目录 一、基本概念
链式存储概念 二、链式二叉树的结构
链式二叉树结构
构建链式二叉树
二叉树的遍历 二叉树节点和高度等 二叉树销毁
三、链式二叉树的练习
相同的树
对称二叉树 另外一颗子树
二叉树前序遍历 二叉树遍历
四、完整代码
Tree.h
Tree.c
五、总结 一…目录 一、基本概念
链式存储概念 二、链式二叉树的结构
链式二叉树结构
构建链式二叉树
二叉树的遍历 二叉树节点和高度等 二叉树销毁
三、链式二叉树的练习
相同的树
对称二叉树 另外一颗子树
二叉树前序遍历 二叉树遍历
四、完整代码
Tree.h
Tree.c
五、总结 一、基本概念
链式二叉树是一种常见的数据结构它是用链表结点来存储二叉树中的每一个结点结点结构通常包括数据域和若干个指针域。其中指针域用于指向左孩子结点和右孩子结点。
对于那些非完全二叉树由于顺序存储结构的空间利用率低因此二叉树一般都采用链式存储结构。在链式二叉树中根据指针的数量可以分为二叉链和三叉链两种结构。二叉链的结点包含存储数据的变量、存储左孩子的指针以及存储右孩子的指针而三叉链的结点除了包含存储数据的变量、存储左孩子的指针以及存储右孩子的指针还包含存储双亲的指针。
二叉树的遍历是指按某条搜索路径访问树中每个结点使得每个结点均被访问一次而且仅被访问一次。根据访问根结点的顺序不同可以分为前序遍历、中序遍历和后序遍历。
链式存储概念
链式存储二叉树的链式存储结构是指用链表来表示一棵二叉树即用链来指示元素的逻辑关系。 通常的方法是 链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所 在的链结点的存储地址 。链式结构又分为二叉链和三叉链当前我们学习中一般都是二叉链。 二、链式二叉树的结构
链式二叉树结构
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType _data;struct BinaryTreeNode* _left;struct BinaryTreeNode* _right;
}BTNode;
构建链式二叉树
int类型 手撕构建方便前期调试 BTNode* BuyNode(BTDataType x)
{BTNode* newnode (BTNode*)malloc(sizeof(BTNode));if (newnode NULL){perror(malloc err);return NULL;}newnode-_data x;newnode-_left NULL;newnode-_right NULL;return newnode;
}//123nn4n5nn67nn8nn 通过前序遍历构建
BTNode* BinaryTreeCreate()
{BTNode* node1 BuyNode(1);BTNode* node2 BuyNode(2);BTNode* node3 BuyNode(3);BTNode* node4 BuyNode(4);BTNode* node5 BuyNode(5);BTNode* node6 BuyNode(6);BTNode* node7 BuyNode(7);BTNode* node8 BuyNode(8);node1-_left node2;node1-_right node6;node2-_left node3;node2-_right node4;node4-_right node5;node6-_left node7;node6-_right node8;return node1;
}
char数组类型 // 通过前序遍历的数组ABD##E#H##CF##G##构建二叉树
BTNode* BinaryTreeCreateChar(BTDataType* a, int* pi)
{if (a[(*pi)] #){(*pi);return NULL;}BTNode* newnode (BTNode*)malloc(sizeof(BTNode));if (newnode NULL){perror(malloc err);return NULL;}newnode-_data a[(*pi)];newnode-_left BinaryTreeCreateChar(a, pi);newnode-_right BinaryTreeCreateChar(a, pi);return newnode;
}
二叉树的遍历
前序前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
前序遍历递归图解 // 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}printf(%d , root-_data);BinaryTreePrevOrder(root-_left);BinaryTreePrevOrder(root-_right);
}
中序中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中间
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}BinaryTreeInOrder(root-_left);printf(%d ,root-_data);BinaryTreeInOrder(root-_right);
}
后序后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}BinaryTreePostOrder(root-_left);BinaryTreePostOrder(root-_right);printf(%d ,root-_data);
} 层序遍历除了先序遍历、中序遍历、后序遍历外还可以对二叉树进行层序遍历。设二叉树的根节点所在 层数为1层序遍历就是从所在二叉树的根节点出发首先访问第一层的树根节点然后从左到右访问第2层 上的节点接着是第三层的节点以此类推自上而下自左至右逐层访问树的结点的过程就是层序遍历。 // 层序遍历
#includeQueue.h
void BinaryTreeLevelOrder(BTNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* Fout QueueFront(q);QueuePop(q);printf(%d ,Fout-_data);if (Fout-_left){QueuePush(q,Fout-_left);}if (Fout-_right){QueuePush(q, Fout-_right);}}QueueDestroy(q);
}
判断二叉树是否是完全二叉树
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* Fout QueueFront(q);QueuePop(q);if (Fout NULL){break;}QueuePush(q, Fout-_left);QueuePush(q, Fout-_right);}while (!QueueEmpty(q)){BTNode* Fout QueueFront(q);QueuePop(q);if (root){QueueDestroy(q);return false;}}QueueDestroy(q);return true;
} 二叉树节点和高度等
1.二叉树节点个数
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{return root NULL ? 0 : BinaryTreeSize(root-_left) BinaryTreeSize(root-_left)1;
}2.二叉树叶子节点个数
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root NULL)return 0;if (root-_leftNULL root-_rightNULL){return 1;}return BinaryTreeLeafSize(root-_left) BinaryTreeLeafSize(root-_right);
}
3.二叉树的最大高度
//二叉树的最大高度
int TreeHeight(BTNode* root)
{if (root NULL)return 0;int node_leftTreeHeight(root-_left); int node_right TreeHeight(root-_right);return node_left node_right ? node_left 1 : node_right 1;
}
4.二叉树第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);
}
5.二叉树查找值为x的节点
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root NULL)return NULL;if (root-_data x)return root;BTNode* ret1 BinaryTreeFind(root-_left, x);if (ret1)return ret1;BTNode* ret2 BinaryTreeFind(root-_right, x);if (ret2)return ret2;return NULL;}二叉树销毁
// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{if (*(root) NULL)return;BinaryTreeDestory((*root)-_left);BinaryTreeDestory((*root)-_right);free(*(root));
}
三、链式二叉树的练习
相同的树
给你两棵二叉树的根节点 p 和 q 编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同并且节点具有相同的值则认为它们是相同的。 思路 可以通过递归的方式同时遍历两棵树。 比较两棵树的根节点值是否相等如果不相等则直接返回 false。 然后递归地对左子树和右子树分别进行相同的比较只有当左右子树在相应位置上都相同的时候才返回 true。 在递归过程中只要有一处不满足相同条件就可以立即返回 false只有所有节点和结构都完全一致才能最终返回 true。 /*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
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);
} 对称二叉树
给你一个二叉树的根节点 root 检查它是否轴对称。 思路 采用递归的方法。 一个二叉树是轴对称的意味着对于任意一个节点它的左子树和右子树是镜像对称的。 具体来说就是对于当前节点它的左子节点和右子节点的值相等如果都存在的话并且左子节点的左子树和右子节点的右子树对称左子节点的右子树和右子节点的左子树也对称。我们通过递归地比较左右子树的对应节点来判断整个二叉树是否对称。如果在递归过程中发现不满足对称条件的情况就可以返回 false如果递归完整棵树都满足则返回 true。 * Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
bool _isSymmetric(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 _isSymmetric(p-left, q-right)_isSymmetric(p-right, q-left);
}
bool isSymmetric(struct TreeNode* root) {return _isSymmetric(root-left, root-right);
} 另外一颗子树
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在返回 true 否则返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。 思路 我们可以从根节点开始对主树 root 进行先序遍历。 在遍历过程中每当遇到一个节点就判断以这个节点为根的子树是否与 subRoot 完全相同。 为了判断子树是否相同可以编写一个辅助函数来比较两棵树是否完全一致这与前面判断两棵树是否相同的思路类似即同时递归地检查节点值以及左右子树的结构和节点值是否匹配。如果找到匹配的子树就返回 true否则继续遍历主树的其他节点。 /*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/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(rootNULL)return false;if( root-valsubRoot-val isSameTree(root,subRoot))return true;return isSubtree(root-left,subRoot)||isSubtree(root-right,subRoot);
} 二叉树前序遍历
给你二叉树的根节点 root 返回它节点值的 前序 遍历。 思路 首先访问根节点然后递归地对左子树进行前序遍历最后递归地对右子树进行前序遍历。 具体来说我们可以使用一个辅助函数在这个函数中先输出当前节点的值然后如果左子树存在就对左子树调用该函数进行递归遍历接着如果右子树存在就对右子树调用该函数进行递归遍历。这样就可以按照前序遍历的顺序输出所有节点的值。 /*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
/*** Note: The returned array must be malloced, assume caller calls free().*/
int TreeSize(struct TreeNode* root) {return root NULL ? 0 : TreeSize(root-left) TreeSize(root-right) 1;
}
void PrevOrder(struct TreeNode* root,int* a,int* i)
{if(rootNULL)return;a[(*i)]root-val;PrevOrder(root-left,a,i);PrevOrder(root-right,a,i);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{* returnSizeTreeSize(root);int* a(int*)malloc(sizeof(int)*(*returnSize));int i 0;PrevOrder(root,a,i);return a;
} 二叉树遍历 编一个程序读入用户输入的一串先序遍历字符串根据此字符串建立一个二叉树以指针方式存储。 例如如下的先序遍历字符串 ABC##DE#G##F### 其中“#”表示的是空格空格字符代表空树。建立起此二叉树以后再对二叉树进行中序遍历输出遍历结果。 输入描述 输入包括1行字符串长度不超过100。 输出描述 可能有多组测试数据对于每组数据 输出将输入字符串建立二叉树后中序遍历的序列每个字符后面都有一个空格。 每个输出结果占一行。 思路 1. 定义二叉树节点结构体包含节点值以及左右子节点指针。 2. 构建二叉树函数通过遍历输入的先序遍历字符串来构建二叉树。使用一个静态索引来跟踪当前处理的字符位置。如果遇到非#字符就创建一个新节点然后递归地构建左子树和右子树遇到#则表示空节点。 3. 中序遍历函数按照中序遍历的顺序先左子树、当前节点、再右子树输出节点值并添加空格。 4. 在主程序中获取用户输入的字符串调用构建二叉树函数得到二叉树然后调用中序遍历函数输出结果。 #includestdio.h
#includestdlib.htypedef struct Tree {struct Tree* le;struct Tree* ri;int val;
} BTNode;void PrevInor(BTNode* root)
{if (root NULL)return;PrevInor(root-le);printf(%c , root-val);PrevInor(root-ri);
}BTNode* BUTree(char* a,int* pi)
{if(a[*pi] #){(*pi);return NULL;}BTNode* newnode(BTNode*)malloc(sizeof(BTNode));newnode-vala[(*pi)];newnode-leBUTree(a, pi);newnode-riBUTree(a, pi);return newnode;
}
int main()
{char a[100];scanf(%s,a);int i0;BTNode* nodeBUTree(a, i);PrevInor(node);
} 四、完整代码
Tree.h
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.htypedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType _data;struct BinaryTreeNode* _left;struct BinaryTreeNode* _right;
}BTNode;// 通过前序遍历的数组ABD##E#H##CF##G##构建二叉树
BTNode* BinaryTreeCreate();//BTDataType* a, int n, int* pi);
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);
BTNode* BuyNode(BTDataType x);//求二叉树的最长高度
int TreeHeight(BTNode* root);
Tree.c
#define _CRT_SECURE_NO_WARNINGS
#includeTree.hBTNode* BuyNode(BTDataType x)
{BTNode* newnode (BTNode*)malloc(sizeof(BTNode));if (newnode NULL){perror(malloc err);return NULL;}newnode-_data x;newnode-_left NULL;newnode-_right NULL;return newnode;
}/*int n,*/
// 通过前序遍历的数组ABD##E#H##CF##G##构建二叉树
BTNode* BinaryTreeCreateChar(BTDataType* a, int* pi)
{if (a[(*pi)] #){(*pi);return NULL;}BTNode* newnode (BTNode*)malloc(sizeof(BTNode));if (newnode NULL){perror(malloc err);return NULL;}newnode-_data a[(*pi)];newnode-_left BinaryTreeCreateChar(a, pi);newnode-_right BinaryTreeCreateChar(a, pi);return newnode;
}//123nn4n5nn67nn8nn
BTNode* BinaryTreeCreate()
{BTNode* node1 BuyNode(1);BTNode* node2 BuyNode(2);BTNode* node3 BuyNode(3);BTNode* node4 BuyNode(4);BTNode* node5 BuyNode(5);BTNode* node6 BuyNode(6);BTNode* node7 BuyNode(7);BTNode* node8 BuyNode(8);node1-_left node2;node1-_right node6;node2-_left node3;node2-_right node4;node4-_right node5;node6-_left node7;node6-_right node8;return node1;
}
// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{if (*(root) NULL)return;BinaryTreeDestory((*root)-_left);BinaryTreeDestory((*root)-_right);free(*(root));
}
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{return root NULL ? 0 : BinaryTreeSize(root-_left) BinaryTreeSize(root-_left)1;
}
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root NULL)return 0;if (root-_leftNULL root-_rightNULL){return 1;}return BinaryTreeLeafSize(root-_left) BinaryTreeLeafSize(root-_right);
}
// 二叉树第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);
}
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root NULL)return NULL;if (root-_data x)return root;BTNode* ret1 BinaryTreeFind(root-_left, x);if (ret1)return ret1;BTNode* ret2 BinaryTreeFind(root-_right, x);if (ret2)return ret2;return NULL;}
// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}printf(%d , root-_data);BinaryTreePrevOrder(root-_left);BinaryTreePrevOrder(root-_right);
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}BinaryTreeInOrder(root-_left);printf(%d ,root-_data);BinaryTreeInOrder(root-_right);
}
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}BinaryTreePostOrder(root-_left);BinaryTreePostOrder(root-_right);printf(%d ,root-_data);
}
// 层序遍历
#includeQueue.h
void BinaryTreeLevelOrder(BTNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* Fout QueueFront(q);QueuePop(q);printf(%d ,Fout-_data);if (Fout-_left){QueuePush(q,Fout-_left);}if (Fout-_right){QueuePush(q, Fout-_right);}}QueueDestroy(q);
}
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* Fout QueueFront(q);QueuePop(q);if (Fout NULL){break;}QueuePush(q, Fout-_left);QueuePush(q, Fout-_right);}while (!QueueEmpty(q)){BTNode* Fout QueueFront(q);QueuePop(q);if (root){QueueDestroy(q);return false;}}QueueDestroy(q);return true;
}//二叉树的最大高度
int TreeHeight(BTNode* root)
{if (root NULL)return 0;int node_leftTreeHeight(root-_left); int node_right TreeHeight(root-_right);return node_left node_right ? node_left 1 : node_right 1;
}Queue.c(部分)
void QueueInit(Queue* pq)
{assert(pq);pq-phead NULL;pq-ptail NULL;pq-size 0;
}
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-phead;while (cur){QNode* next cur-next;free(cur);cur next;}pq-phead pq-ptail NULL;pq-size 0;
}
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc err);return;}newnode-data x;newnode-nextNULL;if (pq-phead NULL){assert(pq-ptail NULL);pq-phead pq-ptail newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq-phead-next NULL){free(pq-phead);pq-phead pq-ptail NULL;}else {QNode* next pq-phead-next;free(pq-phead);pq-phead next;}pq-size--;
}
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-phead-data;
}
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-phead NULL pq-ptail NULL;
}
五、总结 二叉树全面总结 定义 二叉树是一种特殊的树结构每个节点最多有两个子节点分别称为左子节点和右子节点。 主要特点 • 节点度最大为 2。 • 具有递归结构。 重要类型 • 满二叉树所有节点都有两个子节点且叶子节点都在同一层。 • 完全二叉树除了最后一层其他层都是满的最后一层的叶子节点靠左排列。 遍历方式 • 前序遍历先访问根节点再遍历左子树最后遍历右子树。 • 中序遍历先遍历左子树再访问根节点最后遍历右子树。 • 后序遍历先遍历左子树再遍历右子树最后访问根节点。 • 层次遍历按照层次依次访问节点。 应用 • 高效搜索和排序。 • 表达式树。 • 二叉堆实现优先队列等。 性质 • 在完全二叉树中节点编号与层次存在特定关系。 • 叶子节点数与度为 2 的节点数存在一定关系。 存储方式 • 链式存储通过节点指针连接。 • 数组存储适用于完全二叉树。 常见算法 • 构建二叉树。 • 求深度、高度。 • 查找节点。 • 平衡性判断及调整如 AVL 树、红黑树等。 二叉树是数据结构中的基础且重要部分在计算机科学中有广泛的应用和研究价值。
