平台托管是什么意思_saas系统是什么样的系统_百度软件优化排名_深圳网络营销推广服务

概念

二叉树中一个结点的子树数目称为该结点的度

满二叉树

每一个层的结点数都达到最大值

完全二叉树

除最后一层外，其他层均被填满，且最后一层的节点尽可能靠左排列。允许最后一层存在空缺，但空缺必须位于右侧。

也就是说，k-1层都是满的，只允许第k层不满且叶子必须都位于左侧

完全二叉树特点

1.叶结点只可能在层次最大的那两层出现

2.完全二叉树中由根结点到各个结点的路径长度总和在具有同样结点个数的二叉树中达到了最小，也就是任意一棵二叉树中根结点到各结点的最长路径一定不短于结点数目相同的完全二叉树中的路径长度

扩充二叉树

在二叉树里出现空子树的位置增加空树叶，所形成的二叉树被称为扩充二叉树

如何构造一棵扩充二叉树？只需要

在原二叉树里度数为1的分支结点下增加一个空树叶
在原二叉树的树叶下面增加两个新的空树叶。

扩充二叉树是满二叉树，新增空树叶(称为外部结点)的个数=原二叉树的结点(称为内部结点)个数+1

（方框为扩充的结点）

外部路径与内部路径

外部路径长度(E)：从扩充的二叉树的根到每个外部结点的路径长度之和

内部路径长度(I)：扩充的二叉树里从根到每个内部结点的路径长度之和。

E 和 I 满足：E = I + 2n，其中n是内部结点个数。

性质

性质1. 在二叉树中，第i层上最多有 2^i 个结点（i≥0）

性质2. 深度为k的二叉树至多有 2^(k+1)-1个结点（k≥0）。其中深度(depth)定义为二叉树中层数最大的叶结点的层数。

性质3. 任何一棵二叉树，若其终端结点数（度为0）为n0 ，度为2的结点数为n2，则n0=n2+1

性质4. 满二叉树定理：非空满二叉树树叶数目=其分支结点数+1。

性质5. 满二叉树定理推论：非空二叉树的空子树数目=其结点数+1。

性质6.有n个结点的完全二叉树的高度为log2 (n+1)【向上取整】。其中二叉树的高度定义为二叉树中层数最大的叶结点的层数+1（也就是深度+1）

二叉树应用于表达式的计算

二叉树的周游

(1) 前序法(tLR次序，preorder traversal)。

访问根结点；

按前序周游左子树；

按前序周游右子树。

(2) 中序法(LtR次序，inorder traversal)。

按中序周游左子树；

访问根结点；

按中序周游右子树。

(3) 后序法(LRt次序，postorder traversal)。

按后序周游左子树；

按后序周游右子树；

访问根结点。

已知前/中/后序遍历序列，求二叉树形状

已知前/后序遍历序列+中序遍历序列，求后/前序遍历序列

二叉树的递归遍历代码

前序遍历：void preorder(BinaryTreeNode* root)
{if (root != NULL){visit(root->value);preorder(root->leftchild);preorder(root->rightchild);}
}中序遍历：void inorder(BinaryTreeNode* root)
{if (root != NULL){inorder(root->leftchild);visit(root->value);inorder(root->rightchild);}
}后序遍历：void postorder(BinaryTreeNode* root)
{if (root != NULL){postorder(root->leftchild);postorder(root->rightchild);visit(root->value);}
}

如果这个结点是叶结点，就相当于直接执行 visit() ，所以前序大体思想是先遍历到左子树最高层，然后 visit() ，再返回到叶结点的父结点那一层，执行 visit() ，然后再遍历右子树

深度优先周游二叉树的非递归算法

问题的关键：设置一个栈结构。仿照递归算法执行过程中编译栈的工作原理

前序遍历

老师上课讲的版struct node
{int value;node* left;node* right;node(int x) :value(x), left(nullptr), right(nullptr) {};
};
void PreOrderPlus(node* root)
{if (root == nullptr) return;  // 空树直接返回stack<node*>st;node* pointer = root;st.push(NULL); //将null元素放入栈底，相当于监视哨st.push(pointer); //root入栈while (pointer)  //此时pointer相当于根节点{print(pointer);   //先访问根节点if (pointer->right)  st.push(pointer->right);  //右子树入栈if (pointer->left)   pointer = pointer->left;  //遍历左子树else{pointer = st.top();st.pop();}}
}
void print(node* n)
{cout << n->value << " ";
}

