口碑好的郑州网站建设,怎么做多个域名指向一个网站,自助网站建设,杭州网络公司建网站目录 8.假设二叉树采用二叉链表存储结构存储#xff0c;试设计一个算法#xff0c;计算一棵给定二叉树的所有双分支结点个数。 9.设树B是一棵采用链式结构存储的二叉树#xff0c;编写一个把树 B中所有结点的左、右子树进行交换的函数。 10.假设二叉树采用二叉链存储结构存储…目录 8.假设二叉树采用二叉链表存储结构存储试设计一个算法计算一棵给定二叉树的所有双分支结点个数。 9.设树B是一棵采用链式结构存储的二叉树编写一个把树 B中所有结点的左、右子树进行交换的函数。 10.假设二叉树采用二叉链存储结构存储设计一个算法求先序遍历序列中第 k(1k二叉树中结点个数)个结点的值 11.已知二叉树以二叉链表存储编写算法完成: 对于树中每个元素值为X 的结点删去以它为根的子树并释放相应的空间。 12.在二叉树中查找值为 x 的结点试编写算法(用 C语言)打印值为x的结点的所有祖先假设值为X的结点不多于一个。 8.假设二叉树采用二叉链表存储结构存储试设计一个算法计算一棵给定二叉树的所有双分支结点个数。 本题代码如下
int twonode(tree t)
{if (t NULL)//若为空树return 0;else if (t-lchild t-rchild)//双分支结点return twonode(t-lchild) twonode(t-rchild) 1;else//单分支或叶子节点return twonode(t-lchild) twonode(t-rchild);
}
完整测试代码
#includestdio.h
#includestdlib.h
#define true 1
#define false 0
typedef struct treenode
{char data;struct treenode* lchild, * rchild;
}treenode,*tree;
void buildtree(tree* t)
{char ch;ch getchar();if (ch #)*tNULL;else{*t (treenode*)malloc(sizeof(treenode));(*t)-data ch;buildtree(((*t)-lchild));buildtree(((*t)-rchild));}
}
int twonode(tree t)
{if (t NULL)//若为空树return 0;else if (t-lchild t-rchild)//双分支结点return twonode(t-lchild) twonode(t-rchild) 1;else//单分支或叶子节点return twonode(t-lchild) twonode(t-rchild);
}
int main()
{tree t;buildtree(t);printf(双支数为%d\n,twonode(t));return 0;
}
用ABD##E##CF##G##这个测试 9.设树B是一棵采用链式结构存储的二叉树编写一个把树 B中所有结点的左、右子树进行交换的函数。 本题代码如下
void swap(tree* t)
{if (*t){treenode* temp (*t)-lchild;(*t)-lchild (*t)-rchild;(*t)-rchild temp;swap((*t)-lchild);swap((*t)-rchild);}
}
完整测试代码
#includestdio.h
#includestdlib.h
typedef struct treenode
{char data;struct treenode* lchild, * rchild;
}treenode,*tree;
void buildtree(tree* t)
{char ch;ch getchar();if (ch #)*t NULL;else{*t (treenode*)malloc(sizeof(treenode));(*t)-data ch;buildtree(((*t)-lchild));buildtree(((*t)-rchild));}
}
void swap(tree* t)
{if (*t){treenode* temp (*t)-lchild;(*t)-lchild (*t)-rchild;(*t)-rchild temp;swap((*t)-lchild);swap((*t)-rchild);}
}
void disp(tree* t)
{if (*t){printf(%c, (*t)-data);disp((*t)-lchild);disp((*t)-rchild);}
}
int main()
{tree t;buildtree(t);printf(交换过后的二叉树为前序序列);swap(t);disp(t);return 0;
}
用ABD##E##CF##G##测试 10.假设二叉树采用二叉链存储结构存储设计一个算法求先序遍历序列中第 k(1k二叉树中结点个数)个结点的值 本题代码如下
// 查找第k个节点值的函数
char serchk(tree* t, int k)
{if (*t NULL) // 如果节点为空返回*表示未找到return *;if (i k) // 如果当前节点是第k个节点返回节点数据return (*t)-data;i; // 更新当前节点位置char s serchk((*t)-lchild, k); // 递归查找左子树中的第k个节点if (s ! *) // 如果左子树中找到直接返回结果return s;s serchk((*t)-rchild, k); // 否则递归查找右子树中的第k个节点return s; // 返回查找结果
}
完整测试代码
#includestdio.h// 定义二叉树节点结构体
typedef struct treenode
{char data; // 节点存储的数据struct treenode* lchild, * rchild; // 左右子节点指针
}treenode,*tree;// 构建二叉树函数
void buildtree(tree* t)
{char ch;ch getchar(); // 从输入中读取一个字符if (ch #) // 如果字符为#表示空节点*t NULL;else{*t (treenode*)malloc(sizeof(treenode)); // 分配内存空间给新节点(*t)-data ch; // 将读取到的字符赋值给节点数据(*t)-lchild NULL; // 初始化左子节点为空(*t)-rchild NULL; // 初始化右子节点为空buildtree((*t)-lchild); // 递归构建左子树buildtree((*t)-rchild); // 递归构建右子树}
}int i 1; // 全局变量用于记录当前遍历的节点位置// 查找第k个节点值的函数
char serchk(tree* t, int k)
{if (*t NULL) // 如果节点为空返回*表示未找到return *;if (i k) // 如果当前节点是第k个节点返回节点数据return (*t)-data;i; // 更新当前节点位置char s serchk((*t)-lchild, k); // 递归查找左子树中的第k个节点if (s ! *) // 如果左子树中找到直接返回结果return s;s serchk((*t)-rchild, k); // 否则递归查找右子树中的第k个节点return s; // 返回查找结果
}int main()
{tree t; // 定义二叉树变量tbuildtree(t); // 构建二叉树char fserchk(t, 5); // 查找第5个节点的值printf(%c, f); // 输出查找结果return 0;
}用ABD##E##CF##G##测试 11.已知二叉树以二叉链表存储编写算法完成: 对于树中每个元素值为X 的结点删去以它为根的子树并释放相应的空间。 可以直接使用前序遍历访问到值为x的结点就递归的删除它的左、右子树。
本题代码如下
void release(tree* t)//递归释放结点
{if (!*t)return;release((*t)-lchild);release((*t)-rchild);free(*t);
}
void deletex(tree* t,char x)
{if (*t NULL)return;if((*t)-datax){release(t);*t NULL;}if (*t ! NULL)//前序遍历的去找{deletex((*t)-lchild, x);deletex((*t)-rchild, x);}
}
完整测试代码
#includestdio.h
#includestdlib.h
typedef struct treenode
{char data;struct treenode* lchild, * rchild;
}treenode,*tree;
void buildtree(tree* t)
{char ch;ch getchar();if (ch #)*t NULL;else{*t (treenode*)malloc(sizeof(treenode));(*t)-data ch;buildtree((*t)-lchild);buildtree((*t)-rchild);}
}
void release(tree* t)
{if (!*t)return;release((*t)-lchild);release((*t)-rchild);free(*t);
}
void deletex(tree* t,char x)
{if (*t NULL)return;if((*t)-datax){release(t);*t NULL;}if (*t ! NULL){deletex((*t)-lchild, x);deletex((*t)-rchild, x);}
}
void disp(tree* t)
{if (*t){printf(%c, (*t)-data);disp((*t)-lchild);disp((*t)-rchild);}
}
int main()
{tree t;buildtree(t);deletex(t, C);disp(t);return 0;
}
用ABD##E##CF##G##测试 /* A B C D E F G */ 12.在二叉树中查找值为 x 的结点试编写算法(用 C语言)打印值为x的结点的所有祖先假设值为X的结点不多于一个。 采用非递归后序遍历最后访问根结点访问到值为 x 的结点时栈中所有元素均为该结点的祖先依次出栈打印.
本题代码如下注释详解
// 寻找指定字符的所有祖先结点
void ancestor(tree* t, char x)
{stack s[10]; // 定义一个大小为10的栈用于存储二叉树的结点指针和标记位 int top -1; // 初始化栈顶为-1表示栈为空 while (*t ! NULL || top ! -1) // 当当前节点非空或者栈非空时继续循环 {while (*t ! NULL) // 当当前结点非空时将其入栈并向左子树遍历 {top;s[top].t *t; // 将当前结点入栈 s[top].tag 0; // 标记位设为0表示该结点尚未被访问过 *t (*t)-lchild; // 向左子树遍历 }while (top ! -1 s[top].tag 1) // 当栈非空且栈顶元素的标记位为1时出栈即回退 {top--;}if (top ! -1) // 当栈非空时进行以下操作 {if (s[top].t-data x) // 如果栈顶元素的data字段等于指定字符x则输出所有祖先结点 {printf(所有的祖先结点为\n);for (int i 0; i top; i) // 遍历栈中所有元素不包括栈顶元素并输出其data字段 {printf(%c , s[i].t-data);}break; // 找到指定字符的所有祖先结点后跳出循环 }s[top].tag 1; // 如果栈顶元素的data字段不等于指定字符x将其标记位设为1表示该结点已经被访问过 *t s[top].t-rchild; // 向右子树遍历 }}
}
完整测试代码
#includestdio.h
#includestdlib.h
// 定义一个二叉树结点
typedef struct treenode
{char data; //结点存储的数据 struct treenode* lchild, * rchild; // 结点的左右孩子
} treenode, * tree;
// 定义一个栈结构
typedef struct
{treenode* t; // 栈中存储的是二叉树的结点指针 int tag; // 标记位主要用于记录结点是否已经被访问过
} stack;
// 建立二叉树
void buildtree(tree* t)
{char ch;ch getchar(); // 从标准输入获取一个字符 if (ch #) // 如果输入的是#则该节点为空 *t NULL;else{*t (treenode*)malloc(sizeof(treenode)); // 为新的结点分配内存空间 (*t)-data ch; // 将输入的字符赋值给节点的data字段 (*t)-lchild NULL; // 初始化结点的左右孩子为空 (*t)-rchild NULL;buildtree((*t)-lchild); // 递归建立左子树 buildtree((*t)-rchild); // 递归建立右子树 }
}
// 寻找指定字符的所有祖先结点
void ancestor(tree* t, char x)
{stack s[10]; // 定义一个大小为10的栈用于存储二叉树的结点指针和标记位 int top -1; // 初始化栈顶为-1表示栈为空 while (*t ! NULL || top ! -1) // 当当前节点非空或者栈非空时继续循环 {while (*t ! NULL) // 当当前结点非空时将其入栈并向左子树遍历 {top;s[top].t *t; // 将当前结点入栈 s[top].tag 0; // 标记位设为0表示该结点尚未被访问过 *t (*t)-lchild; // 向左子树遍历 }while (top ! -1 s[top].tag 1) // 当栈非空且栈顶元素的标记位为1时出栈即回退 {top--;}if (top ! -1) // 当栈非空时进行以下操作 {if (s[top].t-data x) // 如果栈顶元素的data字段等于指定字符x则输出所有祖先结点 {printf(所有的祖先结点为\n);for (int i 0; i top; i) // 遍历栈中所有元素不包括栈顶元素并输出其data字段 {printf(%c , s[i].t-data);}break; // 找到指定字符的所有祖先结点后跳出循环 }s[top].tag 1; // 如果栈顶元素的data字段不等于指定字符x将其标记位设为1表示该结点已经被访问过 *t s[top].t-rchild; // 向右子树遍历 }}
}
int main()
{tree t; // 定义一个二叉树节点指针t buildtree(t); // 建立二叉树 ancestor(t, D); // 找出字符D的所有祖先结点并输出 return 0;
}
用ABD##E##CF##G##测试
/* A B C
D E F G */
