二叉树详解(深度优先遍历、前序,中序,后序、广度优先遍历、二叉树所有节点的个数、叶节点的个数) |
您所在的位置:网站首页 › 后序遍历英文翻译是什么 › 二叉树详解(深度优先遍历、前序,中序,后序、广度优先遍历、二叉树所有节点的个数、叶节点的个数) |
一、树概念及结构(了解) 1.1树的概念 ![]() 树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它
叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。
有一个特殊的结点,称为根结点,根节点没有前驱结点除根节点外,其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm,其中每一个集合Ti(1data = a[*pi];
++(*pi);
// 递归地创建左子树和右子树
root->left = CreatTree(a, pi);
root->right = CreatTree(a, pi);
return root; // 返回新创建的节点
}4.4前序,中序,后序(深度优先遍历) 方法二:传址调用 代码语言:javascript复制// 定义TreeSize函数,用于计算二叉树的大小(节点数) // 参数:root - 指向二叉树根节点的指针;psize - 指向一个整数的指针,用于存储节点数 void TreeSize(BTNode* root, int* psize) { // 如果根节点为空(即树为空),则直接返回,不执行任何操作 if (root == NULL) { return; } else // 如果根节点不为空(即树非空) { // 通过解引用psize指针来递增其指向的整数值,表示当前节点被计数 ++(*psize); } // 递归调用TreeSize函数来计算左子树的大小 TreeSize(root->left, psize); // 递归调用TreeSize函数来计算右子树的大小 TreeSize(root->right, psize); }方法三:递归、分治思想: 否则,返回左子树节点数 + 右子树节点数 + 1(当前节点) 代码语言:javascript复制int TreeSize(BTNode* root) { // 如果树为空(即根节点为NULL),则返回0 // 否则,返回左子树节点数 + 右子树节点数 + 1(当前节点) return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1; }![]() ![]() ![]() ![]() 这是使用的队列的代码 代码语言:javascript复制//队列初始化 void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; } //队列的销毁 void QueueDestory(Queue* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->head = pq->tail = NULL; } // 队尾入 void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { printf("malloc fail\n"); exit(-1); } newnode->data = x; newnode->next = NULL; if (pq->tail == NULL) { pq->head = pq->tail = newnode; //表示这是第一个节点 } else { pq->tail->next = newnode; //tail的后面加上新节点 pq->tail = newnode; //再让tail指向newnode } } // 队头出 void QueuePop(Queue* pq) { assert(pq); assert(pq->head); // 1、一个 // 2、多个 if (pq->head->next == NULL) { free(pq->head);//释放队头的空间 pq->head = pq->tail = NULL; //队列为空 } else { QNode* next = pq->head->next; //存储队头下一个节点的空间 free(pq->head); //释放队头的空间 pq->head = next; //让队头指向之前队头的下一个节点 } } //队头数据 QDataType QueueFront(Queue* pq) { assert(pq); assert(pq->head); return pq->head->data; } //队尾数据 QDataType QueueBack(Queue* pq) { assert(pq); assert(pq->head); return pq->tail->data; } //队列数据个数 int QueueSize(Queue* pq) { assert(pq); int size = 0; QNode* cur = pq->head; while (cur) { ++size; cur = cur->next; } return size; } //判断队列是否为空 bool QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL; }代码语言:javascript复制// 层序遍历二叉树 void LevelOrder(BTNode* root) { // 定义一个队列q Queue q; // 初始化队列 QueueInit(&q); // 如果根节点不为空 if (root) { // 将根节点入队 QueuePush(&q, root); } // 当队列不为空时循环 while (!QueueEmpty(&q)) { // 取出队列的队首元素,但不从队列中移除 BTNode* front = QueueFront(&q); // 从队列中移除队首元素 QueuePop(&q); // 访问队首元素的数据 printf("%c ", front->data); // 如果队首元素有左子节点,将左子节点入队 if (front->left) { QueuePush(&q, front->left); } // 如果队首元素有右子节点,将右子节点入队 if (front->right) { QueuePush(&q, front->right); } } // 销毁队列,释放其占用的资源 QueueDestory(&q); } ![]() 新年第一篇!!! 祝大家新年快乐 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |