【王道数据结构】【chapter5树与二叉树】【P159t15】

本文主要是介绍【王道数据结构】【chapter5树与二叉树】【P159t15】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

设计一个算法将二叉树的叶结点从左到右的顺序连成一个单链表，表头指针为head。二叉树按二叉链表方式存储，链接时用叶结点的右指针来存放单链表指针。

#include <iostream>
#include <stack>
#include <queue>
typedef struct treenode{char data;struct treenode *left;struct treenode *right;
}treenode,*ptreenode;ptreenode buytreenode(char x)
{ptreenode n=(ptreenode) malloc(sizeof (treenode));n->data=x;n->left= nullptr,n->right= nullptr;return n;
}
ptreenode build_tree()
{ptreenode root= buytreenode('A');root->left= buytreenode('B');root->right= buytreenode('C');root->left->left= buytreenode('D');root->left->right= buytreenode('E');root->right->left= buytreenode('F');root->right->right= buytreenode('G');root->left->left->left= buytreenode('H');root->left->left->right= buytreenode('I');return root;
}ptreenode build_tree2()
{ptreenode root= buytreenode('A');root->left= buytreenode('B');root->right= buytreenode('C');root->left->left= buytreenode('D');root->left->right= buytreenode('E');root->right->left= buytreenode('F');root->right->right= buytreenode('G');root->left->left->left= buytreenode('H');root->left->left->right= buytreenode('I');root->left->right->left= buytreenode('J');root->left->right->right= buytreenode('K');root->right->right->left= buytreenode('L');root->right->right->right= buytreenode('M');return root;
}ptreenode build_tree3()
{ptreenode root= buytreenode('A');root->left= buytreenode('B');root->right= buytreenode('C');root->left->left= buytreenode('D');root->left->right= buytreenode('E');root->right->left= buytreenode('F');root->right->right= buytreenode('G');root->left->left->left= buytreenode('H');root->left->left->right= buytreenode('I');root->left->right->left= buytreenode('J');root->left->right->right= buytreenode('K');root->right->left->left= buytreenode('L');root->right->left->right= buytreenode('M');root->right->right->left= buytreenode('N');root->right->right->right= buytreenode('O');return root;
}void print_tree(ptreenode root) {std::queue<ptreenode> tmp;tmp.push(root);int s = tmp.size();while (!tmp.empty()) {ptreenode t = tmp.front();tmp.pop();s--;printf("%3c", t->data);if (t->left) tmp.push(t->left);if (t->right) tmp.push(t->right);if (s == 0) puts(""), s = tmp.size();}
}void _linkleaf(ptreenode root ,ptreenode &head,ptreenode &pre)
{if(root== nullptr) return;_linkleaf(root->left,head,pre);if(!root->left&&!root->right)//叶子结点{if(head== nullptr)head=root,pre=root;else pre->right=root,pre=pre->right;}_linkleaf(root->right,head,pre);
}
ptreenode linkleaf(ptreenode root)
{ptreenode head=(ptreenode) malloc(sizeof (ptreenode));ptreenode pre= (ptreenode) malloc(sizeof (ptreenode));pre= nullptr,head= nullptr;_linkleaf(root,head,pre);return head;
}
int main() {ptreenode root=build_tree();print_tree(root);ptreenode tmp= linkleaf(root);printf("the leaves' link is:");for(ptreenode i=tmp;i;i=i->right) printf("%3c",i->data);puts("");root=build_tree2();print_tree(root);tmp= linkleaf(root);printf("the leaves' link is:");for(ptreenode i=tmp;i;i=i->right) printf("%3c",i->data);puts("");root=build_tree3();print_tree(root);tmp= linkleaf(root);printf("the leaves' link is:");for(ptreenode i=tmp;i;i=i->right) printf("%3c",i->data);puts("");return 0;
}