搜索到
57
篇与
的结果
-
树形结构的其他运算 树形结构的其他运算#include <stdio.h> #include <stdlib.h> // 7.8 习题7 typedef char dataType; typedef struct treeNode { dataType data; // 数据域 struct treeNode *lChild,*rChild; // 左、右孩子指针域 }node,*binaryTree; // 顺序栈 #define MAX_SIZE 100 typedef struct stack { node *data[MAX_SIZE]; // 栈中存放的是二叉树结点指针 int top; // 栈顶指针 }seqStack; // 1.初始化栈 void init(seqStack *stack) { stack->top = 0; } // 2. 判断栈是否为空 int empty(seqStack stack) { return stack.top == 0; } // 3. 元素入栈 void push(seqStack *stack, node* n) { if(stack->top == MAX_SIZE-1) { printf("栈已满，无法入栈！\n"); exit(1); } stack->data[stack->top++] = n; } // 4. 读取栈顶元素 node *get(seqStack stack) { return stack.data[stack.top-1]; } // 5. 元素出栈 node* pop(seqStack *stack) { if(empty(*stack)) { printf("栈已空，无法出栈！\n"); exit(1); } return stack->data[--stack->top]; } // 6. 按照前序遍历的顺序创建一个二叉树 binaryTree createTree() { binaryTree tree; char c; if((c = getchar()) == '#') tree = NULL; else { tree = (node *) malloc(sizeof(node)); tree->data = c; tree->lChild = createTree(); tree->rChild = createTree(); } return tree; } // 7.1.13.1 递归方法求二叉树的叶子结点个数 int numLeaf(binaryTree tree) { if(!tree) return 0; // 空树 if(!tree->lChild && !tree->rChild) // 左右孩子都不存在 return 1; return numLeaf(tree->lChild) + numLeaf(tree->rChild); } // 7.1.13.2 非递归方法求二叉树的叶子结点个数 int numLeaf1(binaryTree tree) { int num = 0; seqStack stack; stack.top = 0; // 初始化栈 while (tree || !empty(stack)) // 树或栈非空 { if(tree) { if(!tree->lChild && !tree->rChild) num++; push(&stack,tree); // 进栈 tree = tree->lChild; // 一路向左 } else { tree = pop(&stack); // 出栈向右子树 tree = tree->rChild; } } return num; } // 7.1.14 求给定二叉树中序遍历序列的最后一个结点 node * inOrderLast(binaryTree tree) { while (tree && tree->rChild) tree = tree->rChild; return tree; } // 7.1.15 返回二叉树任意两结点p、q的共同祖先 node *seekAncestor(binaryTree t, node *p, node *q) { seqStack s, s1; // 声明顺序栈 init(&s), init(&s1); // 初始化栈 node *r = NULL; // 记录最近访问的结点 while (t || !empty(s)) // 树或栈非空 { if (t) // 一路向左直到左孩子为空 { push(&s,t); // 沿着根的左孩子依次入栈 t = t->lChild; } else { t = get(s); // 读取栈顶元素 if(t->rChild && t->rChild != r) // 右孩子存在且未访问 t = t->rChild; // 转向右孩子 else { pop(&s); // 出栈 if(t == p || t == q) { if(empty(s1)) // 栈s复制给栈s1 for (int i = s.top-1; i >= 0; i--) push(&s1,s.data[i]); else break; // p、q的祖先都已找到，退出循环 } r = t; // 记录最近访问的结点(关键步骤) t = NULL; // 结点访问后重置为空(关键步骤) } } } while (!empty(s)) // 寻找共同祖先 { t = pop(&s); for (int j = s1.top-1; j >= 0; j--) if(t == s1.data[j]) return t; } return NULL; } int main() { binaryTree tree; printf("请输入结点，创建一颗二叉树，#表示空结点:\n"); tree = createTree(); // ABD#E##FG###C## printf("该二叉树叶子结点有%d个\n",numLeaf(tree)); printf("该二叉树叶子结点有%d个\n", numLeaf1(tree)); node *n = inOrderLast(tree); if(n) printf("该二叉树中序遍历序列的最后一个结点是%c",n->data); else printf("该二叉树为空！"); return 0; } -
中序穿线二叉树的实现 中序穿线二叉树的实现#include <stdio.h> #include <stdlib.h> // 7.6.3 中序穿线二叉树(线索二叉树)的实现 typedef char dataType; // 线索二叉树的结点结构 typedef struct node { dataType data; // 数据域 struct node *lChild, *rChild; // 左、右孩子指针 int lTag, rTag; // 左、右指针是否是线索的标志 }treeNode, *binaryTree; // 1. 按前序遍历顺序建立二叉树 treeNode *createTree() { treeNode *tree; char c; if((c = getchar()) == '#') tree = NULL; else { tree = (treeNode *) malloc(sizeof(treeNode)); tree->data = c; tree->lChild = createTree(); tree->rChild = createTree(); } return tree; } // 2. 对二叉树中序线索化 treeNode *pre = NULL; // 初始化前驱结点指针 void inThread(binaryTree tree) { if(tree) { inThread(tree->lChild); // 左子树线索化 tree->lTag = tree->lChild ? 0:1; tree->rTag = tree->rChild ? 0:1; if(pre) // 对当前结点及前驱结点线索化 { if(tree->lTag) tree->lChild = pre; if(pre->rTag) pre->rChild = tree; } pre = tree; inThread(tree->rChild); // 右子树线索化 } } // 3. 建立中序线索二叉树 void createInThreadTree(binaryTree *tree) { *tree = createTree(); inThread(*tree); } // 4. 寻找中序线索二叉树中p结点的后继结点 treeNode *inNextNode(binaryTree p) { if(p->rTag == 1) return p->rChild; p = p->rChild; while (p->lTag == 0) p = p->lChild; return p; } // 5. 中序线索二叉树的中序遍历 void inOrder(binaryTree tree) { if(tree) { while (tree->lTag == 0) tree = tree->lChild; while (tree) { printf("%c ",tree->data); tree = inNextNode(tree); } } } int main() { binaryTree tree; // 声明二叉树 printf("请输入结点，创建一颗二叉树，#表示空结点:\n"); createInThreadTree(&tree); //建立中序线索二叉树 ABD#E##FG###C## printf("中序线索二叉树的中序遍历\n"); inOrder(tree); return 0; }
-
二叉树其他运算的实现 二叉树其他运算的实现#include <stdio.h> #include <stdlib.h> // 7.5 二叉树其他运算的实现 typedef char dataType; typedef struct node { dataType data; // 数据域 struct node *lChild,*rChild; // 左、右孩子指针域 }treeNode,*binaryTree; // 1. 按照前序遍历的顺序创建一个二叉树 binaryTree createTree() { binaryTree tree; char c; if((c = getchar()) == '#') tree = NULL; else { tree = (treeNode *) malloc(sizeof(treeNode)); tree->data = c; tree->lChild = createTree(); tree->rChild = createTree(); } return tree; } // 2.二叉树的查找 treeNode *locate(binaryTree tree, dataType x) { treeNode *p; if(!tree) return NULL; // 如果是空树 if(tree->data == x) return tree; // 根结点符合条件 p = locate(tree->lChild,x); // 寻找左子树 if(p) return p; return locate(tree->rChild,x); // 寻找右子树 } // 3. 统计二叉树的结点个数 int numOfNode(binaryTree tree) { if(!tree) return 0; return numOfNode(tree->lChild) + numOfNode(tree->rChild) +1; } // 4. 判断两棵二叉树是否相等 int isEqual(binaryTree t1, binaryTree t2) { int t = 0; if(!t1 && !t2) t=1; else { if(t1->data == t2->data) { if(isEqual(t1->lChild,t2->lChild)) { t = isEqual(t1->rChild,t2->rChild); } } } return t; } // 5. 递归方式求二叉树的高度或深度 int depth(binaryTree tree) { int lh,rh; if(!tree) return 0; lh = depth(tree->lChild); rh = depth(tree->rChild); return lh>rh ? lh+1 :rh+1; } int main() { binaryTree tree; // 声明二叉树 printf("请输入结点，创建一颗二叉树，#表示空结点:\n"); tree = createTree(); // ABD#E##FG###C## treeNode *node; char x = 'A'; node = locate(tree,x); if(node) printf("结点%c存在\n",node->data); int num = numOfNode(tree); printf("该二叉树共有%d个结点\n",num); int h = depth(tree); printf("该二叉树高度或深度是%d",h); return 0; }
-
二叉树的递归遍历 二叉树的递归遍历#include <stdio.h> #include <stdlib.h> // 7.4.2 二叉树的递归遍历 typedef char dataType; // 结点值的类型 typedef struct treeNode { dataType data; // 结点数据域 struct treeNode *lChild, *rChild; // 左、右孩子指针 }node, *binaryTree; // 1.按照前序遍历的顺序建立给定的二叉树 binaryTree createTree() { char c; binaryTree t; if((c = getchar()) == '#') t = NULL; else { t = (node *) malloc(sizeof(node)); t->data = c; t->lChild = createTree(); t->rChild = createTree(); } return t; } // 2. 前序遍历 void preOrder(binaryTree t) { if(t) { printf("%c ",t->data); preOrder(t->lChild); preOrder(t->rChild); } } // 3. 中序遍历 void inOrder(binaryTree t) { if(t) { inOrder(t->lChild); printf("%c ",t->data); inOrder(t->rChild); } } // 4. 后序遍历 void postOrder(binaryTree t) { if(t) { postOrder(t->lChild); postOrder(t->rChild); printf("%c ",t->data); } } int main() { binaryTree tree; // 声明二叉树 printf("请输入结点，创建一颗二叉树，#表示空结点:\n"); tree = createTree(); // ABD#E##FG###C## printf("前序遍历\n"); preOrder(tree); printf("\n中序遍历\n"); inOrder(tree); printf("\n后序遍历\n"); postOrder(tree); return 0; }
-
二叉树的非递归遍历 二叉树的非递归遍历#include <stdio.h> #include <stdlib.h> // 7.4.3 二叉树的非递归遍历 typedef char dataType; typedef struct treeNode { dataType data; // 数据域 struct treeNode *lChild,*rChild; // 左、右孩子指针域 }node,*binaryTree; // 顺序栈 #define MAX_SIZE 100 typedef struct stack { node *data[MAX_SIZE]; // 栈中存放的是二叉树结点指针 int top; // 栈顶指针 }seqStack; // 顺序循环队列：用于层序(层次)遍历 typedef struct { node *data[MAX_SIZE]; int front,rear; // 队头、队尾指针 }queue; // 1.栈初始化 void initStack(seqStack *stack) { stack->top = 0; } // 2. 判断栈是否为空 int emptyStack(seqStack stack) { return stack.top == 0; } // 3. 入栈 void push(seqStack *stack, node* n) { if(stack->top == MAX_SIZE-1) { printf("栈已满，无法入栈！\n"); exit(1); } stack->data[stack->top++] = n; } // 4. 读取栈顶元素 node *get(seqStack stack) { return stack.data[stack.top-1]; } // 5. 出栈 node* pop(seqStack *stack) { if(emptyStack(*stack)) { printf("栈已空，无法出栈！\n"); exit(1); } return stack->data[--stack->top]; } // 6.队列初始化 void initQueue(queue *q) { q->front = q->rear = 0; } // 7.判断队列是否为空 int emptyQueue(queue q) { return q.rear == q.front; } // 8.入队 void enQueue(queue *q, node *n) { if((q->rear+1)%MAX_SIZE == q->front) { printf("队列满，无法入队！\n"); exit(1); } q->data[q->rear] = n; q->rear = (q->rear + 1)%MAX_SIZE; } // 9.出队 node *deQueue(queue *q) { if(emptyQueue(*q)) { printf("队列为空，无法出队！\n"); exit(1); } node *n = q->data[q->front]; q->front = (q->front+1)%MAX_SIZE; return n; } // 10. 按照前序遍历的顺序创建一个二叉树 binaryTree createTree() { binaryTree t; char c; if((c = getchar()) == '#') t = NULL; else { t = (node *) malloc(sizeof(node)); t->data = c; t->lChild = createTree(); t->rChild = createTree(); } return t; } // 11. 非递归前序遍历 void preOrder(binaryTree t) { seqStack stack; // 声明顺序栈 stack.top = 0; // 初始化栈 while (t || !emptyStack(stack)) // 树非空或栈非空 { if(t) // 一路向左直到左孩子为空 { printf("%c ",t->data); // 先访问根节点 push(&stack,t); t = t->lChild; // 再访问左孩子 } else { t = pop(&stack); t = t->rChild; // 再访问右孩子 } } } // 12.非递归中序遍历 void inOrder(binaryTree t) { seqStack stack; // 声明顺序栈 stack.top = 0; // 初始化栈 while (t || !emptyStack(stack)) { if(t) // 一路向左直到左孩子为空 { push(&stack,t); t = t->lChild; } else { t = pop(&stack); printf("%c ",t->data); t = t->rChild; } } } // 13.非递归后序遍历 void postOrder(binaryTree t) { seqStack stack; // 声明顺序栈 stack.top = 0; // 初始化栈 node *r = NULL; // 记录最近访问的结点 while (t || !emptyStack(stack)) { if (t) // 一路向左直到左孩子为空 { push(&stack,t); // 沿着根的左孩子依次入栈 t = t->lChild; } else { t = stack.data[stack.top-1]; // 读取栈顶元素 if(t->rChild && t->rChild != r) // 右孩子存在且未访问 t = t->rChild; // 转向右孩子 else { pop(&stack); // 出栈 printf("%c ", t->data); r = t; // 记录最近访问的结点(关键步骤) t = NULL; // 结点访问后重置为空(关键步骤) } } } } // 14. 二叉树层次遍历 seqStack nodeStack; void levelOrder(binaryTree t) { if(!t) { printf("二叉树为空！\n"); return; } queue q; // 声明队列 initQueue(&q); // 初始化队列 enQueue(&q,t); // 根节点入队 initStack(&nodeStack); while (!emptyQueue(q)) // 队列非空 { t = deQueue(&q);; // 出队并访问 push(&nodeStack,t); printf("%c ",t->data); if(t->lChild) // 左孩子入队 enQueue(&q,t->lChild); if(t->rChild) // 右孩子入队 enQueue(&q,t->rChild); } } // 15. 非递归求二叉树层数(深度或高度) int level(binaryTree t) { queue q; // 声明队列 initQueue(&q); // 初始化队列 int level = 0, first = 0; // first指向每层最左侧结点 if(!t) return 0; enQueue(&q,t); // 根结点入队 while (!emptyQueue(q)) // 队列非空 { if(first == q.front) // 当队首结点是某层的第一个结点时 { level++; // 层数累加 first = q.rear; // 更新first指针指向下一层的第一个结点位置 } t = deQueue(&q); // 出队并将孩子结点入队 if(t->lChild) // 左孩子入队 enQueue(&q,t->lChild); if(t->rChild) // 右孩子入队 enQueue(&q,t->rChild); } return level; } // 16.非递归求二叉树最大宽度 int width(binaryTree t) { queue q; // 声明循环队列 initQueue(&q); // 初始化队列 int i = 1, width = 0, first = 0; // i初值为1，处理只有一个结点的树 if(!t) return 0; // 树为空时 enQueue(&q,t); // 根节点入队 while (!emptyQueue(q)) // 队列非空时 { if(first == q.front) // 当first指向每层第一个节点时 { if(i > width) width = i; // 更新最大宽度 first = q.rear; // 更新first指针 i = 0; // 重置i，以计算该层宽度 } t = deQueue(&q); // 元素出队 i++; // 计算该层宽度 if(t->lChild) enQueue(&q,t->lChild); // 左孩子入队 if(t->rChild) enQueue(&q,t->rChild); // 右孩子入队 } return width; } // 17.返回二叉树任意两结点p、q的共同祖先 node *seekAncestor(binaryTree t, node *p, node *q) { seqStack s, s1; // 声明顺序栈 initStack(&s), initStack(&s1); // 初始化栈 node *r = NULL; // 记录最近访问的结点 while (t || !emptyStack(s)) { if (t) // 一路向左直到左孩子为空 { push(&s,t); // 沿着根的左孩子依次入栈 t = t->lChild; } else { t = get(s); // 读取栈顶元素 if (t->rChild && t->rChild != r) // 右孩子存在且未访问 t = t->rChild; // 转向右孩子 else { pop(&s); // 出栈 if (t == p || t == q) { if (emptyStack(s1)) for (int i = s.top - 1; i >= 0; i--) push(&s1, s.data[i]); else break; } r = t; // 记录最近访问的结点(关键步骤) t = NULL; // 结点访问后重置为空(关键步骤) } } } while (!emptyStack(s)) { t = pop(&s); for (int j = s1.top-1; j >= 0; j--) if(t == s1.data[j]) return t; } return NULL; } int main() { binaryTree t; // 声明二叉树 printf("请输入结点，创建一颗二叉树，#表示空结点:\n"); t = createTree(); // ABD#E##FG###C## printf("前序遍历\n"); preOrder(t); printf("\n中序遍历\n"); inOrder(t); printf("\n后序遍历\n"); postOrder(t); printf("\n层序遍历\n"); levelOrder(t); printf("\n树的高度为%d", level(t)); node *p = nodeStack.data[2], *q = nodeStack.data[6], *n; n = seekAncestor(t,p,q); if(n) printf("\n结点%c和结点%c的共同祖先是%c",p->data,q->data,n->data); else printf("\n结点%c和结点%c没有共同祖先",p->data,q->data); printf("\n该二叉树的宽度为%d", width(t)); return 0; }
