乔拓云建站平台不是免费的,广告位网站模板,电子商务网站经营性icp,app推广是什么意思接着上一节。我们接着学习二叉树#xff0c;学习使用链表建立二叉树时#xff0c;最好把每个子程序的递归展开图#xff0c;都画一下
前言
在学习二叉树的基本结构前#xff0c;需先要创建一颗二叉树#xff0c;然后才能学习其相关的基本操作#xff0c;由于现在大家二…接着上一节。我们接着学习二叉树学习使用链表建立二叉树时最好把每个子程序的递归展开图都画一下
前言
在学习二叉树的基本结构前需先要创建一颗二叉树然后才能学习其相关的基本操作由于现在大家二叉树的结构了解的不够深入为了减低学习成本这里手动快速创建一颗简单的而二叉树快速进入二叉树操作学习等二叉树结了解的差不多时我们反过头来研究二叉树真正的创建方式
4. 二叉树链式结构的简单实现
4.1创建二叉树
-1.快速手搓二叉树
二叉树图示 代码实现
typedef int BTDataType;typedef struct BinaryTreenode
{struct BinaryTreenode* left;struct BinaryTreenode* right; BTDataType data;
}BT;BT* BuyNode(BTDataType x)
{BT* newnode (BT*)malloc(sizeof(BT));if(NULL newnode){perror(BuyNode::malloc);return NULL;}newnode-data x;newnode-left NULL;newnode-right NULL;return newnode;
}int main()
{BT* node1 BuyNode(1);BT* node2 BuyNode(2);BT* node3 BuyNode(3);BT* node4 BuyNode(4);BT* node5 BuyNode(5);BT* node6 BuyNode(6);BT* node7 BuyNode(7);node1-left node2;node1-right node4;node2-left node3;node4-left node5;node4-right node6;return 0;
}
创建七个结点使用前六个组成一个二叉树留一个备用
-2.二叉树的前序中序后序遍历
前序根节点-左子树-右子树
代码实现
//前序
void PrevOrder(BT* root)
{if (NULL root){printf(NULL );return;}printf(%d , root-data);PrevOrder(root-left);PrevOrder(root-right);
}
前序递归展开图只要有节点它就一定有子节点例如3他就需要遍历它的两颗空树NULL大家可以画一下递归展开图利于我们理解递归 前序大致的顺序1 2 3 NULL NULL NULL 4 5 NULL NULL 6 NULL NULL
测试 中序左子树-根节点-右子树
代码实现
//中续
void InOrder(BT* root)
{if (NULL root){printf(NULL );return;}InOrder(root-left);printf(%d , root-data);InOrder(root-right);
}
中序递归展开图 中序顺序NULL NULL 3 2 NULL 1 NULL 5 NULL 4 NULL 6 NULL
测试 后序左子树-右子树-根
代码实现
void PostOrder(BT* root)
{if(NULL root){printf(NULL);return;}PostOrder(root-left);PostOrder(root-right);printf(%d\n, root-data);
}
后续递归展开图 后序顺序NULL NULL 3 NULL 2 NULL NULL 5 NULL NULL 6 4 1
测试 -3.二叉树节点个数
代码实现
//求二叉树所有节点方法一:
int size 0; //全局变量
int TreeSize(BT* root)
{//使用静态变量//static int size 0; 不行因为初始化一次之后就不能在初始化了会造成累加if (NULL root){return;}size;TreeSize(root-left);TreeSize(root-right);return size;
}方法二:
int TreeSize1(BT* root, int* Size1)
{if (NULL root){return;}(*Size1);TreeSize1(root-left, Size1);TreeSize1(root-right, Size1);return *Size1;
}// 方法三 对比以上面两个代码大大的减少了代码量使用起来更有效率
int TreeSize3(BT* root)
{return root NULL ? 0 :TreeSize3(root-left) TreeSize3(root-right) 1;
}
方法三递归展开图 总节点为: 6
测试 -4.二叉树的高度/深度
代码实现
int BinaryTreeHeight(BT* root)
{if(root NULL){return 0;}int lHeight BinaryTreeHeight(root-lrft);int rHeight BinaryTreeHeight(root-right);return lHeight rHeight ? lHeight 1 : rHeight 1;
}
递归展开图 这张图只标记了左子树的递归展开右子树也是一样的最后左子树和右子树深度相比将大那个加1输出就可以了
测试 -5.求二叉树k层的个数
代码实现
//求k层的个数
int TreeLevelK(BT* root, int k)
{if (root NULL){return 0;}if (k 1){return 1;}int leftk TreeLevelK(root-left, k - 1);int right TreeLevelK(root-right, k - 1);return leftk right;
}
递归展开图
求二叉树第三层的节点个数 测试 -6.二叉树查找值为x的节点
代码实现
//二叉树查找值为x的结点
BT* BinaryTreeFind(BT* root, BTDataType x)
{if (root NULL)return NULL;if (root-data x)return root;BT* lret BinaryTreeFind(root-left, x);if (lret)return lret;BT* rret BinaryTreeFind(root-right, x);if (rret)return rret;return NULL;
}递归展开图 测试 -7.层序遍历
层序遍历是使用队列实现的这里没有使用递归这里看我上几节写的队列
将链表的成员换为二叉树的节点用来存储二叉树的节点然后利用队列的性质将二叉树的值层序输出就可以了 //层序遍历
void LevelOrder(BT* root)
{Queue q;QueueInit(q);if(root)QueuePush(q, root);printf(LevelOrder: );while (!QueueEmpty(q)){BT* 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);
}
测试
