普通二叉树的遍历
前序遍历:根 左子树 右子树
中序遍历:左子树 根 右子树
后序遍历:左子树 右子树 根
一颗普通二叉树的实现
#include<stdlib.h>
//树的定义
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;//手搓一棵树 malloc
BTNode* BuyNode(int x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail");return;}node->data = x;node->left = node->right = NULL;
}BTNode* CreatBinaryTree()
{BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);BTNode* node6 = BuyNode(6);//怎么指向根据树写出来node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;return node1;
}
int main()
{BTNode* root = CreatBinaryTree();return 0;
}前序遍历代码
//前序遍历
void PrevOrder(BTNode*root)
{if (root == NULL)//可能一上来就是空树,也可能走到了空的位置{printf("N");return;//回到上一次调用}//根 左子树 右子树printf("%d", root->data);PrevOrder(root->left);PrevOrder(root->right);}
中序遍历
//中序遍历
void InOrder(BTNode* root)
{if (root == NULL)//可能一上来就是空树,也可能走到了空的位置{printf("N");return;//回到上一次调用}//左子树 根 右子树InOrder(root->left);printf("%d", root->data);PrevOrder(root->right);}
后序遍历逻辑是相同的,不做代码展示了
求树的节点个数
三种写法 1.需要全局变量 2.无需全局变量(需要指针) 3.直接用三目运算符
1.
//求树的节点个数
int size = 0;//全局变量
int TreeSize(BTNode* root)
{if (root == NULL) return 0;else ++size;TreeSize(root->left);TreeSize(root->right);return size;
}
int TreeSize(BTNode* root, int* psize)
{if (root == NULL) return 0;else ++psize;TreeSize(root->left,psize);TreeSize(root->right,psize);
}
3.三目运算符
//三目操作符
/*
1.空:0 2.不为空:左子树+右子树+1
*/
int TreeSize(BTNode* root)
{return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}求叶子节点个数
//求叶子节点个数
int TreeLeafSize(BTNode* root)
{if (root->left == root->right == NULL)return 1;return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}
求高度
//求高度
//空:0 不为空:左子树右子树谁高,就谁+1
int TreeHeight(BTNode* root)
{if (root == NULL)return 0;return TreeHeight(root->left) > TreeHeight(root->right) ? TreeHeight(root->left) + 1: TreeHeight(root->right) + 1;
}//但是这段代码通过不了LeetCode的OJ,遇到很长的树,重复计算太多次了,没有值进行记录这段代码不好,需要优化
优化后
int TreeHeight(BTNode* root)
{if (root == NULL)return 0;int leftheight = TreeHeight(root->left);int rightheight = TreeHeight(root->right);//记录一下,不用重复的返回计算//依然是谁大就谁+1return TreeHeight(root->left) > TreeHeight(root->right) ? +leftheight+1: rightheight + 1;
}
965.单值二叉树
//遍历来解决#include<stdio.h>struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;};#include<stdbool.h>bool isUnivalTree(struct TreeNode* root){if (root == NULL)return true;if (root->left && root->left->val != root->val)return false;if (root->right && root->right->val != root->val)return false;return isUnivalTree(root->left) && isUnivalTree(root->right);
}
这是利用的遍历的思路
还有一种思路:遍历并于固定的值比较
bool fun(struct TreeNode*root,int val)
{}bool isUnivalTree(struct TreeNode* root){bool fun(root,root->val)
}
下篇博客会讲解第二种做法和求第K层的节点个数