一开始写的错误：在while循环之前把root压入栈中

错误原因：因为root结点已经访问过了，再说右子树也压入栈了，root已经没用了，无需再压入栈

感觉dp写的更好啊......

dp超绝五行版#include <iostream>
#include <stack>
using namespace std;// 二叉树节点结构
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}  // 构造函数
};// 非递归前序遍历函数
void preorderTraversal(TreeNode* root) {if (root == nullptr) return;  // 空树直接返回stack<TreeNode*> st;          // 用于模拟递归的栈st.push(root);                // 根节点入栈while (!st.empty()) {TreeNode* node = st.top();  // 取出栈顶节点st.pop();cout << node->val << " ";   // 访问当前节点（根）// 注意栈的LIFO特性，先右后左才能保证访问顺序是根->左->右if (node->right) st.push(node->right);  // 右子节点入栈if (node->left) st.push(node->left);    // 左子节点入栈}
}// 测试用例
int main() {// 创建示例树：//       1//     /   \//    2     3//   / \//  4   5TreeNode* root = new TreeNode(1);root->left = new TreeNode(2);root->right = new TreeNode(3);root->left->left = new TreeNode(4);root->left->right = new TreeNode(5);cout << "前序遍历结果: ";preorderTraversal(root);  // 应输出：1 2 4 5 3// 注意：实际应用中需要释放内存，此处为简化示例省略return 0;
}

中序遍历

#include<iostream>
#include<stack>
using namespace std;
struct node
{int value;node* left;node* right;int tag = 0;  //为1的时候遍历左子树完成，为2的时候遍历右子树完成node(int x) :value(x), left(nullptr), right(nullptr){};
};
void InOrderPlus(node* root)
{if (root == nullptr) return;  // 空树直接返回stack<node*>st;node* pointer = root;st.push(NULL); //将null元素放入栈底，相当于监视哨while (pointer || !st.empty()){while (pointer)   //遍历左子树到尽头{st.push(pointer);pointer = pointer->left;}//找到栈顶元素（也就是最近处理的那个元素）pointer = st.top();st.pop();//处理当前结点print(pointer);//遍历右子树pointer = pointer->right;}
}
void print(node* n)
{cout << n->value << " ";
}

后序遍历

老师上课讲的代码：

dp给的双栈解法，我觉得更好懂

#include <iostream>
#include <stack>
#include <vector>
using namespace std;// 二叉树节点结构体（与中序遍历保持一致）
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};void postorderTraversal(TreeNode* root) {if (!root) return; // 空树直接返回stack<TreeNode*> mainStack;  // 主栈用于控制遍历顺序stack<TreeNode*> outputStack; // 输出栈用于反转结果vector<int> result;          // 存储最终结果mainStack.push(root); // 根节点先入主栈// 第一阶段：类似"改进版前序遍历"（根->右->左）while (!mainStack.empty()) {TreeNode* current = mainStack.top();mainStack.pop();outputStack.push(current); // 当前节点存入输出栈// 关键点：先左后右入栈，保证出栈顺序为右->左if (current->left) mainStack.push(current->left);if (current->right) mainStack.push(current->right);}// 第二阶段：反转输出栈得到后序（左->右->根）while (!outputStack.empty()) {result.push_back(outputStack.top()->val);//push_back()用于向vector后面添加一个元素outputStack.pop();}// 输出结果for (int num : result) {cout << num << " ";}
}// 示例用法
int main() {/* 构建与中序遍历示例相同的树：1/   \2     3/ 4  后序正确结果：4 2 3 1*/TreeNode* root = new TreeNode(1);root->left = new TreeNode(2);root->right = new TreeNode(3);root->left->left = new TreeNode(4);cout << "后序遍历结果：";postorderTraversal(root); // 输出：4 2 3 1return 0;
}

好巧妙啊哈哈哈哈，mainStack用于存储前序遍历时候的情况，outputStack用于存储

