搜索到
40
篇与
的结果
-
二叉树其他运算的实现 二叉树其他运算的实现#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; }
-
-
二叉树的顺序存储 二叉树的顺序存储1.完全二叉树的顺序存储#define MAX_SIZE 100 typedef char dataType; // 二叉树结点值类型 // 7.3.1.1 完全二叉树的顺序存储 dataType tree[MAX_SIZE]; int n; // 完全二叉树中实际所含结点个数 2.一般二叉树的顺序存储#define MAX_SIZE 100 typedef char dataType; // 结点值的类型 // 7.3.1.2 一般二叉树的顺序存储 typedef struct node { dataType data; // 结点数据域 int lChild, rChild; // 左、右孩子坐标 int parent; //有时为了方便的找到双亲结点 }treeNode; typedef struct binaryTree { treeNode tree[MAX_SIZE]; int n; // 结点个数 int root; // 根结点坐标 }tree;
