//节点结构
public class Treenode{
private int index;
private T data;
private Treenode left;
private Treenode right;
public Treenode(int index, T data){
this.index = index;
this.data = data;
this.left = null;
this.right = null;
}
}
//构建树
public class BinaryTree{
public Treenode root = null;
public BinaryTree(){
root = new Treenode<>(1,'A');
}
public void createTree(){
Treenode B = new Treenode(1,'B');
root.left = B;
}
//获取二叉树的高度和大小:一个节点有一个左孩子或者右孩子，高度就 + 1，所以二叉树的高度就是取左孩子与右孩子的最大值，然后加根节点的 1 。获取大小就是获取二叉树所有左孩子与右孩子的节点之和了，最后也要加根节点的 1。
public int getheight(){
return getheight(root)
}
public int getheight(Treenode node){
if (node==null) {
return 0;
}
int left = getheight(node.left);
int height = getheight(node.right);
return left>height?(left+1):(height+1);
}
public int getsize(){
return getsize(root)
}
public int getsize(Treenode node){
if (node==null) {
return 0;
}
int left = getsize(node.left);
int right = getsize(node.right);
return left+height+1;
}
//二叉树的遍历本质上还是递归，只是跟的位置不同而已。
//先序遍历
public void preOrder(Treenode node){
if (node==null) {
return ;
}
System.out.println(node.data+"" );
preOrder(node.left);
preOrder(node.right);
}
// 用栈 迭代 实现前序遍历
public static void preOrder2(Treenode root){
if (root==null) {
return ;
}
Stack<Treenode> stack = new Stack<Treenode>();
stack.push(root);
while(!stack.isEmpty()){//push the right one firstly and it will pop out later
Treenode node = stack.pop();
System.out.print(node.data+"");
if (node.right!=null) {
stack.push(node.right);
}
if (node.left!=null) {
stack.push(node.left)
}
}
}
//中序遍历
public void midOrder(Treenode node){
if (node==null) {
return ;
}
midOrder(node.left);
System.out.println(node.data+"");
midOrder(node.right);
}
// 用栈 迭代 实现中序遍历 .
public static void midOrder2(Treenode node){
if (node == null) {
return;
}
Stack<Treenode> stack = new Stack<Treenode>();
Treenode cur = node;
while(!stack.isEmpty()||cur!=null){
if (cur!=null) {
stack.push(cur);
cur = cur.left//左边遍历
}else{
cur = stack.pop();//弹出的是相对而言的根节点，打印出来 再依次遍历右节点，
System.out.print(pop.data);
cur = cur.right;
}
}
}
//后序遍历
public void afterOrder(Treenode node){
if (node==null) {
return;
}
afterOrder(node.left);
afterOrder(node.right);
System.out.println(node.data+"");
}
// 用栈 迭代 实现后序遍历 .
public void afterOrder2(Treenode root){
if (root == null) {
return;
}
Stack<Treenode> stack1 = new Stack<Treenode>();
Stack<Treenode> stack2 = new Stack<Treenode>();
stack1.push(root);
while(!stack1.isEmpty()){
Treenode node = stack1.pop();
stack2.push(node);
if (node.left !=null) {
stack1.push(node.left);
}
if (node.right != null) {
stack1.push(node.right);
}
}
while(!stack2.isEmpty()){
System.out.print(stack2.pop().dara+"");
}
}
//分层遍历二叉树 宽度优先遍历
public static void levelTravals(Treenode root){
if (root == null) {
return;
}
Linklist<Treenode> queue = new Linklist<Treenode>();
queue.push(root);
while(!queue.isEmpty){
Treenode cur = queue.removeFirst();
System.out.println(cur.data+"")
if (cur.left != null) {
queue.add(cur.left);
}
if (cur.right!= null) {
queue.add(cur.right);
}
}
}
//按层打印二叉树.更新下一行的最右节点进行遍历
public static void printFromToptoBottom(Treenode root){
if (root == null) {
return;
}
Queue<Treenode> queue = new Queue<Treenode>(100);
queue.add(root);
Treenode curright = root;
Treenode nextright = root;
int level = 1;
while(!queue.isEmpty()){
Treenode node = queue.poll();
System.out.print(node.data +"");
if (node.left!=null) {
queue.add(node.left);
nextright = node.left;
}
if (node.right!=null) {
queue.add(node.right);
nextright = node.right;
}
if (node == curright) {
System.out.println(level +"");
level++;
curright = nextright;
}
}
}
}
Class Node{
int data;
Node next;
public Node(int data){
this.data =data;
};
}
//删除单链表指定节点
public void deletnodes(Node head,Node node){
//end 顺序查找法找到尾节点前一个
if (node.next == null) {
while(head.next!=node){
head = head.next;
}
head = null;
}
else if (node == head) {
head = null;
}
else {
Node q = node.next;
node.data = q.data;
node.next = q.next;
}
}
//删除单链表指定数值的节点
//stack
public Node deletValue1(Node head,int num){
Stack<Node> stack = new Stack<Node>();
while(head != null){//指空推出
if (head.next!=num) {
stack.push(head.next);
}
head=head.next;
}
while(!stack.isEmpty()){
stack.peek().next = head;//第一次指向空
head =stack.pop();
}
}
//no stack find the first not to be deleted node as our new list's head
public Node deletValue2(Node head,int num){
while(head!=null){
if (head.data != num) {
break;
}
head = head.next;
}
Node pre = head;
Node cur = head;
while(cur.data!=null){
if (cur.data==num) {
pre.next =cur.next;
}else{
pre = cru;
}
cur = cur.next;
}
}
//删除单链表中数值重复的节点用 hashset实现 contain
public void deletrepeatednodes(Node head){
if (head ==null) {
return;
}
Hashset<Integer> set = new Hashset<Integer>();
Node pre = head;
Node cur = head;
set.add(head.data);
while(cur!=null){
if (set.contain(cur.data)) {
pre.next = cur.next;
}else{
set.add(cur.data);
pre = cur;
}
cur = cur.next;
}
}
// 两个单链表生成相加的列表：每一节点的值都在0~9之间，个位数生成新链表
public Node addlist(Node head1,Node head2){
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
while (head1!=null){
stack1.push(head1.data);
head1 = head1.next;
}
while (head2!=null){
stack2.push(head2.data);
head2 = head2.next;
}
int n1 =0;
int n2 =0;
int n =0;//node1+node2
Node node = null;
Node cur = null;
while (!stack1.isEmpty()||!stack2.isEmpty()) {
n1 = stack1.isEmpty()?0:stack1.pop();
n2 = stack2.isEmpty()?0:stack2.pop();
n = n1+n2+ca;
cur = new Node(n%10);
cur.next = node;
node = cur;
}
return cur;
}
//判断单链表是否为回文结构123321 栈
public boolean isPalindrome(Node head){
if (head == null) {
return false;
}
Stack<Integer> stack = new Stack<Integer>();
Node cur = head;
while(cur!=null){
stack.push(cur.data);
cur = cur.next;
}
while(head!=null){
if (head.data != stack.pop()) {
return false;
}
head = head.next;
}
return true;
}
//删除单链表的倒数第k个节点
public static Node deleteLastKthNode(Node head,int k){
if (k<=0||head==null) {
return head;
}
Node cur = head;
Node kthbefore = head;
for (int i = 0;i<k+1 ; k++) {
if (cur==null) {
return head;
}
cur = cur.next;
}
while(cur != null){
cur = cur.next;
kthbefore = kthbefore.next;
}
kthbefore.next = kthbefore.next.next;
return head;
}
//用两个栈实现一个队列；先进后出+先进后出=先进先出。压入栈+弹栈
public class QueenwithStacks{
private static Stack<Object> stack1 = new Stack<Object>();
private static Stack<Object> stack2 = new Stack<Object>();
public static void pushintostarck1(Object item){
stack1.push(item);
}
public static void pushintostarck2(){
while (!stack2.isEmpty()) {
stack2.pop();
}
if (stack1.isEmpty()) {
throw new RuntimeException();
}
while(!stack1.isEmpty){
Object item = stack1.pop();
stack2.push(item);
}
}
}
网友评论