网站建设 笔记,筑建网站首页,网站模板中心,注册新加坡公司一、二叉树的遍历
二叉树遍历是按照某种特定的规则#xff0c;依次对二叉树中的结点进行相应的操作#xff0c;并且每个结点只操作一次。
1.前序遍历#xff08;先根遍历#xff09;
前序遍历#xff08;Preorder Traversal也叫先序遍历#xff09;——根、左子树、右…一、二叉树的遍历
二叉树遍历是按照某种特定的规则依次对二叉树中的结点进行相应的操作并且每个结点只操作一次。
1.前序遍历先根遍历
前序遍历Preorder Traversal也叫先序遍历——根、左子树、右子树。属于DFS深度优先遍历。空用N表示。 // 前序遍历空用N表示
void PrevOrder(BTNode* root)
{if (root NULL){printf(N );return;}printf(%d , root-_data);PrevOrder(root-_left);PrevOrder(root-_right);
}// 前序遍历不打印空
void PrevOrder(BTNode* root)
{if (root){printf(%d , root-_data);PrevOrder(root-_left);PrevOrder(root-_right);}
} 2.中序遍历中根遍历
中序遍历Inorder Traversal——左子树、根、右子树。空用N表示。 // 中序遍历空用N表示
void InOrder(BTNode* root)
{if (root NULL){printf(N );return;}InOrder(root-_left);printf(%d , root-_data);InOrder(root-_right);
}
3.后序遍历后根遍历
后序遍历Postorder Traversal——左子树、右子树、根。空用N表示。 // 后序遍历空用N表示
void PostOrder(BTNode* root)
{if (root NULL){printf(N );return;}PostOrder(root-_left);PostOrder(root-_right); printf(%d , root-_data);
}
4.层序遍历
设二叉树的根结点所在层数为1层序遍历就是从所在二叉树的根结点出发首先访问第一层的树根结点然后从左到右访问第2层上的结点接着是第三层的结点以此类推自上而下自左至右逐层访问树的结点的过程就是层序遍历。层序遍历是非递归遍历。属于BFS广度优先遍历。 需要用到队列的代码可以将之前写的代码拷贝过来源代码-添加-现有项。
// 层序遍历
#includeQueue.h
void TreeLevelOrder(BTNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);printf(%d , front-_data);if (front-_left)QueuePush(q, front-_left);if (front-_right)QueuePush(q, front-_right);}QueueDestroy(q);
}
其中Queue.h文件中要修改
typedef struct BinaryTreeNode* QDataType;//要使用原生类型
二、二叉树结点个数
// 二叉树结点个数错误示范
int TreeSize(BTNode* root)
{static int size 0;//静态if (root NULL)return 0;elsesize;TreeSize(root-_left);TreeSize(root-_right);return size;//打印结果会累加
}
正确写法递归遍历思路
// 二叉树结点个数方法一
int size 0;
int TreeSize(BTNode* root)
{if (root NULL)return 0;elsesize;TreeSize(root-_left);TreeSize(root-_right);return size;
}
int main()
{BTNode* root CreatBinaryTree();size 0;printf(二叉树结点个数%d\n, TreeSize(root));size 0;printf(二叉树结点个数%d\n, TreeSize(root));return 0;
}// 二叉树结点个数方法二
int TreeSize(BTNode* root, int* psize)
{if (root NULL)return 0;else(*psize);TreeSize(root-_left, psize);TreeSize(root-_right, psize);return *psize;//可以不要返回值
}
int main()
{BTNode* root CreatBinaryTree();int size 0;printf(二叉树结点个数%d\n, TreeSize(root, size));size 0;printf(二叉树结点个数%d\n, TreeSize(root, size));return 0;
}
分治分而治之递归思路 // 二叉树结点个数方法三
int TreeSize(BTNode* root)
{return root NULL ? 0 : TreeSize(root-_left) TreeSize(root-_right) 1;
}
int main()
{BTNode* root CreatBinaryTree();printf(TreeSize:%d\n, TreeSize(root));return 0;
}
三、二叉树叶子结点个数
int TreeLeafSize(BTNode* root)
{if (root NULL)return 0;if (root-_left NULL root-_right NULL)//只有一个叶子return 1;return TreeLeafSize(root-_left) TreeLeafSize(root-_right);
}
四、二叉树高度
为空是0不为空就是左子树高度和右子树高度中大的加1。
//方法一
int fmax(int x, int y)
{return x y ? x : y;
}
int TreeHeight(BTNode* root)
{if (root NULL)return 0;return fmax(TreeHeight(root-left), TreeHeight(root-right)) 1;
}
//方法二
int TreeHeight(BTNode* root)
{if (root NULL)return 0;int leftHeight TreeHeight(root-_left);int rightHeight TreeHeight(root-_right);return leftHeight rightHeight ? leftHeight 1 : rightHeight 1;
} LCR 175. 计算二叉树的深度 - 力扣LeetCode下面代码OJ过不了效率问题
//OJ不能通过
int TreeHeight(BTNode* root)
{if (root NULL)return 0;return leftHeight rightHeight ? leftHeight 1 : rightHeight 1;
}
五、二叉树第k层节点个数 int TreeLevelKSize(BTNode* root, int k)
{if (root NULL)return 0;if (k 1)return 1;// 子问题return TreeLevelKSize(root-_left, k - 1) TreeLevelKSize(root-_right, k - 1);
}
六、二叉树查找值为x的节点
若有多个值为x的节点返回第一次找到的节点因为找到值为x的节点就不会再往下找了若左子树找到值为x的节点就不会再找右子树的节点。
BTNode* TreeFind(BTNode* root, BTDataType x)
{if (root NULL)return NULL;if (root-_data x)return root;BTNode* ret1 TreeFind(root-_left, x);if (ret1)return ret1;BTNode* ret2 TreeFind(root-_right, x);if (ret2)return ret2;return NULL;
}
七、二叉树的销毁
如果是空树不需要销毁。
使用后序遍历先销毁左子树在销毁右子树最后释放根结点。
void TreeDestory(BTNode* root)
{if (root NULL)return;TreeDestory(root-_left);TreeDestory(root-_right);free(root);
}
八、判断二叉树是否是完全二叉树
①层序遍历走空也进队列
②遇到第一个空节点时开始判断后面全空就是完全二叉树后面有非空就不是完全二叉树。 bool TreeComplete(BTNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);// 遇到第一个空就可以开始判断如果队列中还有非空就不是完全二叉树if (front NULL){break;}QueuePush(q, front-_left);QueuePush(q, front-_right);}while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);// 如果有非空就不是完全二叉树if (front){QueueDestroy(q);return false;}}QueueDestroy(q);return true;
}
九、二叉树链式结构的实现
#includestdio.h
#includestdlib.h
#includestdbool.h
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType _data;struct BinaryTreeNode* _left;struct BinaryTreeNode* _right;
}BTNode;
BTNode* BuyNode(int x)
{BTNode* node (BTNode*)malloc(sizeof(BTNode));if (node NULL){perror(malloc fail);return NULL;}node-_data x;node-_left NULL;node-_right NULL;return node;
}
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;
}
// 前序遍历空用N表示
void PrevOrder(BTNode* root)
{if (root NULL){printf(N );return;}printf(%d , root-_data);PrevOrder(root-_left);PrevOrder(root-_right);
}
// 中序遍历空用N表示
void InOrder(BTNode* root)
{if (root NULL){printf(N );return;}InOrder(root-_left);printf(%d , root-_data);InOrder(root-_right);
}
// 后序遍历空用N表示
void PostOrder(BTNode* root)
{if (root NULL){printf(N );return;}PostOrder(root-_left);PostOrder(root-_right); printf(%d , root-_data);
}
// 二叉树结点个数
int TreeSize(BTNode* root)
{return root NULL ? 0 : TreeSize(root-_left) TreeSize(root-_right) 1;
}
// 二叉树叶子结点个数
int TreeLeafSize(BTNode* root)
{if (root NULL)return 0;if (root-_left NULL root-_right NULL)//只有一个叶子return 1;return TreeLeafSize(root-_left) TreeLeafSize(root-_right);
}
// 二叉树的高度为空是0不为空就是左子树高度和右子树高度大的加1
int TreeHeight(BTNode* root)
{if (root NULL)return 0;int leftHeight TreeHeight(root-_left);int rightHeight TreeHeight(root-_right);return leftHeight rightHeight ? leftHeight 1 : rightHeight 1;
}
// 二叉树第k层节点个数
int TreeLevelKSize(BTNode* root, int k)
{if (root NULL)return 0;if (k 1)return 1;return TreeLevelKSize(root-_left, k - 1) TreeLevelKSize(root-_right, k - 1);
}
// 二叉树查找值为x的节点
BTNode* TreeFind(BTNode* root, BTDataType x)
{if (root NULL)return NULL;if (root-_data x)return root;BTNode* ret1 TreeFind(root-_left, x);if (ret1)return ret1;//return TreeFind(root-_right, x);BTNode* ret2 TreeFind(root-_right, x);if (ret2)return ret2;return NULL;
}
// 二叉树销毁
void TreeDestory(BTNode* root)
{if (root NULL)return;TreeDestory(root-_left);TreeDestory(root-_right);free(root);
}
// 层序遍历
#includeQueue.h
void TreeLevelOrder(BTNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);printf(%d , front-_data);if (front-_left)QueuePush(q, front-_left);if (front-_right)QueuePush(q, front-_right);}QueueDestroy(q);
}
// 判断二叉树是否是完全二叉树
bool TreeComplete(BTNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);// 遇到第一个空就可以开始判断如果队列中还有非空就不是完全二叉树if (front NULL){break;}QueuePush(q, front-_left);QueuePush(q, front-_right);}while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);// 如果有非空就不是完全二叉树if (front){QueueDestroy(q);return false;}}QueueDestroy(q);return true;
}
int main()
{BTNode* root CreatBinaryTree();PrevOrder(root);printf(\n); InOrder(root);printf(\n);PostOrder(root);printf(\n);printf(TreeSize:%d\n, TreeSize(root));printf(TreeLeafSize:%d\n, TreeLeafSize(root));printf(TreeHeight:%d\n, TreeHeight(root));printf(TreeLevelKSize:%d\n, TreeLevelKSize(root, 3));TreeLevelOrder(root);printf(\n);TreeComplete(root);TreeDestory(root);root NULL;return 0;
}
