不得不说c语言是真的麻烦 尤其是一个结构体里面再套一个结构体指针，这种指针的初始化稍不留神忘记了初始化，就可能导致程序的崩溃，另外c语言的判空操作 加！的话 是为null的情况 这一点跟java一点也不像,所以建议在写程序判空的时候 能带上是否为null就带上 一方面是防止自己出错,另一方面也大大增加了程序的可读性。
另外令人最反感的是 随着你程序的不断扩大 代码量越来越多 你在查错的时候 本来指针的语法问题已经让自己够不耐烦了,再不断的上翻和下翻找你的方法体会让你愈加烦躁。有时候真的想把电脑…啊啊啊
不过值得庆幸的是 在经历了一下午的调错之后 我成功的把程序的错误全部解决了 并实现了我想要的功能。我不得不感叹，c语言真的…不方便 在java的世界里 我直接new一个队列 双端的 能保证有序的什么的 管你啥时候被销毁 管你的地址在哪 我都不需关注 直接用就行了 唉 想念java的语法 但是又不得不面对c语言。就这吧。
代码如下：
#include#include #include #define maxSize 10 using namespace std; typedef struct Node{ int data; struct Node *left; struct Node *right; }Node, *TreeNode; typedef struct queue{ TreeNode *data; int rear;//尾指针 int front;//头指针 }queue,*Queue; typedef struct stack{ TreeNode *data; int top; }stack,*Stack; void initTree(TreeNode &root); void createTree(TreeNode &root); TreeNode createTree2(TreeNode T);//递归创建二叉树 暂时不会用 void preOrder(TreeNode root); void preOrder2(Stack &s, TreeNode t); int getHeigh(TreeNode root); void inOrder(TreeNode root); void inOrder2(Stack &s, TreeNode root); void postOrder(TreeNode root); void initQueue(Queue &q); bool isFull(Queue q); bool isEmpty(Queue q); void push(Queue &q, Node *node); Node* pop(Queue &q); void bfs(TreeNode root, Queue &q); void leftCounts(TreeNode root, Queue &q, int &count); int recurLeftCounts(TreeNode node); int nodeCounts(TreeNode node); void initStack(Stack &s); bool stackIsEmpty(Stack s); void add(Stack &stack, Node *node); Node* remove(Stack &stack); int main(){ TreeNode root; createTree(root);//创建树 cout << "先序遍历："; preOrder(root);//先序遍历 cout << "n树的高度为：" << getHeigh(root); Queue queue; cout << "n层序遍历："; bfs(root,queue); //非递归实现计算叶子节点数 // int count; // leftCounts(root,queue,count); // cout << "n叶子结点的个数：" << count; //递归实现计算叶子节点数 int nums = recurLeftCounts(root); cout << "n叶子结点的个数：" << nums; //结点的总数 int nodeCount = nodeCounts(root); cout << "n结点的总数：" << nodeCount; //初始化一个栈 Stack stack; //非递归实现先序遍历 cout << "n非递归的先序遍历为："; preOrder2(stack,root); //非递归实现中序遍历 cout << "n非递归的中序遍历为："; inOrder2(stack,root); return 0; } //入栈操作 void add(Stack &stack, Node *node){ if(stack->top == maxSize - 1){ cout << "栈已满,入栈失败..."; return; } stack->data[++stack->top] = node; } //出栈操作 Node* remove(Stack &stack){ if(stackIsEmpty(stack)){ cout << "栈为空,出栈失败..."; } // Node *tmp = stack->data[stack->top]; // stack->top--; // return tmp; return stack->data[stack->top--]; } //判断栈是否为空 bool stackIsEmpty(Stack s){ return s->top == -1; } //判断队列是否为空 bool isEmpty(Queue q){ return q->rear == q->front; } //判断队列是否已满 bool isFull(Queue q){ return (q->rear + 1) % maxSize == q->front; } //入队 void push(Queue &q, Node *node){ if(isFull(q)){ cout << "n队列已满,加入失败..."; return; } q->data[q->rear] = node; q->rear = (q->rear + 1) % maxSize; } //出队 Node* pop(Queue &q){ if(isEmpty(q)){ cout << "n队列为空,出队失败..."; return NULL; } Node *node = q->data[q->front]; q->front = (q->front + 1) % maxSize; return node; } //计算结点的个数 递归 int nodeCounts(TreeNode node){ return !node ? 0 : nodeCounts(node->left) + nodeCounts(node->right) + 1; } //计算叶子结点数 非递归 void leftCounts(TreeNode root, Queue &q, int &count){ if(root) push(q,root); while(!isEmpty(q)){ Node *node = pop(q); if(!node->left && !node->right) { count++; cout << "n叶子结点:" << node->data; } if(node->left) push(q,node->left); if(node->right) push(q,node->right); } } //计算叶子结点数目 递归实现 int recurLeftCounts(TreeNode node){ if(!node) return 0; if(!node->left && !node->right) return 1; return recurLeftCounts(node->left) + recurLeftCounts(node->right); } //层次遍历 void bfs(TreeNode root, Queue &q){ initQueue(q);//初始化队列 if(root) push(q,root); while(!isEmpty(q)){ Node *node = pop(q); cout << node->data << " "; if(node->left) push(q,node->left); if(node->right) push(q,node->right); } } //计算深度 int getHeigh(TreeNode root){ return !root ? 0 : max(getHeigh(root->left) ,getHeigh(root->right)) + 1; } //递归创建二叉树 TreeNode createTree2(TreeNode T){ char ch; T=(TreeNode)malloc(sizeof(Node)); scanf("%c",&ch); if(ch == '#') return 0; T->data=ch; T->left=createTree2(T->left); T->right=createTree2(T->right); return T; } //非递归实现先序遍历 void preOrder2(Stack &s, TreeNode t){ TreeNode p = t; initStack(s); while(p || !stackIsEmpty(s)){ if(p){ cout << p->data << " "; add(s,p); p = p->left; } else{ p = remove(s); p = p->right; } } } //先序遍历 void preOrder(TreeNode root){ if(!root) return; cout << root->data << " "; preOrder(root->left); preOrder(root->right); } //非递归实现中序遍历 void inOrder2(Stack &s, TreeNode root){ TreeNode p = root; initStack(s); while(p || !stackIsEmpty(s)){ if(p){ add(s,p); p = p->left; } else{ p = remove(s); cout << p->data << " "; p = p->right; } } } //中序遍历 void inOrder(TreeNode root){ if(!root) return; inOrder(root->left); cout << root->data << " "; inOrder(root->right); } //后序遍历 void postOrder(TreeNode root){ if(!root) return; postOrder(root->left); postOrder(root->right); cout << root->data << " "; } //创建二叉树 void createTree(TreeNode &root){ initTree(root);//初始化树 Node *node1 = (Node*)malloc(sizeof(Node)); Node *node2 = (Node*)malloc(sizeof(Node)); Node *node3 = (Node*)malloc(sizeof(Node)); Node *node4 = (Node*)malloc(sizeof(Node)); Node *node5 = (Node*)malloc(sizeof(Node)); Node *node6 = (Node*)malloc(sizeof(Node)); node1->data = 1; node2->data = 2; node3->data = 3; node4->data = 4; node5->data = 5; node6->data = 6; root->left = node1; root->right = node2; node2->left = NULL; node2->right = NULL; node1->left = node3; node1->right = node4; node4->left = NULL; node4->right = NULL; node3->left = node5; node3->right = NULL; node5->right = node6; node5->left = NULL; node6->left = NULL; node6->right = NULL; } //初始化栈 void initStack(Stack &s){ s = (Stack)malloc(sizeof(stack)); s->top = -1; s->data = (TreeNode*)malloc(sizeof(Node) * maxSize); } //初始化队列 void initQueue(Queue &q){ q = (Queue)malloc(sizeof(queue));//初始化头指针 q->rear = 0;//指向队尾元素的下一个位置 q->front = 0; q->data = (Node**)malloc(sizeof(Node) * maxSize); //Node** 还可以写成 TreeNode * 二级指针！！！; } //初始化树 void initTree(TreeNode &root){ root = (TreeNode)malloc(sizeof(Node)); root->left = NULL; root->right = NULL; root->data = 99; }
运行结果截图如下：
另外我今天又改进了我的程序 就是使用c++库里面写好的一些数据结构,也就是集合 来实现我的功能,这将为我去实现某些功能提供极大的便利之处.第一次接触c语言的集合.哈哈,除了方法比较少外,但是至少可以实现我想要的功能.这是非常赞的地方. 以下是我用队列去实现树的广度优先遍历.
代码如下：
#include#include #include using namespace std; typedef struct Node{ int data; struct Node *left; struct Node *right; }Node, *TreeNode; void createTree(TreeNode &root); void initTree(TreeNode &root); int main(){ TreeNode root; createTree(root);//创建树 queue q; if(root) q.push(root); TreeNode node; while(!q.empty()){ node = q.front(); cout << node->data << " "; q.pop(); if(node->left) q.push(node->left); if(node->right) q.push(node->right); } } //创建二叉树 void createTree(TreeNode &root){ initTree(root);//初始化树 Node *node1 = (Node*)malloc(sizeof(Node)); Node *node2 = (Node*)malloc(sizeof(Node)); Node *node3 = (Node*)malloc(sizeof(Node)); Node *node4 = (Node*)malloc(sizeof(Node)); Node *node5 = (Node*)malloc(sizeof(Node)); Node *node6 = (Node*)malloc(sizeof(Node)); node1->data = 1; node2->data = 2; node3->data = 3; node4->data = 4; node5->data = 5; node6->data = 6; root->left = node1; root->right = node2; node2->left = NULL; node2->right = NULL; node1->left = node3; node1->right = node4; node4->left = NULL; node4->right = NULL; node3->left = node5; node3->right = NULL; node5->right = node6; node5->left = NULL; node6->left = NULL; node6->right = NULL; } //初始化树 void initTree(TreeNode &root){ root = (TreeNode)malloc(sizeof(Node)); root->left = NULL; root->right = NULL; root->data = 99; }
运行结果如下：