实现一棵二叉树（包含遍历，求深度，求度为1的结点个数）

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define MAX_QUEUE_SIZE 200
typedef int ElemType;	//typedef用来给数据类型起一个别名，详见https://c.biancheng.net/view/298.html
//数据类型
//定义二叉树结构
typedef struct BiTNode {ElemType data;	//数据域struct BiTNodeBiTNode* lChild, * rChild;	//左右子树域
}*BiTree;
typedef struct queue
{BiTNode array[MAX_QUEUE_SIZE];int front;int rear;
}SqQueue;//循环队列基本操作
//初始化队列
SqQueue* Init_CirQueue()
{SqQueue* Q = (SqQueue*)malloc(sizeof(SqQueue));if (!Q)exit(0);Q->front = Q->rear = 0;return(Q);
}
//判断队列是否为空
bool IsEmpty_Queue(SqQueue* Q)
{if (Q->front == Q->rear)return 1;       /*  队列空，返回失败标志  */return 0;
}
//判断队列是否已满
bool IsFull_Queue(SqQueue* Q)
{if ((Q->rear + 1) % MAX_QUEUE_SIZE == Q->front)	/*  队满*/return 1;return 0;
}
//统计队列中元素个数
int Size_Queue(SqQueue* Q)
{return (Q->rear + MAX_QUEUE_SIZE - Q->front) % MAX_QUEUE_SIZE;
}
//往队列中插入元素
bool Push(SqQueue* Q, BiTNode e)
/*  将数据元素e插入到循环队列Q的队尾  */
{if (IsFull_Queue(Q))	/*  队满*/{printf("Insert: The queue is full.\n");return 1;}Q->array[Q->rear].data = e.data;   /*  元素e入队  */Q->array[Q->rear].lChild = e.lChild;Q->array[Q->rear].rChild = e.rChild;Q->rear = (Q->rear + 1) % MAX_QUEUE_SIZE;/*  队尾指针向前移动  */return 0;        /*  入队成功    */
}
//取队首元素
bool Pop(SqQueue* Q, BiTNode* x)
/*  将循环队列Q的队首元素出队  */
{if (IsEmpty_Queue(Q))	/*  队空，返回错误标志    */{printf("The queue is empty.\n");return 1;       /*  队列空，返回失败标志  */}x->data = Q->array[Q->front].data;   /*  取栈顶元素  */x->lChild = Q->array[Q->front].lChild;x->rChild = Q->array[Q->front].rChild;Q->front = (Q->front + 1) % MAX_QUEUE_SIZE;/*  队首指针向前移动  */return 0;
}//先序创建二叉树
int CreateBiTree(BiTree* T)
{ElemType ch;ElemType temp;scanf_s("%d", &ch);temp = getchar();if (ch == -1)*T = NULL;else {*T = (BiTree)malloc(sizeof(BiTNode));if (!(*T))exit(-1);(*T)->data = ch;printf("输入%d的左子节点：", ch);CreateBiTree(&(*T)->lChild);printf("输入%d的右子节点：", ch);CreateBiTree(&(*T)->rChild);}return 1;
}
//先序遍历二叉树
void TraverseBiTree(BiTree T)
{if (T == NULL)return;printf("%d ", T->data);TraverseBiTree(T->lChild);TraverseBiTree(T->rChild);
}
//中序遍历二叉树
void InOrderBiTree(BiTree T)
{if (T == NULL)return;TraverseBiTree(T->lChild);printf("%d ", T->data);TraverseBiTree(T->rChild);
}
//后序遍历二叉树
void PostOrderBiTree(BiTree T)
{if (T == NULL)return;TraverseBiTree(T->lChild);TraverseBiTree(T->rChild);printf("%d ", T->data);
}
//二叉树的深度
int TreeDeep(BiTree T)
{int deep = -1;if (T) {int leftdeep = TreeDeep(T->lChild);int rightdeep = TreeDeep(T->rChild);deep = leftdeep >= rightdeep ? leftdeep + 1 : rightdeep + 1;}return deep;
}int TreeDeep_norecursion(BiTree T)
{int deep = -1;if (T) {SqQueue* Q = NULL;Q = Init_CirQueue();Push(Q, *T);while (!IsEmpty_Queue(Q)){int len = Size_Queue(Q);deep++;while (len--) {BiTNode temp;Pop(Q, &temp);if (temp.lChild)Push(Q, *temp.lChild);if (temp.rChild)Push(Q, *temp.rChild);}}}return deep;
}//求二叉树度为1的结点个数
int Degree1count(BiTree T)
{int num = 0;//补充以下内容if (T == NULL) return 0;if (T->lChild && !T->rChild || !T->lChild && T->rChild){num = 1;}num = num + Degree1count(T->lChild) + Degree1count(T->rChild);return num;
}int Degree1count_norecursion(BiTree T)
{int num = 0;//补充以下内容if (T){SqQueue* Q = NULL;Q = Init_CirQueue();Push(Q, *T);while (!IsEmpty_Queue(Q)){int len = Size_Queue(Q);while (len--){BiTNode temp;Pop(Q, &temp);if (temp.lChild)Push(Q, *temp.lChild);if (temp.rChild)Push(Q, *temp.rChild);if ((temp.lChild && !temp.rChild) || (!temp.lChild && temp.rChild))num++;}}}return num;
}//主函数
int main(void)
{BiTree T;int deepth = -1, num = 0;printf("请输入第一个结点的值,-1表示没有对应子树:\n");CreateBiTree(&T);printf("先序遍历二叉树:\n");TraverseBiTree(T);printf("\n");printf("中序遍历二叉树:\n");InOrderBiTree(T);printf("\n");printf("后序遍历二叉树:\n");PostOrderBiTree(T);printf("\n");deepth = TreeDeep(T);printf("树的深度为:%d", deepth);printf("\n");deepth = TreeDeep_norecursion(T);printf("树的深度为:%d", deepth);printf("\n");num = Degree1count(T);printf("树的度为1的结点个数为:%d", num);printf("\n");num = Degree1count_norecursion(T);printf("树的度为1的结点个数为:%d", num);printf("\n");return 0;
}

