数据结构-二叉树-头歌（交换左右子树/寻找最长路径（长度及路径）/WPL/双序遍历/二叉树最大宽度/二叉树表达数）

穆月月

1221人浏览 · 2023-11-17 21:17:46

穆月月 · 2023-11-17 21:17:46 发布

//交换左右子树

#include<iostream>
#include<cstring>
using namespace std;
typedef struct BiTNode
{
	char data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void CreateBiTree(BiTree &T,char S[],int &i)
{//先序建立二叉树
	if(S[i]=='0')
		T=NULL;
	else
	{
		T=new BiTNode;
		T->data=S[i];
		CreateBiTree(T->lchild,S,++i);
		CreateBiTree(T->rchild,S,++i);
	}
}
void ChangeRL(BiTree &T)
{//二叉树左右孩子的交换
/**************begin************/ 
 if (T == 0) {
        return;
    }
	BiTNode *temp;
    temp=T->lchild;
    T->lchild=T->rchild;
    T->rchild=temp;
    ChangeRL(T->lchild);
    ChangeRL(T->rchild);
    
    /**************end************/
}
void PreOrderTraverse(BiTree T)
{//先序遍历
	if(T)
	{
    	cout<<T->data;
		PreOrderTraverse(T->lchild);
		PreOrderTraverse(T->rchild);
	}
}
int main()
{
	char S[100];
	while(cin>>S)
    {
        if(strcmp(S,"0")==0) break;
		int i=-1;
	  	BiTree T;
		CreateBiTree(T,S,++i);
		ChangeRL(T);
		PreOrderTraverse(T);
		cout<<endl;
	}
	return 0;
}

基于二叉链表的二叉树的双序遍历

#include<iostream>
#include <string.h>
using namespace std;
typedef struct BiTNode
{
	char data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void CreateBiTree(BiTree &T,char S[],int &i)
{//先序建立二叉树
	if(S[i]=='0')
		T=NULL;
	else
	{
		T=new BiTNode;
		T->data=S[i];
		CreateBiTree(T->lchild,S,++i);
		CreateBiTree(T->rchild,S,++i);
	}
}
void DoubleTraverse(BiTree T)
{//双序遍历二叉树T的递归算法
/**************begin************/
if (T==0) {
  return;  
}

cout<<T->data;
DoubleTraverse(T->lchild);
cout<<T->data;
DoubleTraverse(T->rchild);
    /**************end************/
}
int main()
{
	char S[100];
	while(cin>>S)
    {
        if(strcmp(S,"0")==0) break;
        int i=-1;
	  	BiTree T;
		CreateBiTree(T,S,++i);
		DoubleTraverse(T);
		cout<<endl;
	}
	return 0;
}

基于二叉链表的二叉树最大宽度的计算

#include <iostream>
#include <string.h>
#include <queue>
#include <stdlib.h>
using namespace std;

typedef struct BiTNode
{
    char data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

BiTree CreateBiTree(int &pos, char *str)
{// 先序建立二叉树
    char c=str[pos++];
    if(c=='0') return NULL;
    BiTree root=new BiTNode();
    root->data=c;
    root->lchild=CreateBiTree(pos,str);
    root->rchild=CreateBiTree(pos,str);
    return root;
}

int Width(BiTree T)
{// 求二叉树T最大宽度
/**************begin************/
 int max=0;
        queue <BiTree> q;
        if (T==0) {
            return 0;
        }
    if (T !=NULL)
    {
        q.push(T);   //根节点进队列
    }
  
    while (q.empty() == false)  //队列不为空判断
    {
        int size = q.size();
        while(size--)//遍历当前层的元素
            {
                BiTNode* temp=q.front();
                q.pop();
                if(temp->lchild) q.push(temp->lchild);
                if(temp->rchild) q.push(temp->rchild);
            }
        if(max<q.size())max=q.size();
        }
        return max;
    /**************end************/
}

int main()
{
    char str[1000];
    while(cin>>str)
    {
        if(strcmp(str,"0")==0) break;
        int pos=0;                         // 标记字符串处理位置
        BiTree root=CreateBiTree(pos,str);
        cout<<Width(root)<<endl;
    }
    return 0;
}

基于二叉链表的二叉树最长路径的求解

#include<iostream>
#include<vector>
#include<queue>
#define MAXSIZE 100
using namespace std;
typedef struct BiTNode
{
	char data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void CreateBiTree(BiTree &T,char S[],int &i)
{//程序生成器
	if(S[i]=='0')
		T=NULL;
	else
	{
		T=new BiTNode;
		T->data=S[i];
		CreateBiTree(T->lchild,S,++i);
		CreateBiTree(T->rchild,S,++i);
	}
}
void LongestPath(BiTree T)
{
    if (T == nullptr)
    {
        cout << "The tree is empty." << endl;
        return;
    }

    vector<char> currentPath;
    vector<char> longestPath;

    queue<pair<BiTree, vector<char>>> q;
    q.push({T, {T->data}});

    while (!q.empty())
    {
        auto current = q.front();
        q.pop();

        BiTree node = current.first;
        vector<char> currentPath = current.second;

        if (node->lchild == nullptr && node->rchild == nullptr)
        {
            if (currentPath.size() > longestPath.size())
            {
                longestPath = currentPath;
            }
        }

        if (node->lchild != nullptr)
        {
            vector<char> newPath = currentPath;
            newPath.push_back(node->lchild->data);
            q.push({node->lchild, newPath});
        }

        if (node->rchild != nullptr)
        {
            vector<char> newPath = currentPath;
            newPath.push_back(node->rchild->data);
            q.push({node->rchild, newPath});
        }
    }
    cout << longestPath.size() << endl;
    for (char node : longestPath)
    {
        cout << node;
    }
 cout << endl;

}
int main()
{
	char S[100];
	while(cin>>S&&S[0]!='0')
	{
		int i=-1;
		BiTree T;
		CreateBiTree(T,S,++i);
		LongestPath(T);
	}
	return 0;
}

基于二叉链表的二叉树叶子结点到根结点的路径的求解

#include<iostream>
using namespace std;
char path[100];  //路径数组，存储路径上每个结点的值
typedef struct BiTNode
{
	char data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void CreateBiTree(BiTree &T,char S[],int &i)
{//先序建立二叉树
	if(S[i]=='0')
		T=NULL;
	else
	{
		T=new BiTNode;
		T->data=S[i];
		CreateBiTree(T->lchild,S,++i);
		CreateBiTree(T->rchild,S,++i);
	}
}
void AllPath(BiTree T,char path[],int pathlen)
{//二叉树叶子结点到根结点的路径的求解
/**************begin************/
if (T==0) {
    return;
}
path [pathlen]=T->data;
pathlen++;
    if (T->lchild==0&&T->rchild==0) {
        //叶子结点     
        for(int i=0;i<pathlen;i++){
            cout<<path[pathlen-i-1];
        }
        cout<<endl;
    }
    else{
        AllPath(T->lchild,path,pathlen);
        AllPath(T->rchild,path,pathlen);
    }
    
    /**************end************/
}
int main()
{
	char S[100];
	while(cin>>S&&S[0]!='0')
	{
		int i=-1;
		BiTree T;
		CreateBiTree(T,S,++i);
		int pathlen=0;         //初始化路径到根结点的长度为0
        AllPath(T,path,pathlen);
	}
	return 0;
}

基于二叉树的表达式求值

#include<iostream>
#define MAXSIZE 100
using namespace std;
typedef struct BiTNode
{//二叉树的双链表存储表示
	double data;          //结点数据域
	bool ischaracter;      //判断结点是否为字符
	struct BiTNode *lchild,*rchild;    //左右孩子指针
}BiTNode,*BiTree;
typedef struct
{//字符栈的存储结构
	char *base;     //栈底指针
	char *top;       //栈顶指针
	int stacksize;   //栈可用的最大容量
}SqStack1;
typedef struct
{//结点栈的存储结构
	BiTree *base;
	BiTree *top;
	int stacksize;
}SqStack2;
void InitStack1(SqStack1 &s)
{//字符栈的初始化
	s.base=new char[MAXSIZE];  //为顺序栈动态分配一个最大容量为MAXSIZE的数组空间
	s.top=s.base;              //初始为空栈
	s.stacksize=MAXSIZE;        //置栈的最大容量为MAXSIZE
}
void InitStack2(SqStack2 &s)
{//结点栈的初始化
	s.base=new BiTree[MAXSIZE];
	s.top=s.base;
	s.stacksize=MAXSIZE;
}
void Push1(SqStack1 &s,char ch)
{//字符入栈操作
	if(s.top-s.base==s.stacksize)   //栈满
		return;
	*s.top=ch;    //元素ch压入栈顶
	s.top++;       //栈顶指针加1
}
void Push2(SqStack2 &s,BiTree t)
{//结点入栈操作
	if(s.top-s.base==s.stacksize)
		return;
	*s.top=t;
	s.top++;
}
void Pop1(SqStack1 &s,char &ch)
{//字符出栈操作
	if(s.top==s.base)     //栈空
		return;
	else
	{
		s.top--;     //栈顶指针减1
		ch=*s.top;   //将栈顶元素赋给ch
	}
}
void Pop2(SqStack2 &s,BiTree &t)
{//结点出栈操作
	if(s.top==s.base)
		return;
	else
	{
		s.top--;
		t=*s.top;
	}
}
char GetTop(SqStack1 s)
{//取字符栈的栈顶元素
	if(s.base==s.top)    //栈空
		return -1;
	else
		return *(s.top-1);    //返回栈顶元素的值，栈顶指针不变
}
bool EmptyStack(SqStack1 s)
{//栈的判空操作
	if(s.base==s.top)   //栈空返回true
		return true;
	else
		return false;   //栈非空返回false
}
char Precede(char a,char b)
{//判断符号的优先级
	if(a=='+'||a=='-')
	{
		if(b=='+'||b=='-'||b==')'||b=='=')
			return '>';    //>代表a的优先级高于b
		else
			return '<';
	}
	else if(a=='*'||a=='/')
	{
		if(b=='+'||b=='-'||b=='*'||b=='/'||b==')'||b=='=')
			return '>';
		else
			return '<';
	}
	else if(a=='(')
	{
		if(b==')')
			return '=';
		else
			return '<';
	}
	else if(a==')')
			return '>';
	else
	{
		if(b=='=')
			return '=';
		else
			return '<';
	}
}
double Operate(double a,char ch,double b)
{//运算操作，返回相应的数值结果
	if(ch=='+')
		return a+b;
	else if(ch=='-')
		return a-b;
	else if(ch=='*')
		return a*b;
	else
		return a/b;
}
bool IsCharacter(char ch)
{//判断ch是否为+、-、*、/、(、)、= 这类的字符，是则返回true
	if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='=')
		return true;
	else
		return false;
}
double InOrder(BiTree T) {
    if (T != nullptr) {
        if (T->ischaracter) {
            double ans1 = InOrder(T->lchild);
            double ans2 = InOrder(T->rchild);
            return Operate(ans1, T->data, ans2);
        } else {
            return T->data;
        }
    }
    return 0.0;  
}

void CreateBT(char ch[],BiTree &t,SqStack1 optr,SqStack2 expt)
{//创建二叉树

    int i=0;
    char opr,c[2];  //辅助数组c
    BiTree t1,t2;
    double num;
    while(ch[i]!='\0'||!EmptyStack(optr))
    {
        if(!IsCharacter(ch[i]))     //当前遍历的不是运算符元素
        {
            c[0]=ch[i];
            c[1]='\0';
            BiTree q=new BiTNode;     //生成一个新结点*q
            num=strtod(c,NULL);      //将字符数组c转换成浮点数，赋给num
            q->ischaracter=false;   //结点*q不为运算符
            q->data=num;            //结点数据域置为num
            q->lchild=NULL;         //左右孩子置为NULL
            q->rchild=NULL;
            Push2(expt,q);       //将结点q压入数字栈
            i++;                  //指针i加1
        }//if
        else                 //当前遍历的是运算符元素
        {
            switch(Precede(GetTop(optr),ch[i]))    //比较栈顶元素和当前遍历字符的优先级
            {
                case '<':                //栈顶元素优先级小于当前运算符
                    Push1(optr,ch[i]);     //将当前运算符入栈
                    i++;                  //指针i加1
                    break;
                case '>':              //栈顶元素优先级大于当前运算符
                    Pop1(optr,opr);     //运算符栈的元素出栈
                    Pop2(expt,t2);      //数字栈的栈顶元素出栈
                    Pop2(expt,t1);
                    t=new BiTNode;      //生成新结点*t
                    t->ischaracter=true;     //结点*t为运算符
                    t->data=opr;          //结点数据域置为opr
                    t->lchild=t1;        //左孩子指向t1
                    t->rchild=t2;        //右孩子指向t2
                    Push2(expt,t);       //将结点t压入数字栈
                    break;
                case '=':         //栈顶元素优先级等于当前运算符
                    Pop1(optr,opr);    //运算符栈的元素出栈
                    i++;                //指针i加1
                    break;
            }//switch
        }//else
    }//while
}
int main()
{
	char ch[MAXSIZE];
	while(cin>>ch)
	{
		if(ch[0]=='=') break;
		BiTree t;
		SqStack1 optr;      //运算符栈optr
		SqStack2 expt;        //数字栈expt
		InitStack1(optr);     //初始化栈
		InitStack2(expt);     //初始化栈
		Push1(optr,'=');    //先在运算符栈底放入一个'='
		CreateBT(ch,t,optr,expt);       //创建二叉树
		double answer=InOrder(t);
		cout<<answer<<endl;
	}
	return 0;
}

二叉树的WPL计算

#include<iostream>
using namespace std;
typedef struct BiTNode
{
	int weight;
	struct BiTNode *left,*right;
}BiTNode,*BiTree;
void CreateBiTree(BiTree &T)
{//先序建立二叉树
	int x;
	cin>>x;
	if(x==0) T=NULL;
	else
    {
		T=new BiTNode;
		T->weight=x;
		CreateBiTree(T->left);
		CreateBiTree(T->right);
	}
}
int WPL(BiTree T, int d) {
    if (T == nullptr) {
        return 0;
    } else if (T->left == 0 && T->right ==0) {
        return T->weight * d;
    } else {
        int wplLeft = WPL(T->left, d + 1);
        int wplRight = WPL(T->right, d + 1);
        return wplLeft + wplRight;
    }
}
int main()
{
	while(1)
    {
		BiTree T;
		CreateBiTree(T);
		if(!T) break;
		int d=0;          //调用时T指向二叉树的根结点，d为0
		cout<<WPL(T,d)<<endl;
	}
	return 0;
}

天工造物局

北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台

更多推荐

LMCache CLI 实战：用 `lmcache kvcache clear` 管理运行中服务的 KV Cache 状态

本文是一份针对 LMCache 官方 CLI 命令 `lmcache kvcache` 的完整技术指南。该命令用于在**运行中的 LMCache 服务（MP HTTP server）**上管理 KV cache 状态，当前提供 `clear` 子命令，用于清空 L1（CPU 内存）层中缓存的全部 KV 数据。读完本文，你将掌握该命令的完整参数体系、退出码语义、终端/JSON/静默三种输出模式，并能

天工造物局

Plate 编辑器降级契约（Degradation Contract）：为虚拟化与 Shell 模式划定原生行为底线

本文围绕 Plate 仓库 `.agents/skills/performance/rules/degradation-contract.md` 中的核心规则展开，说明在编辑器引入虚拟化渲染、Shell 岛屿（shell islands）、模型驱动选择（model-backed selection）或分阶段挂载（staged mounting）等激进性能手段时，如何为每一种降级模式登记完整的行为契

天工造物局

Dozzle 在 Kubernetes 中的部署与配置：实时查看 Pod 日志的完整指南

Dozzle 是一个面向容器的实时日志查看器，原生支持 Docker、Swarm 与 Kubernetes 三种运行环境。本文围绕官方 Kubernetes 支持文档展开，讲解如何通过 `DOZZLE_MODE=k8s` 在集群内以最小权限 RBAC 部署 Dozzle、如何安装并依赖 Kubernetes Metrics API 展示资源用量，以及如何用 `DOZZLE_NAMESPACE` 与