二叉树的插入和删除：

#include <iostream>
#include <stack>
#include <vector>
using namespace std;struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class BST {
private:TreeNode* root;
//插入操作【递归版】   这里node是根节点，val为要插入结点的值TreeNode* insertNode(TreeNode* node,int val){if (!node)   //如果访问到叶子了，那就直接创建结点并把这个结点赋给上一层栈中的node->leftreturn new TreeNode(val);if (val < node->val)   //如果值比根节点大node->left = insertNode(node->left, val);  //就和根的左结点继续比较大小//反正递归返回的都是根节点else if (val > node->val)   //如果比根节点小那就和右节点比较大小node->right = insertNode(node->right, val);return node;//逐层递归再返回根节点
// 例子：
//           50（初始node）     
//          /  
//        30
//       /  \
//     20    45}
//插入操作【非递归版】void insertNode2(int val){TreeNode* newnode = new TreeNode(val);if (!root) //如果是空树root = newnode;TreeNode* curr = root;  //从root开始遍历TreeNode* parent = curr; //父节点// 当cur为空的时候，parent为cur的父结点，此时cur和parent岔开while (curr){parent = curr;if (val < curr->val)  curr = curr->left;else if (val > curr->val)  curr = curr->right;}if (val < parent->val) parent->left = newnode;else  parent->right = newnode;}//二叉树删除结点【非递归版】void deleteNode(int val){TreeNode* curr = root;TreeNode* parent = nullptr;bool isLeftChild = false;//查找目标节点while (curr && curr->val != val){parent = curr;if (val < curr->val){curr = curr->left;isLeftChild = true;}else{curr = curr->right;isLeftChild = false;}}if (!curr) return;//处理删除//要删除的结点是叶结点或者只有一个叶子if (!curr->left || !curr->right){TreeNode* child = curr->left ? curr->left : curr->right;if (!parent)   root = child;else if (isLeftChild) parent->left = child;else parent->right = child;delete curr;}//要删除的结点有两个叶子else{TreeNode* successorParent = curr;TreeNode* successor = curr->right;//寻找右子树中最小结点while (successor->left){successorParent = successor;successor = successor->left;}curr->val = successor->val;if (successorParent == curr)  successorParent->right = successor->right;
//            curr (要删除的节点)
//            /  \
//           L    successor(右子树最小节点)
//                    \
//                    RSubTreeelse successorParent->left = successor->right;
//            curr
//            / \
//          L     R
//               /
//                ...
//                  \
//                   successorParent
//                    /
//                successor
//                     \
//                    RSubTree
//                                 关键：successor没有左子结点delete successor;}}
};int main() {}